Free Groups and Presentations

For a word $w$, read its letters from left to right while maintaining a reduced stack: append a new letter unless it is the formal inverse of the stack's last letter, in which case delete that last letter. Induction on the length of $w$ gives a reduced output $\operatorname{red}(w)$, with $\operatorname{red}(r)=r$ for every reduced word $r$.

The same induction shows that reading a neighbouring pair $aa^{-1}$ or $a^{-1}a$ has exactly the same net effect on every preceding stack as omitting that pair. Thus $\operatorname{red}$ is unchanged by an elementary cancellation or reverse insertion; hence $w$ is freely equivalent to $\operatorname{red}(w)$, and two freely equivalent reduced words are equal.

Let $F(X)$ be the set of reduced words. For reduced $r,s$, define $r\cdot s:=\operatorname{red}(rs)$, let the empty word be $e$, and let $r^{-1}$ be the reversal of $r$ with each letter formally inverted. Step 2.1 gives $\operatorname{red}(\operatorname{red}(rs)t)=\operatorname{red}(rst)=\operatorname{red}(r\operatorname{red}(st))$.

The equality in step 3.1 makes the product associative. The empty word is a two-sided identity, and $rr^{-1}$ and $r^{-1}r$ reduce by successive central cancellations to the empty word; therefore every reduced word has the stated two-sided inverse. Hence $F(X)$ is a group.

Send $x\in X$ to the one-letter word $x$. For $u:X\to G$, evaluate a word by replacing $x$ with $u(x)$ and $x^{-1}$ with $u(x)^{-1}$ and multiplying in order. Each elementary cancellation evaluates to an adjacent inverse pair, so evaluation is unchanged by step 2.1 and defines $\widehat u:F(X)\to G$; it extends $u$ and preserves the product by the definition in step 3.1.

Any homomorphism $h:F(X)\to G$ extending $u$ is forced, by writing each reduced word as its ordered product of one-letter words and their inverses, to agree with the evaluation map of step 4.2. Thus $\widehat u$ is unique.

Steps 4.1--5.1 establish the group and the extension-and-uniqueness property of [L4], so the reduced-word group is the free group on $X$.

Apply the universal property of $F$ to $i':X\to F'$ and construct the unique homomorphism $\phi:F\to F'$ with $\phi i=i'$.

Apply the universal property of $F'$ to $i:X\to F$ and construct the unique homomorphism $\psi:F'\to F$ with $\psi i'=i$.

Both $\psi\phi$ and $\operatorname{id}_F$ are homomorphisms $F\to F$ whose composites with $i$ equal $i$, so uniqueness in the universal property gives $\psi\phi=\operatorname{id}_F$.

