# Different ways of constructing the free group over a set.

This could be too broad if we're not careful. I'm sorry if it ends up that way.

Let's put together a list of different constructions of the free group $F_X$ over a given set $X$.

It seems to be one of those things a lot of people know about (and use implicitly) but whose constructions can be so tedious, it's hard to get hold of at first. The main problem, as Lee Mosher reminds us, seems to be associativity.

The Wikipedia page (linked to above) goes some way into listing some useful perspectives. I'm impressed by this intuitive summary from Wolfram:

A group is called a free group if no relation exists between its group generators other than the relationship between an element and its inverse required as one of the defining properties of a group.

But this is not exactly a construction nor is it strictly the free group over a set.

Here's a brief list of what I have so far:

This starts with the "standard" construction using finite strings over $\mathcal{X}=X\cup X'$ then asks for an opinion on quotienting by some equivalence relation.

The free group is constructed as the left adjoint of the composition of certain forgetful functors. This one is interesting in that it goes via the category InvMon of monoids with involutions as objects and involution-preserving homomorphims as morphisms.

Martin Brandenburg also gives quite a concise one in the comments there, so I invite him to elaborate on that here :)

The above list is not at all exhaustive (of what I know) and there's bound to be some overlap. Personally I would be interested to see explicit use of Universal Algebra, Semigroup Theory, and Category Theory. The reason for the latter should be clear from the above; as for the first two, see

Feel free to give more details on those already listed here.

• I'm a big fan of Massey's presentation in "Algebraic Topology: An Introduction" (or something like that); he starts from the "words with cancelling rules" approach, points out that you end up saying a lot of not-quite-sensible things, and then shows how to construct things based on universal properties, with the "words" model as motivation throughout. – John Hughes Jul 3 '14 at 12:53
• One should never define the free group as a set of reduced words. This is conceptually wrong and requires tedious calculations to verify the group structure ... the free group (or free object of any type) is defined via its universal property. Existence is a simple application of Freyd's Adjoint Functor Theorem. Explicitly, we have $F(S) = \langle \mathrm{im}(\phi) \rangle$ with $\phi : S \to \prod_{i : S \to U(G) \text{ generates} G} G$. The structure of words can be derived from the universal property. See also math.stackexchange.com/questions/487628 – Martin Brandenburg Jul 3 '14 at 20:42
• @MartinBrandenburg: "should never" might be a bit strong. What I like about this question is that different definitions are useful for different purposes. The modern geometric theory of free groups and their automorphism and outer automorphism groups is founded on a good intuitive understanding of reduced words, starting with the bounded cancellation lemma and Cooper's paper "Automorphisms of free groups have finitely generated fixed point sets". Part of that is what goes into my answer below, in which there are no tedious calculations, just geometry. – Lee Mosher Jul 3 '14 at 23:32
• I might put together a detailed answer from the perspective of Universal Algebra, time permitting; I need to brush-up on it. – Shaun Jul 6 '14 at 19:11
• Using Lawvere theories might be illustrative. Have a look at the "Free $T$-algebras and underlying sets" section of the link provided. But would that give a construction, @MartinBrandenburg? :) – Shaun Jul 7 '14 at 9:52

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.

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.

Recently I learned a new (to me) way of proving the associativity of multiplication of reduced words from this AMS Monthly article

An Elementary Treatment of the Construction of the Free Product of Groups http://www.jstor.org/stable/10.4169/amer.math.monthly.122.7.690

James E. McClure and Alec McGail

The American Mathematical Monthly, Vol. 122, No. 7 (August–September 2015), pp. 690-692

The article addresses free products of groups, but of course the technique applies to free groups as well.

They show that every word has a unique reduced form in a direct and elementary way. Then the associativity follows immediately from the (easy) associativity in the free monoid.

Here is the proof. I will use Charles Rezk's notation, so the words are finite sequences of letters, which are elements of $S \cup S^*$. Suppose a word $w$ has two sequences of reductions $$w \to w_1 \to \cdots \to w_m,$$ $$w \to w'_1 \to \cdots \to w'_n,$$ where each step $w_i \to w_{i+1}$ is ''cancellation of a pair of some adjacent letters $a$, $a^*$'' and the final word $w_m$ is reduced (and similarly for the $w'_j$). We call $w_{i+1}$ an immediate descendent of $w_i$, and $w_j$ a descendent of $w_i$ if $i<j$. If $w_i = w'_j$ for any $i$ and $j$, then we are done by induction on the word length. So assume that $w_1 \neq w'_1$. There are two cases.

