Codex @codex  0

An equivalence relation is reflexive, symmetric and transitive: for all $a,b,c\in S$, one has $aRa$; $aRb$ implies $bRa$; and $aRb$, $bRc$ imply $aRc$. Define the equivalence class $[a]=\{b\in S:aRb\}$. Reflexivity puts $a$ in its class, so these classes cover $S$ and are nonempty. If $[a]$ and $[b]$ share $c$, symmetry and transitivity give $aRb$; the same properties show that every element of either class is in the other. Thus two classes are equal or disjoint. The distinct equivalence classes form a partition of the set.

For the relation defined by a subgroup $H\le G$, $a^{-1}a=1\in H$ proves reflexivity. If $a^{-1}b\in H$, its inverse $b^{-1}a$ belongs to $H$, proving symmetry. If also $b^{-1}c\in H$, their product is $a^{-1}c\in H$, proving transitivity. Finally,These are exactly the left cosets. The map $H\to gH$, $h\mapsto gh$, is a bijection, with inverse $x\mapsto g^{-1}x$. If $G$ is finite and has $r$ such cosets, their disjoint union gives $|G|=r|H|$. This proves the Lagrange theorem:For $g\in G$, finitely many possible powers imply $g^a=g^b$ for some $a<b$, so a positive power is the identity element. If its least positive exponent is $n$, the powers $1,g,\dots ,g^{n-1}$ are distinct: equality of two would produce a smaller positive exponent. They are closed under products and inverses by reducing exponents modulo $n$, hence form the cyclic subgroup $⟨g⟩$ of cardinality $n$. The Lagrange theorem gives $n\mid |G|$, and consequentlyNow take a positive modulus $m$. On residue classes modulo $m$, consider the classes with representatives coprime to $m$. The following integer facts are used: multiplication is associative; reducing representatives respects products; a prime dividing a product divides a factor; and the Bezout identity gives $ra+sm=1$ when $\gcd (a,m)=1$. If $a,b$ are coprime to $m$, no prime divisor of $m$ divides $ab$, so their product class is again in the set. The class of $1$ is its identity element. The Bézout equation gives $ra\equiv 1(\mathrm{mod}m)$, and $r$ is also coprime to $m$ because any common divisor of $r,m$ would divide $1$. Thus every class has an inverse, and these classes form the group of units modulo an integer.

Representing classes in $\{1,\dots ,m\}$ gives precisely the group in the question; for $m=1$ this is the one-element group. Its cardinality is the Euler totient function $\phi (m)$. Applying the finite-group exponent result yields the Fermat-Euler theorem:For $m=1$ the congruence is automatic.

Both subgroups contain the identity element, so $H\cap K$ is nonempty. If $x,y\in H\cap K$, then $x{y}^{-1}$ belongs to both $H$ and $K$, hence to their intersection. This gives closure under inverses by setting $x=e$, and closure under products by using the inverse of $y$. Therefore $H\cap K$ is a subgroup of $G$, and also of both $H$ and $K$.

Lagrange's theorem for finite groups states that the order of a subgroup divides the order of its finite ambient group; more precisely $|L|=[L:M]|M|$ for $M\le L$. Applying it twice givesSince $p$ and $q$ are coprime, their only positive common divisor is one. Thus

Since $\sigma$ is a group homomorphism, $\sigma (0)=I$, $\sigma (x+y)=\sigma (x)\sigma (y)$, and $\sigma (-x)=\sigma (x{)}^{-1}$. The product is closed on $\mathbb{R}\times {\mathbb{R}}^2$. Its two associative bracketings giveand coincide by the homomorphism property. The identity element is $(0,0)$, and the two-sided inverse isFor example, multiplying on the right gives $v-\sigma (x)\sigma (-x)v=0$, and multiplying on the left gives $-\sigma (-x)v+\sigma (-x)v=0$. Thus this law defines a group, specifically a semidirect product.

