Definition:Word (Abstract Algebra)

From ProofWiki
(Redirected from Definition:Set of Words)
Jump to navigation Jump to search

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.