Different ways of constructing the free group over a set.

Solution 1:

It's just not that hard to construct the free group via reduced words. The trick is to prove the universal property before proving associativity. The argument is standard (e.g., it is in Dummit & Foote, Ch.6). Who came up with it first?

Start with a set of symbols $S$. Extend to a set $S\amalg S^*$ of letters, equipped with an involution $a\mapsto a^*$ which switches the summands. A reduced word is a finite sequence $x=(x_1,\dots,x_n)$ of letters such that $x_j\neq x_{j+1}^*$ for all $j$. Define a binary operation $x\cdot y$ on the set $F$ of reduced words: $$ (x_1,\dots,x_m)\cdot (y_1,\dots,y_n) := (x_1,\dots, x_{m-k},y_{k+1},\dots,y_n), $$ where $k$ is the unique integer such that $x_{m-k}\neq y_{k+1}^*$ but $x_{m-j}=y_{j+1}^*$ for $j<k$ (with the obvious modifications when $k=\min(m,n)$, giving $(y_{m+1},\dots,y_n)$ or $(x_1,\dots,x_{m-n})$ or $()$ as the case may be).

The following is entirely straightforward to prove:

• Every function $\phi\colon S\to G$ to a group $G$ extends uniquely to a function $\Phi\colon F\to G$ such that:

  1. $\Phi((s))=\phi(s)$ for each symbol $s\in S$, and

  2. $\Phi(x\cdot y)=\Phi(x)\Phi(y)$ for any reduced words $x,y\in F$.

Note: 2. implies that $\Phi$ must send the empty word to the identity element and that $\Phi((s^*))=\phi(s)^{-1}$, since $()=()\cdot ()=(s)\cdot (s^*)=(s^*)\cdot (s)$ in $F$.

The construction of $\Phi$ is simply: extend $\phi$ to $S\amalg S^*\to G$ by $\phi(s^*):=\phi(s)^{-1}$, and define $\Phi(x):=\phi(x_1)\cdots \phi(x_n)$.

Now let $G=$ the permutation group of $F$. For each letter $a\in S\amalg S^*$, let $\lambda_a\colon F\to F$ be the left-multiplication function $$ \lambda_a(x) := (a)\cdot x. $$ A direct calculation using the definition of the binary operation shows that the functions $\lambda_a$ and $\lambda_{a^*}$ are inverse to each other, so $\lambda_a\in G$. Let $\phi\colon S\to G$ be $\phi(s):=\lambda_s$, and let $\Phi\colon F\to G$ be the unique multiplicative extension as above. From the construction of $\Phi$ calculate that the evaluation of the permutation $\Phi(x)\in G$ at the empty word is exactly $x$, so $\Phi$ is injective. From this we can read off that the operation on $F$ is associative, since multiplication in $G$ is associative; the other group axioms for $F$ are obvious.

Solution 2:

The simplest definition of the elements of a free group is the one using reduced words; you found it in Ledermann. This also leads to a reasonably simple definition of the multiplication. But this just pushes the problem somewhere else, namely in verification of the associative law (once the associative law is proved, it then follows that each word is equivalent to a unique reduced word).

Personally I like a topological proof of the associative law; this will be in my book on $Out(F_n)$. One first constructs the tree $T$ whose edges are oriented and labelled by the elements of $X$, such that for each vertex $v$ and each $x \in X$ there is a unique incoming and a unique outgoing edge at $v$ labelled with $x$. After the fact one notices that this tree is the universal covering space of the wedge of circles with one circle for each generator; but you don't need the theory of universal covering spaces to construct this tree, you just construct it inductively by constructing the radius $n$ neighborhood of a base vertex, verifying as you go along that the construction satisfies the tree axiom, namely that it is connected and contains no circles. The associative law in the free group then comes down to the fact that the operation of concatenating paths and straightening the result to eliminate backtracking is an associative operation, which follows from the simple observation that two points in a tree are connected by a unique path without backtracking.