•

The formal definition is the same as the intuitive definition

Main

Formal definition

Universal property

Formal definition of the free group

Discussion3

Written by Patrick Stevens last updated 5th Aug 2016

Title

Tab title

Tab subtitle

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

X^{r}

for the set that contains all the freely reduced words over (so, for instance, excluding the word ). ^[1]

We define the free group

F (X)

, or , on the set to be a certain subgroup of the symmetric group : namely that which is generated by the following elements, one for each :

$ρ_{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 , so each is a bijective function from to . We specify it by stating what it does to every element of (that is, to every freely reduced word over ).

We first specify what it does to those words which don't end in

x^{- 1}

: simply appends an to such words. We then specify it to the remaining words, those which do end in : then just removes the .

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 is to be cancelled. Therefore each is a function .

Then we do it all again for all the inverses

x^{- 1}

, creating the functions ; and finally, we add in the identity element, denoted , which simply returns its input unchanged.

Notice that the

ρ_{x}

and are all indeed bijective (and therefore members of ), because in fact and 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 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_{1} a_{2} \dots a_{n}

is a freely reduced word. (Indeed, if the word is freely reduced then none of the successive can have cancelled each other's effect out, so every application of a 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) . ^[2] This really does produce a member of the free group (i.e. of the subgroup of the symmetry group), because each is an element of and we have already specified how to make 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 and produce the same member of the free group. (That is, we show that implies .) 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 at the empty word, we get ; and when we evaluate at the empty word, we get ; so the two words must be equal after all.

Todo

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 for , so every element is some for some selection of . Note that need not necessarily be freely reduced as a word at the moment; but if it is indeed not freely reduced, so some cancel each other out, then removing that pair completely doesn't change the function . For example, . 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.

Summaries

You can edit summaries by clicking on them, reorder them by dragging, or add a new one (up to 3). By default you should avoid creating more than one summary unless the subject matter benefits substantially from multiple kinds of explanation.

Summary

Tab title

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.

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}}$ .

Parents:

Free group