1. We have $$w = (u_1, a, a^*, u_2, b, b^*, u_3),$$ where the $u_i$ are subwords and $a, b$ are letters, and $$w_1 = (u_1, u_2, b, b^*, u_3),$$ $$w'_1 = (u_1, a, a^*, u_2, u_3).$$ Then $$\tilde{w} = (u_1, u_2, u_3)$$ is a common (immediate) descendent of $w_1$ and $w'_1$.
2. We have $$w = (u_1, a, a^*, a, u_2),$$ where the $u_i$ are subwords and $a$ is a letter, and $$w_1 = (u_1, a, u_2) = w'_1.$$

In both cases, we are done by induction on the word length.

The following is what I have after running through "A Course in Universal Algebra" by Burris et al. using the description of a group given here. It's just a sketch. Consult the text wherever necessary.

We work in the type $\mathcal{G}=\{\cdot, \sim, e\}$, where $\cdot\in\mathcal{G}_2$ is a binary operation, $\sim\in\mathcal{G}_1$ is a unary operation, and $e\in\mathcal{G}_0$ is a nullary operation, all subject to \begin{align} x\cdot (y\cdot z)&=(x\cdot y)\cdot z,\tag{associativity} \\ e\cdot x&=x=x\cdot e,\text{ and}\tag{identity}\\ x\cdot(\sim x)&=e=(\sim x)\cdot x.\tag{inverses}\end{align}

Definition 1: Let $X$ be a set of (distinct) variables. The set $T(X)$ of terms of type $\mathcal{G}$ over $X$ is the smallest set s.t.

• $X\cup\{e\}\subseteq T(X)$ and
• If $p_1, \dots , p_n\in T(X)$ and $f\in\mathcal{G}_n$, then the string $f(p_1, \dots , p_n)\in T(X)$

Definition 2: Given a group $\mathbb{G}=\langle G, \{\cdot^{\mathbb{G}}, \sim^{\mathbb{G}}, e^{\mathbb{G}}\}\rangle$ (i.e., an algebra of type $\mathcal{G}$) and an $n$-ary term $p(x_1, \dots , x_n)$ of type $\mathcal{G}$ over $X=\{x_i\mid i\in I\}$, some $I$, define the term function of $\mathbb{G}$ corresponding to $p$, denoted $p^{\mathbb{G}}: G^n\to G$, like so.

• If $p$ is a variable $x_i$, then $p^{\mathbb{G}}(a_1, \dots , a_n)=a_i.$
• If $p$ is of the form $p_1(a_1, \dots , a_n)\cdot p_2(a_1, \dots , a_n)$, $\sim p_1(a_1, \dots , a_n)$, or $e$, then $p^{\mathbb{G}}(a_1, \dots , a_n)$ is $p_1^{\mathbb{G}}(a_1, \dots , a_n)\cdot p_2^{\mathbb{G}}(a_1, \dots , a_n)$, $\sim p_1^{\mathbb{G}}(a_1, \dots , a_n)$, or $e^{\mathbb{G}}$.
• If $p=f\in\mathcal{G}$, then $p^{\mathbb{G}}=f^{\mathbb{G}}$.

Definition 3: The term algebra of type $\mathcal{G}$ over $X$, denoted $\mathbb{T}(X)$, has as its underlying set $T(X)$ and has the fundamental operations $$f^{\mathbb{T}(X)}:(p_1, \dots , p_n)\mapsto f(p_1, \dots , p_n)$$ for $f\in\mathcal{G}_n$ and $p_i\in T(X)$ for all $i\in \overline{1, n}$. (NB: Since $\mathcal{G}_0\neq\emptyset$, $\mathbb{T}(\emptyset)$ exists.)

The free group $F_X$ over $X$ is exactly $\mathbb{T}(X)$ (up to isomorphism).

See Example 1, p. 74, Ibid.

Please do correct me if I'm wrong.

• In hindsight, Definition 2 seems unnecessary here; it's helpful when reading the section of the book though. – Shaun Jul 7 '14 at 14:04
• No, Definition 2 is necessary. – Shaun Aug 8 '18 at 22:21