Monoids and Submonoids

In abstract algebra, algebraic structures provide a framework for studying sets and the operations defined on them. By categorizing sets based on the mathematical properties they satisfy, we establish a hierarchy of algebraic systems starting from basic structures like semigroups and moving to highly structured systems like monoids and groups.

1. Algebraic Systems and Binary Operations

An algebraic system is a mathematical structure consisting of a non-empty set paired with one or more binary operations.

Binary Operations and Closure

A binary operator $*$ is said to be a binary operation on a non-empty set $A$ if it satisfies the closure property:

$a * b \in A \quad \forall a, b \in A$

Examples of Closure:

Closed: The set of natural numbers $\mathbb{N} = \{1, 2, 3, \dots\}$ is closed under standard addition ( $+$ ) and multiplication ( $\cdot$ ). For instance, $3 + 5 = 8 \in \mathbb{N}$ and .

An algebraic system is denoted as a tuple $(A, *)$ . When a set is equipped with multiple operations, it is represented as $(A, *_1, *_2, \dots)$ . For instance:

$(\mathbb{N}, +)$
$(\mathbb{Z}, +, -)$
$(\mathbb{R}, +, \cdot, -)$

Fundamental Properties of Binary Operations

Let $*$ be a binary operation on a non-empty set $A$ :

