Monoids and Groups: short notes (Engineering Mathematics)

Introduction

An algebraic structure is a set together with one or more operations that combine elements. Abstracting away from what the elements are (numbers, strings, permutations, matrices) and keeping only the laws the operation obeys lets one theorem cover all of them. Strings under concatenation form a monoid, which is why automata theory and parsing can use algebraic arguments; the integers modulo $n$ form groups that underlie hashing, checksums and public-key cryptography; permutations of a set form groups used in counting arguments.

The development follows the hierarchy semigroup, monoid, group, abelian group, then covers subgroups, cyclic groups and Lagrange's theorem. Rings and fields are defined at the end for reference.

Prerequisites

Functions: a binary operation is a function $S \times S \to S$ ; bijections and composition.
Modular arithmetic: $a \bmod n$ is the remainder in $\{0, \ldots, n-1\}$ ; $\gcd$ .

Core concepts

Binary operations and their properties

A binary operation on a set $S$ is a function $* : S \times S \to S$ . Requiring the result to lie in $S$ is the closure property; subtraction is a binary operation on $\mathbb{Z}$ but not on $\mathbb{N}$ ( $2 - 5 \notin \mathbb{N}$ ).

Property	Statement
Associative	$(a * b) * c = a * (b * c)$ for all $a, b, c$
Commutative	$a * b = b * a$ for all $a, b$
Identity	some $e$ with $e * a = a * e = a$ for all $a$
Inverse (given identity $e$ )	for $a$ , some $a^{-1}$ with $a * a^{-1} = a^{-1} * a = e$
Idempotent element	$a * a = a$

On an $n$ -element set there are $n^{n^2}$ binary operations (each of the $n^2$ table cells holds one of $n$ values) and $n^{n(n+1)/2}$ commutative ones (only the diagonal and the cells above it are free).

The hierarchy

Structure	Closure	Associative	Identity	Inverses	Commutative
Semigroup	Yes	Yes
Monoid	Yes	Yes	Yes
Group	Yes	Yes	Yes	Yes (every element)
Abelian group	Yes	Yes	Yes	Yes	Yes

Hierarchy of algebraic structures from bottom to top: magma, semigroup (associative), monoid (identity element), group (every element has an inverse), abelian group (commutative). — Figure 1. Each structure adds one axiom to the one below it.

Some books call a set with just a closed binary operation an algebraic system or groupoid instead of a magma; the axioms above are what matter.

Examples and non-examples

Set and operation	Semigroup	Monoid	Group	Abelian
$(\mathbb{Z}, +)$	Yes	Yes ( $e = 0$ )	Yes ( $a^{-1} = -a$ )	Yes
$(\mathbb{N}, +)$ , with $0 \in \mathbb{N}$	Yes	Yes	No (no $-1$ )	n/a
$(\mathbb{Z}^{+}, +)$	Yes	No (no 0)	No	n/a
$(\mathbb{Z}, \times)$	Yes	Yes ( $e = 1$ )	No (2 has no inverse)	n/a
$(\mathbb{Q} - \{0\}, \times)$	Yes	Yes	Yes	Yes
$(\mathbb{Z}, -)$	No (not associative)	No	No	n/a
$(\Sigma^*, \cdot)$ , strings under concatenation	Yes	Yes ( $e = \varepsilon$ )	No for a nonempty alphabet; yes for the empty alphabet	n/a for a nonempty alphabet (not a group); yes for the empty alphabet. Concatenation is commutative exactly when $\lvert\Sigma\rvert\le1$ .
$(\mathcal P(A),\cup)$	Yes	Yes ( $e=\emptyset$ )	No for $A\ne\emptyset$ ; yes for $A=\emptyset$ (trivial group)	Yes for $A=\emptyset$ ; n/a for $A\ne\emptyset$ (not a group)
$(\mathcal{P}(A), \oplus)$ (symmetric difference)	Yes	Yes ( $e = \emptyset$ )	Yes ( $X^{-1} = X$ )	Yes
$(\mathbb{Z}_n, +_n)$ , addition mod $n$	Yes	Yes	Yes	Yes
$(\mathbb{Z}_n^{*}, \times_n)$ , units mod $n$	Yes	Yes	Yes	Yes
$(S_n, \circ)$ , permutations of $n$ objects	Yes	Yes	Yes	Only for $n \le 2$
Invertible $n \times n$ real matrices under product	Yes	Yes	Yes	Only for $n = 1$

