Contents/Index
@1. Monoids in General
Definition
The general theory on monoids. A monoid is a tuple $M = (S,\star)$ of a set $S$ and a binary operator $\star$ for which the following two axioms hold:
- Associativity: For every $a,b,c \in G$ we have that
$$a \star (b \star c) = (a \star b) \star c$$
- The existence of an identity element: We have one unique element $1 \in M$ such that for every $a \in M$ we have
$$1 \star a = a \star 1 = a$$
The second axiom ensures that no monoid is empty. If we furthermore for every $a,b \in M$ have that
$$
a \star b = b \star a
$$
we say that $M$ is abelian or that $M$ is commutative.
Examples
- The set $\mathbb{N} = \{0, 1, 2, ...\}$ with the operator + forms a monoid. Call it $M = (\mathbb{N},+)$. We have that the operator is associative. We have that $a + 0 = 0 + a = a$ for all $a \in M$.
- The set of all strings $S$ forms a monoid with concatenation as the operator. That is $M = (S,*)$. We have that concatenation is associative. Let $\varepsilon$ be the empty string. We have that $\varepsilon * s = s * \varepsilon = s$ for every $s \in S$.