Free Groups and Presentations: Examples and Counterexamples

Delete the initial adjacent pair $x{x}^{-1}$ to obtain $y{y}^{-1}x$.

Delete the initial adjacent pair $y{y}^{-1}$ in the resulting word to obtain $x$.

The one-letter word $x$ has no adjacent pair and is reduced, while steps 1.1 and 2.1 are a finite cancellation sequence; hence the two words are freely equivalent.

On the empty alphabet, the empty word is the only finite word and hence the only reduced word; by [L1], $F_{\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{d}}(\mathrm{\varnothing })$ has the single class $[\epsilon ]$.

That class is the identity, so $F_{\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{d}}(\mathrm{\varnothing })$ has exactly one element.

By [L3] this model is a free group on $\mathrm{\varnothing }$, so [L2] makes every free group on $\mathrm{\varnothing }$ isomorphic to it; an isomorphism is a bijection, so every free group on $\mathrm{\varnothing }$ has exactly one element and is trivial.

A reduced word on $\{x,x^{-1}\}$ cannot contain both letters, since a change from one to the other creates an adjacent inverse pair; hence every reduced word is uniquely $x^n$ for $n\ge 0$ or $x^{-n}$ for $n\ge 1$, with the empty word corresponding to exponent $0$.

Thus $[x]$ generates the group, and no positive power $[x{]}^n$ is the identity because its reduced representative $x^n$ is nonempty; therefore $[x]$ has infinite order.

Since $[x]$ generates by step 2.1, [L5] makes every element of $F_{\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{d}}(\{x\})$ equal to $[x{]}^k$ for some $k\in \mathbb{Z}$, and [L2] applied to the infinite-order element $[x]$ makes that exponent unique; so $\theta ([x{]}^k):=k$ is a well-defined injection, it is surjective because $k=\theta ([x{]}^k)$, and [L6] makes it a homomorphism. Construct $\theta :F_{\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{d}}(\{x\})\to (\mathbb{Z},+)$ as this isomorphism, which carries $[x]$ to $1$.

By [L4] the word-quotient model is a free group on $X$, so for any free group $(F,i)$ on $X$ the isomorphism $\varphi :F\to F_{\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{d}}(\{x\})$ of [L3] satisfies $\varphi (i(x))=[x]$; then $\theta \circ \varphi$ is an isomorphism $F\to (\mathbb{Z},+)$ carrying $i(x)$ to $1$.

The words $xy$ and $yx$ are reduced, and they are literally different because $x\mathrm{\ne }y$.

Uniqueness in [L1] makes their word classes different, so $[x][y]\mathrm{\ne }[y][x]$ in the word-quotient free group.

By [L2] and [L3], every free group on $X$ is isomorphic to that model by an isomorphism fixing the generators, so the two chosen basis elements do not commute and the group is not abelian.

In the additive group $\mathbb{Z}\mathrm{/}n$, the $n$-fold multiple of $[1{]}_n$ is $[n{]}_n=[0{]}_n$, so [L3] constructs a homomorphism $\pi :P\to \mathbb{Z}\mathrm{/}n$ with $\pi (a)=[1{]}_n$.

Every word on one generator represents $a^k$ for some $k\in \mathbb{Z}$; write $k=qn+r$ by [L1]. Since $a^n=e$ in $P$, [L4] gives $a^k=(a^n{)}^q{a}^r=a^r$ with $0\le r<n$.

The image of $a^r$ is $[r{]}_n$, and [L2] makes these images distinct and exhaustive for $0\le r<n$; combined with step 1.2, this proves that $\pi$ is injective and surjective.

Hence $\pi$ is the claimed isomorphism; when $n=1$, the sole normal form is $a^0=e$ and the sole residue is $[0{]}_1$.

Direct substitution on $\mathbb{Z}\mathrm{/}n$ gives ${\rho }^n=\mathrm{id}$, ${\sigma }^2=\mathrm{id}$, and $\sigma \rho {\sigma }^{-1}\rho =\mathrm{id}$ because $\sigma \rho \sigma (k)=k-1$; thus the displayed relators hold.

In $P$, the relators give $s^{-1}=s$, $sr=r^{-1}s$, $r^n=e$, and $s^2=e$; moving every $s$ to the right and reducing exponents therefore writes every element as $r^i{s}^{\epsilon }$ with $0\le i<n$ and $\epsilon \in \{0,1\}$.

The permutations ${\rho }^i$ are distinct by their values ${\rho }^i(0)=i$, and the permutations ${\rho }^i\sigma$ are likewise distinct; the two families are disjoint because equality would first force the same $i$ from the value at $0$ and then force $i+1=i-1$ in $\mathbb{Z}\mathrm{/}n$ from the value at $1$, impossible for $n\ge 3$. Step 1.1 gives the same relations among $\rho$ and $\sigma$, so the set $\{{\rho }^i{\sigma }^{\epsilon }:0\le i<n,\epsilon \in \{0,1\}\}$ is closed under products and inverses and contains $\rho$ and $\sigma$; being a subgroup containing $\{\rho ,\sigma \}$, it equals $D_n$ by the minimality in [F1]. Hence [L1] and [L3] give exactly $2n$ elements of $D_n$.

