Definition:Word (Abstract Algebra)
This page is about Word in the context of Abstract Algebra. For other uses, see Word.
Definition
Let $\struct {M, \circ}$ be a magma.
Let $S \subseteq M$ be a subset.
A word in $S$ is the product of a finite number of elements of $S$.
The set of words in $S$ is denoted $\map W S$:
- $\map W S := \set {s_1 \circ s_2 \circ \cdots \circ s_n: n \in \N_{>0}: s_i \in S, 1 \le i \le n}$
Note that there is nothing in this definition preventing any of the elements of $S$ being repeated, neither is anything said about the order of these elements.
Monoid
Let $\struct {M, \circ}$ be a monoid whose identity element is $e$.
Let $S \subseteq M$ be a subset of $M$.
The set of words in $S$ is denoted and defined:
- $\map W S := \set {\ds \sum_{i \mathop = 1}^r n_i \cdot s_i : r \in \N, n_i \in \N, s_i \in S}$
where:
- $n_i \cdot s_i$ denotes the power of $s_i$:
- $n \cdot a = \begin {cases}
e & : n = 0 \\ \paren {\paren {n - 1} \cdot a} \circ a & : n > 0 \end {cases}$
- $\ds \sum_{i \mathop = 1}^r n_i \cdot s_i := \paren {n_1 \cdot s_1} \circ \paren {n_2 \cdot s_2} \circ \cdots \circ \paren {n_r \cdot s_r}$
Also denoted as
Some sources use $\operatorname {gp} S$ for $\map W S$.
Context
It is usual for the algebraic structure of the concept of a word to be a group, a monoid or a semigroup.
However, if the operation $\circ$ is not associative then this definition still holds.
Examples
Set with $2$ Elements
Let $G$ be a group.
Let $X \subseteq G$ be a subset of $G$ such that $X = \set {a, b}$.
Then some of the elements of the set of words $\map W S$ of $G$ are:
- $a, b, a b, b a, a b a, b a b, a^{-1} b, b a^{-1}, a b^{-1}, b^{-1} a, a b^{-1}, a^{-1} b^{-1}, a^{-1} b^{-1} a, \ldots$
Symmetric Group on $3$ Letters
Let $S_3$ denote the Symmetric Group on 3 Letters, whose Cayley table is given as:
- $\begin{array}{c|cccccc}
\circ & e & (123) & (132) & (23) & (13) & (12) \\ \hline e & e & (123) & (132) & (23) & (13) & (12) \\ (123) & (123) & (132) & e & (13) & (12) & (23) \\ (132) & (132) & e & (123) & (12) & (23) & (13) \\ (23) & (23) & (12) & (13) & e & (132) & (123) \\ (13) & (13) & (23) & (12) & (123) & e & (132) \\ (12) & (12) & (13) & (23) & (132) & (123) & e \\ \end{array}$
Consider the subset $\set {\tuple {1 2}, \tuple {132} }$ of $S_3$.
Then some of the elements of the set of words of $\set {\tuple {1 2}, \tuple {132} }$ are:
- $\tuple {123}^2, \tuple {123}^{-1} \tuple {1 2}^2, \tuple {123} \tuple {1 2} \tuple {123}^{-1} \tuple {1 2}^{-1}, \ldots$
Also see
- Results about words in the context of abstract algebra can be found here.