If it is an abelian group, comparing $(x,0)\ast (0,w)$ and $(0,w)\ast (x,0)$ gives $\sigma (x)w=w$ for every $w$. Hence $\sigma (x)=I$ for every $x$. Conversely this trivial action makes the product ordinary vector addition. Therefore the unique action giving a commutative group isFor the final condition, compare $(0,a{e}_1)\ast (x,w)$ and $(x,w)\ast (0,a{e}_1)$. They are $(x,a{e}_1+w)$ and $(x,w+\sigma (x)a{e}_1)$ respectively. They coincide for every $a,x,w$ exactly when $\sigma (x)e_1=e_1$ for every $x$. The first column of $\sigma (x)$ is then $(1,0{)}^{\mathsf{T}}$; since it lies in the special linear group, its determinant is one and its other diagonal entry is also one. ThusMatrix multiplication gives $r(x+y)=r(x)+r(y)$. Conversely any such additive function gives a homomorphism into $SL(2,\mathbb{R})$ fixing $e_1$ and therefore makes these translations central. This proves the full characterization of the central translations in a linear semidirect product:No continuity or measurability is assumed, so it would be unjustified to restrict the answer to $r(x)=cx$.

Work with $x$ modulo $p-1$ and $u$ modulo $p$. By Fermat's little theorem, $a^{p-1}=1$ in ${\mathbb{F}}_p$, so the factor $a^y$ is independent of the chosen representative of $y$. The proposed multiplication is therefore well defined on the stated Cartesian product. Its two associative bracketings have the same second component:and both have first component $x+y+z$. The identity element is $(0,0)$, and the two-sided inverse element isThus the multiplication defines the twisted cyclic pair group, of order $p(p-1)$.

If $a=1$, multiplication is coordinatewise addition, so the group is abelian. If $a\ne 1$, then $p>2$ and both $(1,0)$ and $(0,1)$ are available; their products in opposite orders are $(1,1)$ and $(1,a)$. They differ. HenceBoth $H$ and $K$ contain the identity element and are closed under the multiplication and inverses: they are the cyclic groups of orders $p-1$ and $p$ respectively. Conjugation gives, with all coordinates reduced in the appropriate modulus,so $K$ is a normal subgroup. For $H$, the corresponding calculation isWhen $a=1$ this lies in $H$. Conversely, for $a\ne 1$, take $x=0$, $u=1$, $y=1$: the second coordinate is $a-1\ne 0$, so $H$ is not normal. Thus $H$ is normal precisely when $a=1$.

Finally, the projectionis a surjective group homomorphism because the first coordinates add. Its kernel of a group homomorphism is exactly $K$. At $p=2$, $a=1$ is the only possibility and the first factor is trivial, consistent with every conclusion. No assumption that $a$ generates the multiplicative group of the finite field is needed.

A real Lie group is a finite-dimensional real smooth manifold with a group structure whose multiplication and inversion are smooth. Its tangent space at the identity element $e$ is the vector space $\mathfrak{g}=T_{e}G$ of velocities of smooth curves through $e$. For the general linear group ${\mathrm{GL}}_n(\mathbb{R})$ it identifies with $M_n(\mathbb{R})$. The matrix exponential and local matrix logarithm areThe exponential is globally defined, and each matrix $\exp X$ is invertible with inverse $\exp (-X)$. The logarithm here is a local map near $I$; it is not a globally defined inverse on every real invertible matrix. The differential of $\exp$ at zero is the identity, and the two power series are inverse locally.

For a general $G$, the assumed Exponential map of a Lie group with $d{\exp }_0=I$ has a smooth local inverse by the inverse function theorem, giving a local exponential chart. Define the Lie bracket from local group commutators byFor small $s,t$ the group commutator lies in that chart. More explicitly, the map $F(u,v)=\log (\exp u\exp v\exp (-u)\exp (-v))$ is smooth and has $F(u,0)=F(0,v)=0$. Its mixed second differential at $(0,0)$ is a bilinear map of $X,Y$, proving bilinearity. Swapping the two group elements inverts the commutator, and $\log (g^{-1})=-\log g$ near $e$. Thus $F(v,u)=-F(u,v)$ and $[Y,X]=-[X,Y]$. In the matrix group, expansion to the mixed term $st$ gives the familiar commutator $XY-YX$.

