Skip to main content

Section 1.2 The free group.

Let \(X\) be a set. We will call \(X\) an alphabet and we will call its elements symbols. For each symbol \(x \in X\) take a formal inverse \(x^{-1}\) and we denote:

\begin{equation*} X^{\pm 1} = X \cup \{x^{-1} : x \in X\}. \end{equation*}

We further adopt the convention that \(\left(x^{-1}\right)^{-1} = x\text{.}\) A word in \(X^{\pm 1}\) is a string of symbols

\begin{equation*} w(X) = x_1x_2\cdots x_n \end{equation*}

where each symbol \(x_i \in X^{\pm 1}\text{.}\) In the situation where alphabet is clear we will simply write \(w\) instead of \(w(X)\text{.}\)

So, for example, if \(X = \{a,b,c\}\) then \(X^{\pm 1} = \{a, a^{-1}, b, b^{-1},c , c^{-1}\}\) and the string

\begin{equation*} abbac^{-1}b^{-1}ba^{-1} \end{equation*}

is a word in \(X^{\pm 1}\text{.}\)

Given two words \(w_1,w_2\) in some alphabet \(X\text{,}\) we denote their concatenation by \(w_1\ast w_2\text{.}\) For example if

\begin{equation*} w_1 = ab \text{ and } w_2 = ba, \end{equation*}

then \(w_1\ast w_2 = abba\text{.}\)

We can view concatenation as an associative product, and can view words as long products of single letter words. Given a word \(w\) we will say that \(u\) is a subword of \(w\) if there are words \(w',w''\text{,}\) which may be empty, such that

\begin{equation*} w = w'\ast u \ast w''. \end{equation*}

We will now define an equivalence relation on the set of words in \(X^{\pm 1}\) generated by rewriting rules.

Definition 1.2.1.

An elementary cancellation in a word \(w\) is the operation of deleting a subword of the form \(xx^{-1}\) where \(x \in X^{\pm 1}\text{,}\) i.e.

\begin{equation*} w = w'\ast xx^{-1} \ast w'' \stackrel{c}{\to} w'\ast w''\text{.} \end{equation*}

If \(u\) is obtained from \(w\) by an elementary cancellation, i.e. \(w \stackrel{c}{\to}u\text{,}\) then we say that \(w\) is obtained from \(u\) by an elementary insertion.

We the identity operation \(w \to w\) to simultaneously be a trivial cancellation and a trivial insertion.

So, for example, we have:

\begin{equation*} bca^{-1}ac \stackrel{c}{\to} bcc. \end{equation*}

Is an elementary cancellation.

We now define an equivalence relation \(\stackrel{c}{\sim}\) on the set of words in \(X^{\pm 1}\) as follows:

  1. For each word we declare \(w \stackrel c \sim w\text{.}\) (Reflexivity)
  2. We declare \(w \stackrel c \sim u\) if \(w\) can be brought to \(u\) by a sequence of elementary cancellations and elementary insertions.

We can now define the free group \(F(X)\) on the alphabet \(X\text{.}\)

  1. The set underlying \(F(X)\) is the set of all words strings in the symbols \(X^{\pm 1}\text{,}\) modulo the equicalence relation \(\stackrel c \sim\text{.}\)
  2. The multiplication is concatenation of words.
  3. The identity element \(1 = 1_{F(X)}\) is the empty word.

Although we have a definition of \(F(X)\) an outstanding problem remains: although concatenation is well-defined for words, it is not immediately well-defined for equivalence classes. In particular we must exclude the following possibility

\begin{equation*} w \stackrel c \sim w', u \stackrel c \sim u', \textrm{ but } w*u {\stackrel{c}{\not\sim}} w'*u', \end{equation*}

otherwise we will not have proved that the structure \(F(X)\) we defined is actually a group.

Furthermore, working with a set modulo an equivalence relation is problematic: given two words, it's not immediately clear whether they're equal or not. Consider an analogy with the set \(\QQ\) of fractions. We can consider fractions to be formal ratios of integers, but two different formal ratios, such as \(\frac 2 4 \text{ and } \frac 4 8\text{,}\) can be equal. \(\QQ\) is therefore best thought of the set of ratios of formal ratios of integers modulo some equivalence relation. Furthermore every equivalence class of ratios has a reduced element.. In \(\QQ\) a ratio is reduced if the numerator and denominator are relatively prime.

To this end we have the following. A word \(w(X)\) in \(X^{\pm 1}\) is reduced if it has no subwords of the form \(x^{\pm 1}x^{\mp 1}\) for some \(x \in X.\) Now given a non-reduced word, it is possible to remove a subword of the form \(x^{\pm 1}x^{\mp 1}\) via an elementary cancellation. Because words have finite length and elementary cancellations reduce length, every word can be brought to a reduced form after finitely many elementary cancellations. The outstanding issue here is that perhaps different sequences of elementary cancellations can give rise to different reduced words. Thankfully we have the following result.

A restatement of this theorem is that elementary reductions form a confluent rewriting system.

Denote by \(\overline{w}\) the unique reduced form of \(w\). We can now prove the following.

The first item is immediate from Theorem 1.2.2. For the second item, let \(w \stackrel c \sim w', u \stackrel c \sim u'\text{.}\) Then \(\overline{w'} = \overline{w}, \overline{u'} = \overline{u}\text{.}\) Now Theorem 1.2.2 implies that
\begin{equation*} \overline{\overline{w}*\overline{u}} = \overline{w*u}, \end{equation*}
since the left hand side just means "first perform cancellations within the subwords \(w\) and \(u\)" and the Theorem implies that the order of cancellations doesn't matter. We therefore have
\begin{equation*} \overline{w*u} = \overline{\overline{w}*\overline{u}} = \overline{\overline{w'}*\overline{u'}} = \overline{w'*u'}. \end{equation*}
So \(w*u =_{F(X)}w'*u'. \)

Exercises 1.2.1 Exercises

The purpose of these exercises, besides proving a crucial fact about free groups, is to get the reader to write arguments using words and using the technique of induction on word length.

1.

Prove the diamond lemma:

Figure 1.2.5. The diamond lemma

Hint: There are two cases to consider: whether or not the cancelled subwords in \(w\) overlap. Be thoughtful with your notation and use of subscripts.

2.

Use the diamond lemma to prove Theorem 1.2.2

Hint: Use a peak reduction argument. Suppose that \(w\) and \(w'\) were distinct reduced words with \(w\stackrel c \sim w'\text{.}\) Then there is a sequence

\begin{equation*} w = w_0 \stackrel x \leftrightarrow w_1 \stackrel c \leftrightarrow \cdots \stackrel c \leftrightarrow w_n =w' \end{equation*}

where each \(\stackrel c \leftrightarrow\) is either an elementary insertion or deletion. In particular there exists a sequence of minimal total word length i.e.

\begin{equation*} \sum_{i=0}^n |w_i|, \end{equation*}

where \(|w_i|\) is the length of a word, is minimal among all such sequences. Consider an intermediate word of maximal length and the diamond lemma.

3.
Finish the showing that \(F(X)\) is a group by showing that every element has an inverse.