The free group may be constructed formally using van der Waerden's trick, which is not intuitive at all but leads to a definition that is very easy to work with. This page will detail van der Waerden's construction, and will prove that the trick yields a group which has all the right properties to be the free group.

The construction

Write for the set that contains all the freely reduced words over $X \cup X^{- 1}$ (so, for instance, excluding the word $a a^{- 1}$ ). ^[1]

We define the free group $F (X)$ , or $F X$ , on the set $X$ to be a certain subgroup of the symmetric group $S y m (X^{r})$ : namely that which is generated by the following elements, one for each $x \in X \cup X^{- 1}$ :

$ρ_{x} : S y m (X^{r}) \to S y m (X^{r})$ , sending $a_{1} a_{2} \dots a_{n} \mapsto a_{1} a_{2} \dots a_{n} x$ if $a_{n} \neq x^{- 1}$ , and $a_{1} a_{2} \dots a_{n - 1} x^{- 1} \mapsto a_{1} a_{2} \dots a_{n - 1}$ .

$ρ_{x^{- 1}} : S y m (X^{r}) \to S y m (X^{r})$ , sending $a_{1} a_{2} \dots a_{n} \mapsto a_{1} a_{2} \dots a_{n} x^{- 1}$ if $a_{n} \neq x$ , and $a_{1} a_{2} \dots a_{n - 1} x \mapsto a_{1} a_{2} \dots a_{n - 1}$ .

Recall that each $ρ_{x}$ lies in $S y m (X^{r})$ , so each is a bijective function from $X^{r}$ to $X^{r}$ . We specify it by stating what it does to every element of $X^{r}$ (that is, to every freely reduced word over $X$ ).

We first specify what it does to those words which don't end in $x^{- 1}$ : $ρ_{x}$ simply appends an $x$ to such words. We then specify it to the remaining words, those which do end in $x^{- 1}$ : then $ρ_{x}$ just removes the $x^{- 1}$ .

It's easy to check that if $ρ_{x}$ is given a freely-reduced word as input, then it produces a freely-reduced word as output, because the only change to the word is at the end and we make sure to provide a separate definition if $x$ is to be cancelled. Therefore each $ρ_{x}$ is a function $X^{r} \to X^{r}$ .

Then we do it all again for all the inverses $x^{- 1}$ , creating the functions $ρ_{x^{- 1}}$ ; and finally, we add in the identity element, denoted $ρ_{ε}$ , which simply returns its input unchanged.

Notice that the $ρ_{x}$ and $ρ_{x^{- 1}}$ are all indeed bijective (and therefore members of $S y m (X^{r})$ ), because in fact $ρ_{x}$ and $ρ_{x^{- 1}}$ are inverse to each other (each cancelling off what the other did), and a function with an inverse is bijective.

So, we've defined the free group as a certain subgroup of the symmetric group. Remember that the subgroup has as its group operation "function composition"; so $ρ_{x} \cdot ρ_{y} = ρ_{x} \circ ρ_{y}$ , for instance. We will write $ρ_{x} ρ_{y}$ for this, omitting the group operation.

Something key to notice is that if we apply $ρ_{a_{n}} ρ_{a_{n - 1}} \dots ρ_{a_{1}}$ to the empty word $ε$ , we get $ρ_{a_{n}} ρ_{a_{n - 1}} \dots ρ_{a_{1}} (ε) = ρ_{a_{n}} ρ_{a_{n - 1}} \dots ρ_{a_{3}} (ρ_{a_{2}} (a_{1})) = ρ_{a_{n} a_{n - 1} \dots a_{3}} (a_{1} a_{2}) = \dots = a_{1} a_{2} \dots a_{n}$ if $a_{1} a_{2} \dots a_{n}$ is a freely reduced word. (Indeed, if the word is freely reduced then none of the successive $ρ_{a_{i}}, ρ_{a_{i + 1}}$ can have cancelled each other's effect out, so every application of a $ρ_{a_{i}}$ must be appending a letter.) Hence we might hope to have captured the freely reduced words in our subgroup.

The formal definition is the same as the intuitive definition

We'll show that there is a bijection between the free group and the set of reduced words, by "converting" each reduced word into a corresponding member of the free group.

Take a reduced word, $w = a_{1} a_{2} \dots a_{n}$ , and produce the member of the free group (that is, the function) $ρ_{a_{1}} ρ_{a_{2}} \dots ρ_{a_{n}}$ . ^[2] This really does produce a member of the free group (i.e. of the subgroup of the symmetry group), because each $a_{i}$ is an element of $X \cup X^{- 1}$ and we have already specified how to make $ρ_{a_{i}}$ from such an element.

Now, we claim that in fact this map is injective: that is, we can't take two words $a_{1} a_{2} \dots a_{n}$ and $b_{1} b_{2} \dots b_{m}$ and produce the same member of the free group. (That is, we show that $ρ_{a_{1}} ρ_{a_{2}} \dots ρ_{a_{n}} = ρ_{b_{1}} ρ_{b_{2}} \dots ρ_{b_{m}}$ implies $a_{1} \dots a_{n} = b_{1} \dots b_{m}$ .) Indeed, if the two functions ("elements of the free group") are equal, then they must in particular do the same thing when they are applied to the empty word $ε$ . But by the "key notice" above, when we evaluate $ρ_{a_{1}} ρ_{a_{2}} \dots ρ_{a_{n}}$ at the empty word, we get $a_{n} a_{n - 1} \dots a_{2} a_{1}$ ; and when we evaluate $ρ_{b_{1}} ρ_{b_{2}} \dots ρ_{b_{m}}$ at the empty word, we get $b_{m} b_{m - 1} \dots b_{2} b_{1}$ ; so the two words must be equal after all.

we've got this backwards

Finally, the map is surjective: we can make any member of the free group by "converting the appropriate reduced word into a function". Indeed, the free group is generated by the $ρ_{x}$ and $ρ_{x^{- 1}}$ for $x \in X$ , so every element is some $ρ_{x_{1}} \dots ρ_{x_{n}}$ for some selection of $x_{1}, \dots, x_{n} \in X \cup X^{- 1}$ . Note that $x_{1} \dots x_{n}$ need not necessarily be freely reduced as a word at the moment; but if it is indeed not freely reduced, so some $x_{i}, x_{i + 1}$ cancel each other out, then removing that pair completely doesn't change the function $ρ_{x_{1}} \dots ρ_{x_{n}}$ . For example, $ρ_{x_{1}} ρ_{x_{1}^{- 1}} ρ_{x_{2}} = ρ_{x_{2}}$ . Hence the process of "performing one step of a free reduction" (i.e. removing a cancelling pair) doesn't change the member of the free group as a function; and since each such removal makes the word shorter, it must eventually terminate. It remains to show that it doesn't matter in what order we remove the cancelling pairs; but that is immediate because we've already shown that our "conversion" process is injective: we started with a member of the free group, so if it corresponds to a freely reduced word then it corresponds to a unique freely reduced word. Since we've just shown that it does indeed correspond to a freely reduced word (by repeatedly removing cancelling pairs), we are done.

The above shows that the free group can be considered just to be the set of reduced words.

^{^︎}
We use the superscript $r$ to denote "reduced".
^{^︎}
Recall that the group operation here is composition of functions, so this is actually the function $ρ_{a_{1}} \circ ρ_{a_{2}} \circ \dots \circ ρ_{a_{n}}$ .