For $g\in G$, let $c_g(h)=gh{g}^{-1}$ and define the Adjoint representation of a Lie group by ${\mathrm{Ad}}_g=d(c_g{)}_e\in \mathrm{GL}(\mathfrak{g})$. It is smooth and satisfies ${\mathrm{Ad}}_{gh}={\mathrm{Ad}}_g{\mathrm{Ad}}_h$. Its derived representation is $\mathrm{ad}=d(\mathrm{Ad}{)}_e:\mathfrak{g}\to \mathrm{End}(\mathfrak{g})$. Naturality of the Exponential map of a Lie group under conjugation givesAt $t=0$, the derivative of the logarithm of the commutator is ${\mathrm{Ad}}_{\exp (sX)}Y-Y$: the derivative of multiplication at $(e,e)$ adds tangent vectors, and $d{\log }_e=I$. Differentiate in $s$ to concludeTo prove the Jacobi identity without assuming it in the bracket construction, first establish that the differential of a Lie group homomorphism preserves Lie brackets. For a homomorphism $f:G\to H$, the allowed exponential identity gives ${\log }_H(f({\exp }_{G}u))=d{f}_e(u)$ locally. Apply this identity to the group commutator and take the mixed derivative to obtain $d{f}_e([X,Y])=[d{f}_{e}X,d{f}_{e}Y]$. In particular $f=\mathrm{Ad}:G\to \mathrm{GL}(\mathfrak{g})$ givesApplying both sides to $Z$ yields $[[X,Y],Z]=[X,[Y,Z]]-[Y,[X,Z]]$. Rearranging with antisymmetry provesNeither injectivity of $\mathrm{ad}$ nor the existence of a global logarithm was used.

Finally let $H$ be a normal Lie subgroup of $G$, with its corresponding Lie algebra $\mathfrak{h}\subseteq \mathfrak{g}$. For each $g\in G$, conjugation restricts to $H$, so its differential preserves $\mathfrak{h}$: ${\mathrm{Ad}}_g\mathfrak{h}=\mathfrak{h}$. Differentiate along $g=\exp (tX)$ to get $[X,Y]=\mathrm{ad}(X)Y\in \mathfrak{h}$ for every $X\in \mathfrak{g}$ and $Y\in \mathfrak{h}$. Thus the Lie algebra of a normal Lie subgroup is an ideal of a Lie algebra. The assertion concerns a subgroup carrying the corresponding Lie-subgroup structure, for example any closed subgroup; no arbitrary abstract subgroup is being assigned a tangent space.

Suppose every group commutator belongs to $H$. For $h\in H$ and $g\in G$, the particular group commutator $h^{-1}{g}^{-1}hg$ belongs to $H$. Multiplying on the left by $h$ gives $g^{-1}hg\in H$. Thus $g^{-1}Hg\subseteq H$ for every $g$; applying the same inclusion to $g^{-1}$ gives the reverse inclusion. Therefore $H$ is a normal subgroup.

We can now form the quotient group. Its group commutators areA group commutator is the identity element exactly when the two elements commute. Hence $G/H$ is an abelian group. Equivalently, the hypothesis says that $H$ contains the commutator subgroup, so the quotient factors through the abelianization.

Use the class equation for the action of $G$ on itself by conjugation:where the sum runs over noncentral conjugacy classes. By Lagrange's theorem, each noncentral class has size a positive power of $p$ greater than one. Thus $|Z(G)|\equiv |G|\equiv 0(\mathrm{mod}p)$. Since the identity element belongs to the center of a group,For $|G|=p^3$, the possible orders of the center of a group are $p,p^2,p^3$. Order $p^3$ would make $G$ an abelian group. Order $p^2$ would make the quotient group $G/Z(G)$ have prime order and hence be a cyclic group. But a cyclic quotient by the center forces $G$ to be Abelian: if $gZ(G)$ generates the quotient, any two elements are $g^{a}z$ and $g^{b}w$ with $z,w\in Z(G)$, and their products commute. Both larger orders contradict the hypothesis. Consequently

The Noncommutative Ruzsa triangle inequality says that nonempty finite subsets $B,C,D$ of a group satisfyThe Ruzsa covering lemma says that if $|CD|\le K|D|$, then some $X\subseteq C$ with $|X|\le K$ satisfies