Commutativity: The operation $*$ is commutative if: $a * b = b * a \quad \forall a, b \in A$
Associativity: The operation $*$ is associative if: $(a * b) * c = a * ($

2. Semigroups and Subsemigroups

A semigroup is a simpler algebraic system that serves as a building block for monoids.

Definition of a Semigroup

An algebraic system $(A, *)$ is called a semigroup if it satisfies the following two axioms:

Closure: $*$ is a closed operation on $A$ .
Associativity: $*$ is associative on $A$ , meaning $(a * b) * c = a * (b * c)$ for all .

Examples of Semigroups:

$(\mathbb{N}, +)$ is a semigroup.
$(\mathbb{N}, \cdot)$ is a semigroup.
The set of positive odd integers $A = \{1, 3, 5, 7, \dots\}$ under multiplication is a semigroup because:

Non-Examples of Semigroups:

$(\mathbb{N}, -)$ is not a semigroup because subtraction is neither closed on $\mathbb{N}$ nor associative: $(5 - 3) - 1 = 1 \neq 5 - (3 - 1) = 3$ .

Subsemigroups

Let $(S, *)$ be a semigroup and let $T \subseteq S$ . The algebraic system $(T, *)$ is called a subsemigroup of $(S, *)$ if the subset $T$ is closed under the operation :

$a * b \in T \quad \forall a, b \in T$

Example of a Subsemigroup:

Consider the semigroup $(\mathbb{N}, +)$ , where $\mathbb{N}$ is the set of all natural numbers. Let $\mathbb{E}$ be the set of all positive even integers $\mathbb{E} = \{2, 4, 6, \dots\}$ . Since and the sum of any two even integers is an even integer, is a subsemigroup of .

Cartesian Product of Semigroups

If $(S_1, *_1)$ and $(S_2, *_2)$ are semigroups, then their Cartesian product is also a semigroup under the component-wise operation defined by:

$(s_1', s_2') * (s_1'', s_2'') = (s_1' *_1 s_1'',\ s_2' *_2 s_2'')$

text

       S1 Semigroup             S2 Semigroup
       [ s1', s1'' ]           [ s2', s2'' ]
             │                       │
             └───────────┬───────────┘
                         ▼
                  S1 x S2 Product
       [ (s1', s2') * (s1'', s2'') ]

Proof of Associativity:

Let $a = (a_1, a_2)$ , $b = (b_1, b_2)$ , and .

$a * (b * c) = (a_1, a_2) * \left((b_1, b_2) * (c_1, c_2)\right)$

$= (a_1, a_2) * (b_1 *_1 c_1,\ b_2 *_2 c_2)$

$= (a_1 *_1 (b_1 *_1 c_1),\ a_2 *_2 (b_2 *_2 c_2))$

Since both $S_1$ and $S_2$ are associative semigroups:

$= ((a_1 *_1 b_1) *_1 c_1,\ (a_2 *_2 b_2) *_2 c_2)$

$= (a_1 *_1 b_1,\ a_2 *_2 b_2) * (c_1, c_2)$

$= \left((a_1, a_2) * (b_1, b_2)\right) * (c_1, c_2) = (a * b) * c$

Since the operation is closed and associative, $(S_1 \times S_2, *)$ is a semigroup.

3. Monoids

A monoid extends a semigroup by requiring the existence of an identity element.

Definition of a Monoid

An algebraic system $(M, *)$ is a monoid if it satisfies three essential axioms:

Closure: $a * b \in M$ for all $a, b \in M$ .
Associativity: $(a * b) * c = a * (b * c)$ for all .

The algebraic hierarchy can be visualized as follows:

text

  Algebraic Systems
         │
         ▼ (requires Associativity)
     Semigroups
         │
         ▼ (requires Identity Element)
      Monoids
         │
         ▼ (requires Inverse Elements)
       Groups
         │
         ▼ (requires Commutativity)
    Abelian Groups

Examples of Monoids

Additive Natural Numbers with Zero: Consider $(\mathbb{N} \cup \{0\}, +)$ $(N \cup {0}, +)$ .
- Closure: Sum of two non-negative integers is non-negative.
- Associativity: Addition is associative.
- Identity: $0$ serves as the identity element, since $a + 0 = 0 + a = a$ .

Semigroups that are NOT Monoids

Let $(\mathbb{Z}, *)$ be an algebraic structure where the operation is defined as:

$n * m = \max(n, m)$

Closure: $\max(n, m) \in \mathbb{Z}$ for all $n, m \in \mathbb{Z}$ .
Associativity: $\max(\max(a, b), c) = \max(a, \max(b, c)) = \max(a, b, c)$ . Therefore, is a semigroup.

4. Key Computer Science Examples of Monoids

Monoids are widely applied in computer science, notably in formal languages, string processing, and functional programming.

A. The Free Monoid of Strings (String Concatenation)

Let $\Sigma$ be a finite alphabet, and let $S = \Sigma^*$ be the set of all finite-length strings constructed from $\Sigma$ , including the empty string $\lambda$ (sometimes denoted as $\epsilon$ ). Let the binary operation be string concatenation, represented by $+$ .

Closure: Concatenating any two strings $s_1, s_2 \in S$ results in another string $s_1 + s_2 \in S$ .

Hence, $(S, +)$ is a monoid.

Note: $(S, +)$ is not a group because the inverse of a non-empty string does not exist under concatenation (i.e., you cannot concatenate a string with another to cancel it out and get the empty string $\lambda$ ).

B. Function Composition Monoid

Let $S$ be a set, and let $F(S)$ be the collection of all functions $f: S \to S$ . The binary operation is the composition of functions, denoted by $\circ$ .

Closure: The composition of two functions $f_1, f_2 \in F(S)$ (defined as $(f_1 \circ f_2)(x) = f_1(f_2(x))$ ) is also a function from to .

Hence, $(F(S), \circ)$ is a monoid.

5. Submonoids

Definition of a Submonoid

Let $(M, *)$ be a monoid and let $H \subseteq M$ . The algebraic system $(H, *)$ is a submonoid of $(M, *)$ if and only if it satisfies the following two properties:

Closure: $H$ is closed under the operation $*$ : $a * b \in H \quad \forall a, b \in H$
Identity Preservation: The identity element $e$ of the parent monoid must belong to :

text

                 Monoid (M, *, e)
             ┌──────────────────────┐
             │                      │
             │   Submonoid (H)      │
             │   ┌──────────────┐   │
             │   │  h1, h2, ... │   │
             │   │  Identity e  │   │
             │   └──────────────┘   │
             │                      │
             └──────────────────────┘

Examples of Submonoids

Even Non-Negative Integers: Let $(M, +)$ be the monoid $(\mathbb{N} \cup \{0\}, +)$ with identity element $0$ . Let $H$ be the set of even non-negative integers ${0, 2, 4, 6, \dots$ .

Non-Examples of Submonoids

Let $(\mathbb{N} \cup \{0\}, +)$ $(N \cup {0}, +)$ be the additive monoid with identity $0$ $0$ . Let $H$ $H$ be the set of positive odd integers $\{1, 3, 5, \dots\}$ ${1, 3, 5, \dots}$ .
- This is not a submonoid because the identity element . Additionally, it is not closed under addition ().

6. Transposing to Groups

To contextualize monoids in the broader spectrum of algebraic structures, we can look at what happens when we enforce the existence of inverses.

A monoid $(G, *)$ becomes a group if it satisfies the inverse property:

$\forall a \in G, \exists a^{-1} \in G \text{ such that } a * a^{-1} = a^{-1} * a = e$

If the operation is also commutative, the group is called an Abelian group.

Matrix Multiplication Example

Let $M$ be the set of all $n \times n$ non-singular matrices.

Monoid Status: Under matrix multiplication, $M$ acts as a monoid. The identity element is the identity matrix $I_n$ .
Group Status: Since all matrices in $M$ are non-singular (determinant $|A| \neq 0$ ), every matrix has a unique multiplicative inverse such that . Thus, is a group.

Summary

An algebraic system is a set paired with closed operations.
A semigroup is an algebraic system $(S, *)$ that is closed and associative.
A monoid is a semigroup that also contains a unique identity element $e$ such that $a * e = e * a = a$ .
Submonoids are subsets of a monoid that are closed under the parent operation and contain the parent monoid's identity element.
Common computer science abstractions like string concatenation and function composition are classical representations of monoids.

Assessed progress

Monoids and Submonoids

Monoids and Submonoids

1. Algebraic Systems and Binary Operations

Binary Operations and Closure

Examples of Closure:

Fundamental Properties of Binary Operations

2. Semigroups and Subsemigroups

Definition of a Semigroup

Examples of Semigroups:

Non-Examples of Semigroups:

Subsemigroups

Example of a Subsemigroup:

Cartesian Product of Semigroups

Proof of Associativity:

3. Monoids

Definition of a Monoid

Examples of Monoids

Semigroups that are NOT Monoids

4. Key Computer Science Examples of Monoids

A. The Free Monoid of Strings (String Concatenation)

B. Function Composition Monoid

5. Submonoids

Definition of a Submonoid

Examples of Submonoids

Non-Examples of Submonoids

6. Transposing to Groups

Matrix Multiplication Example

Summary

Key Concepts

Algebraic System

Closure Property

Semigroup

Monoid

Submonoid

Quick Check

Discrete Mathematical Structures

Discrete Mathematical Structures