By [L2], construct a homomorphism from the displayed presentation $P$ to $D_n$, sending $r$ to $\rho$ and $s$ to $\sigma$; its image is a subgroup containing $\rho$ and $\sigma$, so [F1] makes it all of $D_n$ and the homomorphism surjective.

Step 1.2 gives at most the same $2n$ normal forms in $P$, and step 2.1 shows that their images under the surjection of step 2.2 are all distinct; therefore that homomorphism is bijective and hence an isomorphism.

The target is the subgroup $D_n=⟨\{\rho ,\sigma \}⟩$ of $\mathrm{Sym}(\mathbb{Z}\mathrm{/}n)$ specified in the Example, which step 2.1 shows has order $2n$; so the displayed isomorphism holds with the stated conventions and boundary $n\ge 3$.

Sending $a$ to $(1,0)$ and $b$ to $(0,1)$ kills the two square relators and the commutator in the abelian direct product, so [L1] constructs a homomorphism $\pi :P\to (\mathbb{Z}\mathrm{/}2)\times (\mathbb{Z}\mathrm{/}2)$.

The commutator relation gives $ab=ba$, and the square relations reduce both exponents modulo $2$, so every element of $P$ has one of the forms $e,a,b,ab$.

Their images are $(0,0),(1,0),(0,1),(1,1)$, which are distinct and exhaustive by [L2]; together with step 1.2, this makes $\pi$ bijective.

Hence $P$ is isomorphic to $(\mathbb{Z}\mathrm{/}2)\times (\mathbb{Z}\mathrm{/}2)$, the Klein four-group.

Sending $a$ to $(1,0)$ and $b$ to $(0,1)$ kills the commutator in the abelian direct product, so [L1] constructs a homomorphism $\pi :P\to \mathbb{Z}\times \mathbb{Z}$.

The relator gives $ab=ba$, so group algebra and [L3] move all powers of $a$ before all powers of $b$ and write every element of $P$ as $a^m{b}^n$ for integers $m,n$.

The map $\pi$ sends $a^m{b}^n$ to $(m,n)$ by [L2], so it is surjective and step 1.2 shows that its kernel is trivial: an element mapping to $(0,0)$ has the form $a^0{b}^0=e$.

Therefore $\pi$ is the claimed isomorphism $P\cong \mathbb{Z}\times \mathbb{Z}$.

Direct permutation computation gives $s^2=t^2=\mathrm{id}$ and $(st{)}^3=\mathrm{id}$, so [L2] constructs a homomorphism $\pi :P\to \mathrm{Sym}(A)$.

After cancelling $s^2$ and $t^2$, every word alternates. The relation $(st{)}^3=e$ gives $stst=ts$ and hence $tst=sts$ after multiplying on the left by $s$; replacing the first three letters of any alternating word of length at least four by the other side creates an adjacent equal pair and shortens the word.

Their images are respectively $\mathrm{id},(01),(12),(012),(021),(02)$, so they are distinct; [L1] gives $\mathrm{\mid }\mathrm{Sym}(A)\mathrm{\mid }=3!=6$, and these images exhaust it.

Repeating step 1.2 leaves one of $e,s,t,st,ts,sts$, since the two alternating words of length three are equal.

Step 2.1 gives at most six elements in $P$, while step 1.3 gives six distinct images under $\pi$; hence $\pi$ is bijective and is the claimed isomorphism.

The relation $ab=e$ gives $b=a^{-1}$ by [F2], and therefore $ba=a^{-1}a=e$ in $G$.

The word $ba$ has no adjacent inverse pair and contains neither the relator $ab$ nor its inverse $b^{-1}{a}^{-1}$ as a contiguous subword.

Thus $ba$ represents the identity by step 1.1 but is stuck and nonempty under the stated procedure by step 1.2, refuting the claim.

The relator $ab{a}^{-1}{b}^{-1}=e$ gives $ab=ba$; hence [L2] gives $a^2{b}^2=(ab{)}^2$, and $a^2{b}^2{a}^{-2}{b}^{-2}=a^2{b}^2(a^2{b}^2{)}^{-1}=e$.

The eight-letter word $a,a,b,b,a^{-1},a^{-1},b^{-1},b^{-1}$ has no adjacent inverse pair.

Its five length-four windows are $aabb$, $abb{a}^{-1}$, $bb{a}^{-1}{a}^{-1}$, $b{a}^{-1}{a}^{-1}{b}^{-1}$, and $a^{-1}{a}^{-1}{b}^{-1}{b}^{-1}$; none is the relator $ab{a}^{-1}{b}^{-1}$ or its inverse $ba{b}^{-1}{a}^{-1}$.

The nonempty identity word is therefore stuck under the delete-only procedure; since its first move in any nonconstant relator-rewriting path cannot be a cancellation or deletion, such a path must begin with an insertion and increase the length.

The relations $ab=e$ and $aba=e$ give $a=(ab)a=e$ and then $b=e$, so every word represents the identity in $G$.

Deleting the occurrence of the relator $aba$ from the whole word $aba$ gives the empty word.

Deleting the prefix $ab$ gives the one-letter word $a$, which has no inverse pair and contains none of $ab$, $aba$, $b^{-1}{a}^{-1}$, or $a^{-1}{b}^{-1}{a}^{-1}$; hence it is stuck.

The two allowed first deletions end at different terminal strings, $\epsilon$ and $a$, even though step 1.1 shows that both represent the same group element; therefore the procedure is order-dependent.