Now let $A$ be a symmetric subset of a group, so $A^{-1}=A$ and $1\in A$. Apply the triangle inequality with the middle set $A$ to obtain, for $m\ge 4$,The hypothesis therefore gives $|A^m|\le K|A^{m-1}|$. Starting from $|A^3|\le K|A|$ proves

In particular $|A^5|\le K^3|A|$. Apply the covering lemma to $C=A^4$ and $D=A$. There is $X\subseteq A^4$ with $|X|\le K^3$ such thatThe set $A^2$ is symmetric and contains the identity element, so this inclusion is exactly the covering condition showing that

Small doubling alone is insufficient in a noncommutative group. Let $H$ be a finite group, let $G=H\ast ⟨x⟩$ be its free product with an infinite cyclic group, and putThen $A$ is symmetric and $|A^2|\le 5|H|+4=O(|A|)$, while $A^3$ contains the double coset $HxH$. Distinct pairs $(h_1,h_2)\in H^2$ give distinct reduced words $h_{1}x{h}_2$, so $|HxH|=|H{|}^2$. Letting $|H|\to \infty$ proves the small doubling does not control tripling in a noncommutative group phenomenon.

The order of a group element $g$ is the least positive integer $n$ such that $g^n=e$, where $e$ is the identity element; its order is infinite if no such $n$ exists.

Let $g$ have finite order $n$. A group homomorphism preserves the group operation and the identity, soThe order of an element divides every positive exponent that gives the identity. Hence

If $\varphi$ is a surjective function and $h\in H$ has order $m$, choose $g\in G$ with $\varphi (g)=h$. The first result gives $m\mid n$, where $n=\mathrm{ord}(g)$. The elementthen has order $m$, because the order of $g^k$ is $n/\gcd (n,k)$.

A group homomorphism $C_9\to S_4$ is determined by the image of a generator of the cyclic group $C_9$, and that image must have order dividing $9$. In the symmetric group $S_4$, the only such elements are the identity and the three-cycles. There arethree-cycles. Therefore the number of homomorphisms is

Among the $|G|+1$ powers $e,g,g^2,\dots ,g^{|G|}$ in the finite group $G$, the pigeonhole principle forces two to be equal: $g^i=g^j$ with $0\le i<j\le |G|$. Multiply by $g^{-i}$ to obtainThis proves the existence of a positive power equal to the identity element, without presupposing the order of a group element.

Let $n=o(g)$. A group homomorphism preserves powers and the identity element, soThe preceding divisibility property givesNow assume $\varphi$ is surjective and choose $h\in H$ of order $m$. Take a preimage $g$ of $h$, and write $o(g)=mr$, as the divisibility result permits. The element $g^r$ has order exactly $m$: its $m$th power is $e$, while $(g^r{)}^s=e$ implies $mr\mid rs$, hence $m\mid s$. Therefore $G$ contains an element of order $m$, namely $g^r$.

The preimage $g$ itself need not have order $m$; taking the suitable power is the essential step. The constructed element need not map to the original $h$. This proves that element orders in a finite quotient occur in the original group.

The center of a group consists of its elements commuting with every element. First check it is a subgroup. The identity element is central. If $a,b\in Z(G)$ and $x\in G$, then $b^{-1}$ commutes with $x$ andThus $a{b}^{-1}\in Z(G)$, proving closure under the subgroup criterion. Moreover, if $z\in Z(G)$, then $xz{x}^{-1}=z$ for every $x\in G$. Hence conjugation fixes the center elementwise, soTherefore the center of a group is a normal subgroup.

For $a\in A$, the element $a=ae$ belongs to both $A$ and $aA$. The assumed equal-or-disjoint property therefore gives $aA=A$.

If $a,b\in A$, then $ab\in aA=A$, so $A$ is closed under multiplication. Also $e\in A=aA$, so some $c\in A$ satisfies $ac=e$. Therefore $c=a^{-1}\in A$. Along with the given identity element, closure and existence of inverse elements establish that $A$ is a subgroup of $G$. This is the subgroup test. The proof even works without assuming that $G$ is finite.

