Abstract Algebra: Monoids, Groups, Semirings, and Fields

The Hierarchy of Algebraic Structures

Abstract algebra studies mathematical structures by specifying the operations and properties they must satisfy. Each structure adds more requirements, making it more powerful but more restrictive.

---

Monoids

Definition

A monoid is a triple $(S, \bullet, e)$ where:

• $S$ is a set
• $\bullet : S \times S \to S$ is a binary operation (closed)
• $e \in S$ is the identity element

satisfying:

1. Associativity: $(x \bullet y) \bullet z = x \bullet (y \bullet z)$ for all $x, y, z \in S$
2. Identity: $e \bullet x = x = x \bullet e$ for all $x \in S$

Examples

Monoid	Operation	Identity
$(\mathbb{N}, +, 0)$	Addition	$0$
$(\mathbb{N}, \times, 1)$	Multiplication	$1$
$(\Sigma^*, \cdot, \varepsilon)$	String concatenation	$\varepsilon$
$(\text{Rel}(A, A), \circ, \text{id}_A)$	Relational composition	$\text{id}_A$
$(\mathcal{P}(A), \cup, \emptyset)$	Union	$\emptyset$
$(\mathcal{P}(A), \cap, A)$	Intersection	$A$

Commutative Monoid

A monoid is commutative (or abelian) if $x \bullet y = y \bullet x$ for all $x, y \in S$.

Examples: $(\mathbb{N}, +, 0)$, $(\mathcal{P}(A), \cup, \emptyset)$.

Non-example: $(\Sigma^*, \cdot, \varepsilon)$ is NOT commutative ($ab \neq ba$ in general).

Examinable: Endo-Relations Form a Monoid

Theorem: For any set $A$, the endo-relations $(\text{Rel}(A, A), \circ, \text{id}_A)$ form a monoid.

Proof:

• Closure: Composition of relations $R : A \nrightarrow A$ and $S : A \nrightarrow A$ yields $S \circ R : A \nrightarrow A$.
• Associativity: Already proved: $(T \circ S) \circ R = T \circ (S \circ R)$.
• Identity: $\text{id}_A \circ R = R = R \circ \text{id}_A$.

---

Groups

Definition

A group is a monoid $(G, \bullet, e)$ where every element has an inverse.

For each $x \in G$, there exists $x^{-1} \in G$ such that:

$x \bullet x^{-1} = e = x^{-1} \bullet x$

Examples

Group	Operation	Identity	Inverse
$(\mathbb{Z}, +, 0)$	Addition	$0$	$-x$
$(\mathbb{Q} \setminus \{0\}, \times, 1)$	Multiplication	$1$	$1/x$
$(\mathbb{Z}_n, +, 0)$ mod $n$	Addition mod $n$	$0$	$n - x$
Symmetric group $S_n$	Permutation composition	Identity permutation	Inverse permutation

Abelian Group

A group is abelian if the operation is commutative.

Key Property

In a group, equations are always solvable: for any $a, b \in G$, there exists a unique $x$ with $a \bullet x = b$ (namely $x = a^{-1} \bullet b$).

Non-examples

• $(\mathbb{N}, +, 0)$ is NOT a group (no additive inverses)
• $(\mathbb{Z}, \times, 1)$ is NOT a group (most elements lack multiplicative inverses)

---

Semirings

Definition

A semiring is a structure $(S, 0, \oplus, 1, \otimes)$ where:

1. $(S, 0, \oplus)$ is a commutative monoid (addition)
2. $(S, 1, \otimes)$ is a monoid (multiplication)
3. Distributivity: $x \otimes (y \oplus z) = (x \otimes y) \oplus (x \otimes z)$ and $(x \oplus y) \otimes z = (x \otimes z) \oplus (y \otimes z)$
4. Annihilation: $0 \otimes x = 0 = x \otimes 0$

Examples

Semiring	Addition $\oplus$	Multiply $\otimes$	Zero	One
$(\mathbb{N}, +, \times)$	$+$	$\times$	$0$	$1$
Boolean semiring $\mathbb{B}$	$\lor$ (OR)	$\land$ (AND)	$0$	$1$
Min-plus (tropical)	$\min$	$+$	$\infty$	$0$
Max-plus	$\max$	$+$	$-\infty$	$0$

The Boolean Semiring

$\mathbb{B} = (\{0, 1\}, 0, \lor, 1, \land)$

This is the foundation for:

• Relational composition via matrix multiplication
• Reachability in graphs

The Min-Plus Semiring (Tropical)

$(\mathbb{R} \cup \{\infty\}, \infty, \min, 0, +)$

Applications:

• Shortest path algorithms
• Dynamic programming optimisation

---

Rings

Definition

A ring is a semiring where $(S, 0, \oplus)$ is an abelian group.

Every element has an additive inverse.

Examples

• $(\mathbb{Z}, +, \times)$: integers (additive inverse is negation)
• $(\mathbb{Z}_n, +, \times)$: integers mod $n$
• Polynomials over $\mathbb{Z}$

Non-example

$(\mathbb{N}, +, \times)$ is NOT a ring (no additive inverses).

---

Fields

Definition

A field is a commutative ring where every non-zero element has a multiplicative inverse.

$(F, 0, +, 1, \times)$ satisfies:

1. $(F, 0, +)$ is an abelian group
2. $(F \setminus \{0\}, 1, \times)$ is an abelian group
3. Distributivity holds

Examples

• $\mathbb{Q}$: rational numbers
• $\mathbb{R}$: real numbers
• $\mathbb{C}$: complex numbers
• $\mathbb{Z}_p$: integers mod $p$, where $p$ is prime

Key Theorem

Theorem: $\mathbb{Z}_p$ (integers mod $p$) is a field if and only if $p$ is prime.

Proof:

• If $p$ is prime and $a \not\equiv 0 \pmod{p}$, then $\gcd(a, p) = 1$.
• By Bézout’s identity, $\exists x, y$ with $ax + py = 1$.
• Thus $ax \equiv 1 \pmod{p}$, so $a$ has a multiplicative inverse.
• If $p$ is composite, say $p = ab$ with $1 < a, b < p$, then $a, b$ are zero divisors and cannot have inverses.

Why This Matters for Cryptography

$\mathbb{Z}_p$ being a field is essential for:

• Diffie-Hellman key exchange: relies on exponentiation in $\mathbb{Z}_p^*$
• RSA: requires computing inverses mod $\varphi(n)$

---

Summary Table

Structure	Addition	Multiplication	Key Property
Monoid	Associative + Identity	—	Minimal structure
Group	Inverses exist	—	Equations solvable
Semiring	Commutative monoid	Monoid	Matrix multiplication works
Ring	Abelian group	Monoid	Can subtract
Field	Abelian group	Abelian group (except 0)	Can divide

---

Tripos Questions

2016 P2 Q6: Prove that the set of all strings over alphabet $\{a, b\}$ under concatenation forms a monoid. Is it a group?

2020 P2 Q9: Show that $\mathbb{Z}_p$ is a field when $p$ is prime. Explain why $a^{p-1} \equiv 1 \pmod{p}$ for $a \not\equiv 0 \pmod{p}$.

---

Summary

• Monoid: set + operation + identity + associativity
• Group: monoid + inverses
• Semiring: two operations, distributivity, additive identity annihilates
• Ring: semiring + additive inverses
• Field: ring + multiplicative inverses (except zero)
• $\mathbb{Z}_p$ is a field iff $p$ is prime (foundational for cryptography)