For these modular-unit examples assume $n\ge2$ . Here $\mathbb{Z}_n^{*} = \{a \in \{1, \ldots, n-1\} \mid \gcd(a, n) = 1\}$ , of size $\varphi(n)$ (Euler's totient). $(\mathbb{Z}_n - \{0\}, \times_n)$ is a group if and only if $n$ is prime.

Basic theorems

For a group $(G, *)$ with identity $e$ :

The identity is unique. (If $e, e'$ are identities, $e = e * e' = e'$ .) This holds already in a monoid.
Each element has a unique inverse. (If $b, c$ are inverses of $a$ , $b = b * (a * c) = (b * a) * c = c$ .) Also holds for invertible elements of a monoid.
$(a^{-1})^{-1} = a$ and $(a * b)^{-1} = b^{-1} * a^{-1}$ (the order reverses).
Cancellation: $a * b = a * c \Rightarrow b = c$ , and $b * a = c * a \Rightarrow b = c$ .
The equations $a * x = b$ and $y * a = b$ have unique solutions $x = a^{-1} * b$ , $y = b * a^{-1}$ . Hence in the Cayley table (operation table) of a finite group every element appears exactly once in each row and each column (a Latin square). This is necessary but not sufficient: a Latin square table need not be associative.
If $a * a = e$ for every $a$ , then $G$ is abelian. (Proof: $ab = (ab)^{-1} = b^{-1} a^{-1} = ba$ .)

Order of a group and of an element

The order $|G|$ is the number of elements.
The order of an element $a$ , written $o(a)$ , is the least positive $k$ with $a^k = e$ (in additive notation, $k \cdot a = 0$ ); if none exists, $a$ has infinite order. $o(e) = 1$ , $o(a) = o(a^{-1})$ .
For integer $m$ , if $a$ has finite order $d$ , then $a^m=e$ if and only if $d\mid m$ ; if $a$ has infinite order, $a^m=e$ if and only if $m=0$ .
In $(\mathbb{Z}_n, +_n)$ , $o(a) = n / \gcd(a, n)$ .

Subgroups

A non-empty subset $H \subseteq G$ is a subgroup ( $H \le G$ ) if it is a group under the same operation. Tests:

One-step test: $H \ne \emptyset$ and $a, b \in H \Rightarrow a * b^{-1} \in H$ .
Finite test: if $H$ is finite and non-empty, closure under $*$ alone suffices.

The intersection of two subgroups is a subgroup; their union is a subgroup if and only if one contains the other.

Lagrange's theorem

If $G$ is a finite group and $H \le G$ , then $|H|$ divides $|G|$ . The cosets $aH = \{a * h \mid h \in H\}$ partition $G$ into blocks of size $|H|$ , and their number is the index $[G : H] = |G| / |H|$ .

Consequences:

$o(a)$ divides $|G|$ (apply Lagrange to the subgroup generated by $a$ ), so $a^{|G|} = e$ .
A group of prime order $p$ is cyclic, generated by any non-identity element, and has only the trivial subgroups $\{e\}$ and $G$ .
The converse of Lagrange is false: the alternating group $A_4$ has order 12 but no subgroup of order 6.
Applied to $\mathbb{Z}_n^{*}$ : $a^{\varphi(n)} \equiv 1 \pmod n$ when $\gcd(a, n) = 1$ (Euler), and $a^{p-1} \equiv 1 \pmod p$ for prime $p \nmid a$ (Fermat).

Cyclic groups

$G$ is cyclic if $G = \langle g \rangle = \{g^k \mid k \in \mathbb{Z}\}$ for some generator $g$ . Every cyclic group is abelian (the converse fails: the Klein four-group is abelian and not cyclic). Every subgroup of a cyclic group is cyclic.

For a finite cyclic group of order $n$ :

the number of generators is $\varphi(n)$ ; in $\mathbb{Z}_n$ , $a$ generates if and only if $\gcd(a, n) = 1$ ;
for each divisor $d$ of $n$ there is exactly one subgroup of order $d$ , so the number of subgroups is the number of divisors of $n$ ;
the number of elements of order $d$ is $\varphi(d)$ for each $d \mid n$ .

Every group of order 1, 2, 3, 5 or 7 (prime orders and 1) is cyclic; of order 4 it is either $\mathbb{Z}_4$ or the Klein four-group $V_4 = \mathbb{Z}_2 \times \mathbb{Z}_2$ . Every group of order at most 5 is abelian; the smallest non-abelian group is $S_3$ , of order 6.

Rings and fields (definitions for reference)

A ring $(R, +, \cdot)$ : $(R, +)$ is an abelian group, $(R, \cdot)$ is a semigroup (these notes also require a multiplicative identity 1, as in many modern texts; some books do not), and multiplication distributes over addition on both sides. Example: $(\mathbb{Z}, +, \times)$ , $(\mathbb{Z}_n, +_n, \times_n)$ , $n \times n$ matrices.
A field is a commutative ring with $1 \ne 0$ in which every non-zero element has a multiplicative inverse, so $(F - \{0\}, \cdot)$ is an abelian group. Examples: $\mathbb{Q}, \mathbb{R}, \mathbb{C}$ , and $\mathbb{Z}_p$ for prime $p$ . $\mathbb{Z}_n$ is a field if and only if $n$ is prime.

Worked examples

Example 1: identify the structure

On $\mathbb{Z}$ , define $a * b = a + b - 3$ . Closure: yes. Associative: $(a * b) * c = a + b + c - 6 = a * (b * c)$ . Identity: $a * e = a$ gives $e = 3$ . Inverse: $a * a' = 3$ gives $a' = 6 - a$ . Commutative: yes. So $(\mathbb{Z}, *)$ is an abelian group.

On $\mathbb{Z}$ , $a * b = \max(a, b)$ : associative and commutative, but no identity (it would have to be $-\infty$ ), so a semigroup only. On $\mathbb{N}$ (with 0), $\max$ has identity 0, giving a commutative monoid that is not a group.

Example 2: element orders in $\mathbb{Z}_{12}$

$o(a) = 12/\gcd(a, 12)$ : $o(0) = 1$ ; $o(6) = 2$ ; $o(4) = o(8) = 3$ ; $o(3) = o(9) = 4$ ; $o(2) = o(10) = 6$ ; $o(1) = o(5) = o(7) = o(11) = 12$ . Generators: $1, 5, 7, 11$ , that is $\varphi(12) = 4$ . Subgroups: one for each divisor $1, 2, 3, 4, 6, 12$ , six in all. The counts $1, 1, 2, 2, 2, 4$ of elements of each order equal $\varphi(d)$ and add to 12.

Example 3: the group $\mathbb{Z}_{10}^{*}$

$\mathbb{Z}_{10}^{*} = \{1, 3, 7, 9\}$ , $\varphi(10) = 4$ . Powers of 3 mod 10: $3, 9, 7, 1$ , so 3 generates the group, which is cyclic of order 4. Inverses: $3^{-1} = 7$ (since $21 \equiv 1$ ), $9^{-1} = 9$ . Lagrange check: $o(9) = 2$ divides 4.

Example 4: a non-abelian group

In $S_3$ with composition (apply the right permutation first), let $\sigma = (1\,2)$ and $\tau = (1\,2\,3)$ . Then $\sigma \circ \tau$ sends $1 \to 2 \to 1$ , $2 \to 3 \to 3$ , $3 \to 1 \to 2$ , giving $(2\,3)$ , while $\tau \circ \sigma = (1\,3)$ . Since these differ, $S_3$ is not abelian. Element orders in $S_3$ : one of order 1, three of order 2, two of order 3; all divide 6, but no element has order 6, so $S_3$ is not cyclic.

Important properties and observations

A monoid's invertible elements form a group (the group of units).
A finite semigroup with both cancellation laws is a group.
Associativity cannot be read off a Cayley table at a glance; check it (or recognise the operation).
In additive notation, the identity is 0, the inverse of $a$ is $-a$ , and $a^k$ becomes $k a$ .
Groups of order $p^2$ ( $p$ prime) are abelian, though not necessarily cyclic ( $V_4$ has order 4).

GATE examination perspective

Structure identification. Given a set and an operation (possibly a custom one such as $a * b = a + b - ab$ ), check closure, associativity, identity, inverses and commutativity in that order. Check closure and the existence of inverses for every element carefully.
Orders and generators. Use $o(a) = n/\gcd(a, n)$ in $\mathbb{Z}_n$ , $\varphi(n)$ generators, one subgroup per divisor.
Lagrange. Possible subgroup and element orders must divide $|G|$ ; remember the converse is false.
Trap: $(\mathbb{Z}_n - \{0\}, \times_n)$ is a group only for prime $n$ .
Trap: $(ab)^{-1} = b^{-1} a^{-1}$ , not $a^{-1} b^{-1}$ , in a non-abelian group.

Summary

Semigroup: closed + associative; monoid: + identity; group: + inverses; abelian: + commutative.
Identity and inverses are unique; cancellation holds in groups; Cayley tables of groups are Latin squares.
Lagrange: $|H|$ divides $|G|$ ; $o(a)$ divides $|G|$ ; prime-order groups are cyclic.
Cyclic of order $n$ : $\varphi(n)$ generators, one subgroup per divisor of $n$ .
$\mathbb{Z}_n$ under $+$ is always a group; $\mathbb{Z}_n^{*}$ under $\times$ is a group of order $\varphi(n)$ .
By the convention used here, a ring is an abelian group under $+$ , with associative multiplication, a multiplicative identity, and both distributive laws. A field is a commutative ring with $1\ne0$ in which every nonzero element is multiplicatively invertible.

Functions: prerequisite. Binary operations and bijections (permutations).
Partial Orders and Lattices: related. Lattices are another algebraic structure with two operations.
Alphabets, Strings and Languages: related. $\Sigma^*$ is the free monoid on $\Sigma$ .

Monoids and Groups

Introduction

Prerequisites

Core concepts

Binary operations and their properties

The hierarchy

Examples and non-examples

Basic theorems

Order of a group and of an element

Subgroups

Lagrange's theorem

Cyclic groups

Rings and fields (definitions for reference)

Worked examples

Example 1: identify the structure

Example 2: element orders in $\mathbb{Z}_{12}$

Example 3: the group $\mathbb{Z}_{10}^{*}$

Example 4: a non-abelian group

Important properties and observations

GATE examination perspective

Summary

Sources

Next steps

Introduction

Prerequisites

Core concepts

Binary operations and their properties

The hierarchy

Examples and non-examples

Basic theorems

Order of a group and of an element

Subgroups

Lagrange's theorem

Cyclic groups

Rings and fields (definitions for reference)

Worked examples

Example 1: identify the structure

Example 2: element orders in Z12\mathbb{Z}_{12}Z12​

Example 3: the group Z10∗\mathbb{Z}_{10}^{*}Z10∗​

Example 4: a non-abelian group

Important properties and observations

GATE examination perspective

Summary

Related topics

Sources

Next steps

Example 2: element orders in $\mathbb{Z}_{12}$

Example 3: the group $\mathbb{Z}_{10}^{*}$