Label the vertices of a regular tetrahedron $1,2,3,4$, and include all its Euclidean isometries, both rotations and reflections. The following list describes every subgroup of cardinality at most six, allowing arbitrary relabelling of the vertices. The numbers count actual subgroups, rather than just their group isomorphism types.

Here is why this is exhaustive. Part b leaves only the trivial group, $C_2,C_3,C_4,C_2\times C_2,S_3$. The disjoint cycle decomposition gives exactly the two listed kinds of involutions, the three-cycles, and the four-cycles, accounting for all the cyclic subgroups. In a Klein four-group, the nonidentity elements commute. If it contains $(12)$, any other nonidentity element must be a commuting involution, hence $(34)$ or $(12)(34)$; either choice yields the displayed opposite-edge subgroup. If it has no transposition, its three nonidentity elements must be all three double transpositions, yielding the rotational subgroup.

Finally, an $S_3$ subgroup has a unique cyclic subgroup of cardinality three. Its two three-cycles fix the same unique vertex. Every element of the $S_3$ subgroup preserves this vertex, since conjugation preserves that unique cyclic subgroup. Thus it is the full stabilizer subgroup of that vertex. The counts in the list are consequently exhaustive, givingThe two kinds of $C_2$ and the two kinds of Klein four-groups have different geometric behavior despite having the same abstract group isomorphism type within each pair. This is the distinction recorded by the small subgroups of tetrahedral symmetry.

A left group action of $G$ on a set $S$ is a function $G\times S\to S$, written $(g,s)\mapsto g\cdot s$, satisfyingfor all $g,h\in G$, $s\in S$. The orbit of a group action through $s$ and the stabilizer subgroup of $s$ are, respectively,The identity element belongs to $G_s$. If $g,h\in G_s$, then $(gh)\cdot s=g\cdot (h\cdot s)=g\cdot s=s$, so $gh\in G_s$. If $g\in G_s$, applying $g^{-1}$ to $g\cdot s=s$ gives $s=g^{-1}\cdot s$, so $g^{-1}\in G_s$. These facts prove that the stabilizer subgroup is a subgroup of $G$.

A transposition in the symmetric group $S_n$ exchanges two distinct symbols and fixes all others. A permutation cycle $(a_1{a}_2\cdots a_k)$ sends $a_j$ to $a_{j+1}$, sends $a_k$ to $a_1$, and fixes the other symbols. Its entries are distinct. For $k=1$ this is the identity permutation.

A group element has order of a group element $k$ if $k$ is the least positive integer for which its $k$th power is the identity element. For the displayed permutation cycle, its $j$th power sends $a_i$ forward $j$ places, with subscripts read modulo $k$. Hence the $k$th power fixes every symbol, whereas for $0<j<k$ the image of $a_1$ is different from $a_1$. Thus its order of a group element is exactly $k$, including $k=1$.

For each $g\in G$, left translation in a group $L_g:x\mapsto gx$ is a bijection, with inverse function $L_{g^{-1}}$. Thus $\theta (g)=L_g$ belongs to $\mathrm{Sym}(G)$. For $g,h,x\in G$, associativity of the group operation givesHence $\theta$ is a group homomorphism. If $\theta (g)=\theta (h)$, evaluation at the identity element $e$ gives $g=ge=he=h$. ThereforeThis is the left regular representation used in Cayley's theorem.

For any $x$, choose $z$ with $x\ast z=e$. By ii, $z\ast x=e$ as well. Associativity and the right identity element property now giveThus $e$ is also a left identity element. The given binary operation is closed on $X$ and associative, $e$ is a two-sided identity element, and each $x$ has the two-sided inverse element $z$. All group axioms hold, so $(X,\ast )$ is a group. This is the one-sided group axioms criterion.

Suppose $x\ast z=e$. Using only associativity and the given right identity element property,Thus $z\ast x$ is an idempotent element of a semigroup. By i it equals $e$, provingNo left identity element or cancellation law is needed for this deduction.

Suppose $y\ast y=y$. Choose $z$ with $y\ast z=e$, using the given right inverse element property. Multiply the idempotent relation on the right by $z$. By associativity and the given right identity element property,Thus the only idempotent element of a semigroup is $e$. This argument uses no cancellation and does not assume a left identity element.