Symmetrically, $\phi\psi=\operatorname{id}_{F'}$.

Thus $\phi$ is bijective, hence a group isomorphism.

Any generator-compatible homomorphism $F\to F'$ equals $\phi$ by the uniqueness in step 1.1; in particular the displayed isomorphism is unique.

Apply [L1] to the identity function $u:X\to G$ to obtain a homomorphism $\pi:F(X)\to G$ satisfying $\pi(x)=x$ for every $x\in X$. It is surjective because every element of $G$ is such an $x$.

Put $K:=\ker\pi$. By [L2], $K\mathrel{\trianglelefteq}F(X)$; since $K$ is itself a normal subgroup containing $K$, the minimality in [L3] gives $\langle\!\langle K\rangle\!\rangle_{F(X)}=K$.

By [L4], $\langle X\mid K\rangle=F(X)/K$. By [L5] and the surjectivity from step 1.1, $F(X)/K\cong\operatorname{im}\pi=G$.

Hence $G\cong\langle X\mid\ker\pi\rangle$, as required.

The empty sequence of elementary moves carries every word $w$ to itself, so $w\sim w$.

If a finite sequence of elementary moves carries $w$ to $w'$, reversing its order and interchanging every cancellation with the corresponding insertion gives a finite sequence from $w'$ to $w$; hence $w\sim w'$ implies $w'\sim w$.

If $w\sim w'$ and $w'\sim w''$, concatenating the two finite move sequences gives a finite move sequence from $w$ to $w''$; hence free equivalence is transitive.

If one elementary move changes $w$ to $w'$, then the same adjacent pair can be deleted or inserted inside $uwv$, so the move changes $uwv$ to $uw'v$; applying this to every move in a finite sequence gives $w\sim w'\Rightarrow uwv\sim uw'v$.

If $w\sim w'$ and $v\sim v'$, step 1.4 gives $wv\sim w'v$ and $w'v\sim w'v'$; transitivity gives $wv\sim w'v'$. Thus steps 1.1 through 1.3 prove that $\sim$ is an equivalence relation, and this step proves the congruence claim.

If $[w]=[w']$ and $[v]=[v']$, then $w\sim w'$ and $v\sim v'$, so [L1] gives $wv\sim w'v'$ and therefore $[wv]=[w'v']$; the class product is well-defined.

Literal string concatenation is associative, so for all word classes $([u][v])[w]=[(uv)w]=[u(vw)]=[u]([v][w])$.

The empty word satisfies $\varepsilon w=w=w\varepsilon$, so $[\varepsilon][w]=[w]=[w][\varepsilon]$.

For $w=a_1\cdots a_n$, put $w^*=a_n^{-1}\cdots a_1^{-1}$; successive cancellations from the central seam carry both $ww^*$ and $w^*w$ to $\varepsilon$, including when $n=0$, so $[w][w^*]=[\varepsilon]=[w^*][w]$.

The product is well-defined and associative, $[\varepsilon]$ is a two-sided identity, and every $[w]$ has the two-sided inverse $[w^*]$; these are the group requirements in [F1].

For $r\in\mathcal R(X)$, define $\lambda_a(r)$ by deleting the first letter when $r$ begins with $a^{-1}$, and by prepending $a$ otherwise; in the second case the only new seam is not an inverse pair, so the output is reduced, while deletion from a reduced word also leaves a reduced word.

If $r=a^{-1}s$ is reduced, then $s$ does not begin with $a$, so $\lambda_a(r)=s$ and $\lambda_{a^{-1}}(s)=a^{-1}s=r$. If $r$ does not begin with $a^{-1}$, then $\lambda_a(r)=ar$ begins with $a$, so $\lambda_{a^{-1}}(ar)=r$. Thus $\lambda_{a^{-1}}\circ\lambda_a=\operatorname{id}$, and replacing $a$ by $a^{-1}$ gives $\lambda_a\circ\lambda_{a^{-1}}=\operatorname{id}$.

Hence each $\lambda_a$ is a bijection of $\mathcal R(X)$, so it is a permutation by [F2], and $\lambda_{a^{-1}}=\lambda_a^{-1}$.

For a word $w=a_1\cdots a_n$, construct $\Lambda_w=\lambda_{a_1}\circ\cdots\circ\lambda_{a_n}$, with the empty composite equal to the identity. Composition acts from right to left. If the suffix $a_{k+1}\cdots a_n$ of a reduced word has already been obtained from $\varepsilon$, then it does not begin with $a_k^{-1}$, so $\lambda_{a_k}$ prepends $a_k$. Induction on the suffix length using [L1] therefore gives $\Lambda_r(\varepsilon)=r$ for every reduced $r$, including $r=\varepsilon$.

Inserting or deleting an adjacent pair $aa^{-1}$ inserts or deletes the adjacent composite $\lambda_a\circ\lambda_{a^{-1}}=\operatorname{id}$ inside $\Lambda_w$; therefore one elementary move leaves $\Lambda_w$ unchanged, and so does any finite sequence of such moves.

The empty word is reduced and freely equivalent to itself, establishing the existence claim for words of length zero.

Assume every word of length $n$ is freely equivalent to a reduced word, and write a word of length $n+1$ as $ua$ with $|u|=n$; by the induction hypothesis, $u\sim r$ for some reduced $r$, so the congruence property of [L3], applied with the one-letter word $a$ on the right, gives $ua\sim ra$.

If reduced words $r$ and $s$ lie in the same class, then $r\sim s$, so [L1] gives $\Lambda_r=\Lambda_s$.

If $r$ is empty or its last letter is not $a^{-1}$, then $ra$ is reduced; otherwise $r=r'a^{-1}$ and one elementary cancellation carries $ra=r'a^{-1}a$ to the reduced word $r'$. Thus every word is freely equivalent to a reduced word.

Applying the equal permutations of step 1.3 to the empty word gives $r=\Lambda_r(\varepsilon)=\Lambda_s(\varepsilon)=s$, because the construction in [L1] recovers every reduced word from $\varepsilon$.

Consequently every class $[w]$ contains at least one reduced representative.

Step 3.1 gives existence and step 2.2 gives uniqueness, so each class contains exactly one reduced word.

Extend $u$ to formal letters by $\widetilde u(x)=u(x)$ and $\widetilde u(x^{-1})=u(x)^{-1}$, and for $w=a_1\cdots a_n$ define $E(w)=\widetilde u(a_1)\cdots\widetilde u(a_n)$, with $E(\varepsilon)=e_G$.

An elementary insertion or cancellation changes this product only by inserting or deleting an adjacent factor $u(x)u(x)^{-1}$ or $u(x)^{-1}u(x)$, which equals $e_G$; hence one elementary move leaves $E(w)$ unchanged.

A finite sequence of elementary moves therefore preserves evaluation, so $\widehat u([w]):=E(w)$ is well-defined on equivalence classes.

For words $w,v$, one has $E(wv)=E(w)E(v)$, so [L1] and [F1] show that $\widehat u$ is a homomorphism; moreover $\widehat u([x])=u(x)$, so it extends $u$.

If $h:F_{\mathrm{word}}(X)\to G$ is any homomorphism with $h([x])=u(x)$, then [F1] gives $h([x^{-1}])=h([x]^{-1})=u(x)^{-1}$. For $w=a_1\cdots a_n$, the class $[w]$ is the ordered product of its one-letter classes, so [F1] forces $h([w])=\widetilde u(a_1)\cdots\widetilde u(a_n)=\widehat u([w])$; hence $h=\widehat u$.

The homomorphism of step 4.1 exists for every $G$ and $u$, and step 5.1 makes it unique; by [F3], $(F_{\mathrm{word}}(X),i_{\mathrm{word}})$ is a free group on $X$, including when $X$ is empty.

The one-letter words $x$ and $y$ are reduced and lie in the same class, so uniqueness in [L1] gives $x=y$.

Thus $i_{\mathrm{word}}(x)=i_{\mathrm{word}}(y)$ implies $x=y$, which is injectivity; when $X$ is empty the assertion is vacuous.

By [L4] and [L2], both displayed models are free groups on the same set $X$, so [L1] gives a unique compatible isomorphism $\Phi:F_{\mathrm{word}}(X)\to F_{\mathrm{red}}(X)$.

Compatibility gives $\Phi([x])=x$, and preservation of inverses gives $\Phi([x^{-1}])=x^{-1}$. Thus $\Phi([a_1\cdots a_n])$ is the reduced product of the one-letter words $a_1,\ldots,a_n$. It is freely equivalent to $a_1\cdots a_n$ and hence is the unique reduced representative of that class by [L3], including the empty class.

Every permutation of $\{0,1\}$ is determined by the image of $0$: it is either the identity or the transposition $(0\,1)$, and these two maps are distinct; hence $C_2$ is a group with exactly two elements.

Restriction to $B$ maps $\operatorname{Hom}(F,C_2)$ to the function set $C_2^B$, and the free-basis property gives a unique homomorphic extension of every function $B\to C_2$; restriction and extension are inverse maps, so restriction is a bijection $\operatorname{Hom}(F,C_2)\to C_2^B$; [L1] counts $|C_2^B|=2^{|B|}$ and [F1] transports that count along the bijection, giving $|\operatorname{Hom}(F,C_2)|=2^{|B|}$, including $B=\varnothing$.

Applying the same restriction-extension bijection to $C$ gives $|\operatorname{Hom}(F,C_2)|=2^{|C|}$, and therefore $2^{|B|}=2^{|C|}$ as natural numbers.

If $|B|<|C|$, then [L2] lets the equality of step 3.1 be read in $\mathbb R$, and [L3] applied to the base $2>1$ gives $2^{|B|}<2^{|C|}$, contradicting step 3.1; the case $|C|<|B|$ is symmetric, so trichotomy [L4] forces $|B|=|C|$.

Thus any two finite free bases of $F$, including empty bases, have the same cardinality.

The empty product puts the identity in $P$; concatenating two finite products keeps them in $P$; and [L2] shows that the inverse of a product is the reverse product of factors $(gr^\varepsilon g^{-1})^{-1}=gr^{-\varepsilon}g^{-1}$. Thus $P$ is a subgroup of $G$ by [F2].

Each $r\in R$ is the one-factor product $ere^{-1}$, so $R\subseteq P$.

Conversely, the normal subgroup $\langle\!\langle R\rangle\!\rangle_G$ contains every $r_i^{\pm1}$ and, by normality, every conjugate $g_ir_i^{\pm1}g_i^{-1}$; subgroup closure then contains every finite product in $P$, including the empty product, so $P\subseteq\langle\!\langle R\rangle\!\rangle_G$.

For $h\in G$, conjugating a displayed product by $h$ replaces each factor $g_ir_i^{\varepsilon_i}g_i^{-1}$ by $(hg_i)r_i^{\varepsilon_i}(hg_i)^{-1}$; hence $hPh^{-1}\subseteq P$. Applying the same inclusion with $h^{-1}$ and conjugating by $h$ gives the reverse inclusion, so $hPh^{-1}=P$ and [F3] makes $P$ normal.

Since $P$ is a normal subgroup containing $R$, minimality in [L1] gives $\langle\!\langle R\rangle\!\rangle_G\subseteq P$.

The inclusions of steps 3.1 and 1.3 give the displayed equality.