Semigroups and Monoids: Introduction with Examples

A semigroup is a set equipped with an associative binary operation — closure plus associativity, nothing more. Add the requirement of an identity element and you get a monoid. The set of all strings over an alphabet, under concatenation, is the prototypical monoid: associativity holds, and the empty string is the identity.

These are the simplest algebraic structures, and they model sequential processes everywhere: composing functions, concatenating strings, running state machines, and combining MapReduce results. Whenever order of combination is irrelevant to bracketing but inverses are not needed, a semigroup or monoid is at work.

Key Concepts

• Semigroup: a set S with an associative binary operation (closure + associativity).
• Monoid: a semigroup possessing an identity element e with a ∗ e = e ∗ a = a.
• Uniqueness of identity: a monoid has exactly one identity — if e and e′ both work, e = e ∗ e′ = e′.
• Generalised associativity: any bracketing of a₁ ∗ a₂ ∗ … ∗ aₙ gives the same result, so the product can be written without parentheses.
• Examples: (ℕ, +) and (ℕ, ×) are monoids; strings under concatenation form a monoid; n×n matrices under multiplication form a monoid with the identity matrix.
• Non-examples: positive integers under addition form a semigroup but not a monoid (no identity); (ℤ, −) is not even a semigroup (subtraction is not associative).

How It Works

• Testing a semigroup: verify closure (a ∗ b ∈ S) and associativity ((a ∗ b) ∗ c = a ∗ (b ∗ c)) — two checks, no identity hunt.
• Upgrading to a monoid: solve a ∗ e = a for an e independent of a; verify e ∗ a = a too.
• Why associativity matters: it lets you fold a sequence left-to-right or in parallel chunks (the basis of parallel reduction) and get the same answer.
• Submonoids: a subset containing the identity and closed under the operation, e.g. even numbers under addition inside (ℤ, +).
• Homomorphisms: structure-preserving maps between monoids, e.g. string length from (strings, concat) to (ℕ, +).

Worked Example

Determine whether (ℤ, ∗) with a ∗ b = max(a, b) is a semigroup or a monoid.

1. Closure: max(a, b) is an integer for integers a, b ✓.
2. Associativity: max(max(a, b), c) = max(a, b, c) = max(a, max(b, c)) ✓. Numerically: max(max(3, 7), 5) = max(7, 5) = 7 and max(3, max(7, 5)) = max(3, 7) = 7 ✓.
3. So (ℤ, max) is a semigroup.
4. Identity hunt: need e with max(a, e) = a for every integer a — that requires e ≤ a for all a, impossible since ℤ is unbounded below.
5. Conclusion: (ℤ, max) is a semigroup but not a monoid. (On ℕ with a ∗ b = min(a, b), by contrast, 0 would fail but there is still no identity; on a bounded set like {1, …, 10} under max, 1 is the identity — a monoid.)

Common Misconceptions

• "A monoid needs inverses." No — inverses are the extra axiom that promotes a monoid to a group. (ℕ, +) is a monoid though no positive integer has an additive inverse in ℕ.
• "The identity must look like 0 or 1." The identity is whatever the operation demands: the empty string for concatenation, the identity matrix for matrix multiplication.
• "Every finite semigroup has an identity." False — ({a, b}, x ∗ y = x) is a finite semigroup (the left-projection operation is associative) with no identity element.

Real-World Applications

• Automata and formal languages: state transitions compose as a monoid; regular languages correspond to finite monoids.
• Functional programming: MapReduce aggregation (sums, string building, set union) works precisely because the combine step is a monoid operation.
• Function composition: all functions from a set to itself form a monoid under composition — the setting of iteration and dynamical systems.

A semigroup asks only for closure and associativity; a monoid adds a unique identity. The max example shows how to test both properties mechanically — and the identity hunt failing is exactly what separates the two structures. From here, adding inverses gives groups, the next rung of the algebraic ladder.