Words Over a Set

Definition: Let $A = \{ a, b, ... \}$ be a nonempty set. The Inverse Set of $A$ is the set $A^{-} = \{ a^{-1}, b^{-1}, ... \}$. A Word over $A \cup A^{-}$ is a finite sequence $w$ of elements in $A \cup A^{-1}$. The Empty Word is the empty sequence $()$.

We are not assuming a group context here. If $A$ is any nonempty set, it is a set of symbols, and $A^{-}$ is also a set of symbols.

For example, if $A = \{ a, b, c, d, e \}$ then an example of a word over $A \cup A^{-}$ is:

(1)

\begin{align} \quad w = aba^{-1}cd^{-1}a^{-1}eb^2 \end{align}

Definition: Let $A$ be a nonempty set. If $w$ is a word over $A \cup A^{-}$ then the Length of $w$ denoted $|w|$ is the number of elements in the sequence.

Defintion: Let $A$ be a nonempty set. If $w = a_1^{\epsilon_1}a_2^{\epsilon_2}...a_n^{\epsilon_n}$ is a word over $A \cup A^{-}$ where $a_1, a_2, ..., a_n \in A$ and $\epsilon_1, \epsilon_2, ..., \epsilon_n \in \{ 1, -1\}$ then the Inverse Word is denoted by $w^{-1}$ and is defined as $w^{-1} = a_n^{-\epsilon_n}a_{n-1}^{\epsilon_{n-1}}...a_1^{-\epsilon_1}$.

In the example above, we have that:

(2)

\begin{align} \quad w^{-1} = b^{-2}e^{-1}adc^{-1}ab^{-1}a^{-1} \end{align}

Defintion: Let $A$ be a nonempty set. If $u$ and $v$ are words over $A$ then the Concatenation of $u$ with $v$ is the word $uv$ obtained by adjoining the sequence $v$ at the end of the sequence $u$.

For example, if $A = \{ a, b, c \}$, $u = aba$ and $v = cb^{-1}$ then:

(3)

\begin{align} \quad uv = abacb^{-1} \end{align}

Let $A$ be a nonempty set and let $\mathcal R$ be a set of words over $A$. We define an equivalence relation $\sim$ on the set of words on $A \cup A^{-}$ with respect to $\mathcal R$. If $u$ and $v$ are words over $A \cup A^{-}$ we say that $u \sim v$ if there is a finite sequence of words $w_1, w_2, ..., w_n$ with $w_1 = u$ and $w_n = v$ such that for all $i \in \{ 1, 2, ..., n - 1\}$:

• 1) $w_{i+1}$ is obtained from $w_i$ by inserting an occurrence of $xx^{-1}$ in the word $w_i$.

• 2) $w_{i+1}$ is obtained from $w_i$ by deleting an occurrence $xx^{-1}$ in the word $w_i$.

• 3) $w_{i+1}$ is obtained from $w_i$ by inserting a word in $\mathcal R$ or $\mathcal R^{-}$ in the word $w_i$.

• 4) $w_{i+1}$ is obtained from $w_i$ by deleting a word in $\mathcal R$ or $\mathcal R^{-}$ in the word $w_i$.

We will shortly see that the set of these equivalence classes with a particular operation forms a group.