Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Groups, semigroups and monoids

Clear, exam-focused notes on semigroups, monoids and groups: definitions, basic laws and proofs, examples, worked problems, common mistakes and exam guidance.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Engineers use algebraic structure ideas when modelling composition of operations, combining states, and reasoning about reversible systems. Understanding semigroups, monoids and groups helps when working with string concatenation, function composition, modular arithmetic (useful in cryptography), permutation groups (useful in algorithms and error-correcting codes) and matrix operations (linear transforms).

Key ideas

Start from a set and a binary operation. We will define the three structures by which extra properties the operation satisfies.

  • Binary operation: A binary operation · on a set S is a rule that assigns to every ordered pair (a, b) in S × S a unique element a·b in S. The operation is assumed closed on S if this holds.

  • Semigroup: A set S with a binary operation · is a semigroup if the operation is closed and associative: for all a, b, c in S, (a·b)·c = a·(b·c). No identity or inverses are required.

  • Monoid: A semigroup (M, ·) is a monoid if there exists an element e in M such that for all a in M, e·a = a·e = a. Such an e is called an identity element (or neutral element). Monoid = semigroup + identity.

  • Group: A monoid (G, ·) is a group if every element has an inverse: for each a in G there exists b in G such that a·b = b·a = e, where e is the identity. Group = monoid + inverses for every element.

  • Abelian group: A group (G, ·) is abelian (or commutative) if for all a, b in G, a·b = b·a.

  • Order of a group: The order of a group G, written |G|, is the number of elements in G. If |G| is finite, G is a finite group; otherwise G is infinite.

  • Order of an element: The order of an element a in G is the smallest positive integer n such that a^n = e (where a^n means a·a·...·a, n times). If no such n exists, the order is infinite.

  • Subsemigroup / Submonoid / Subgroup: A nonempty subset H of S is a subsemigroup if it is closed under the operation (associativity is inherited from S). H is a submonoid if it is a subsemigroup and contains the identity of S. H is a subgroup if it is nonempty, closed under the operation, and for every a in H, a^{-1} ∈ H (equivalently, H ≠ ∅ and for all a, b in H, a·b^{-1} ∈ H).

  • Homomorphism: A map f : (G, ·) → (H, *) between two algebraic structures is a homomorphism if for all a, b in G, f(a·b) = f(a) * f(b). If f is bijective and a homomorphism, it is an isomorphism (structures are 'the same').

Key simple proofs and basic consequences (universities expect these step-by-step):

  1. Uniqueness of identity in a monoid

    Assume e and e' are both identity elements. Then e = e·e' = e'. So identity is unique.

  2. Uniqueness of inverse in a group

    If b and c are both inverses of a (so a·b = b·a = e and a·c = c·a = e), then b = b·e = b·(a·c) = (b·a)·c = e·c = c. So inverse is unique.

  3. Inverse of a product

    For a, b in a group G, show (a·b)^{-1} = b^{-1}·a^{-1}. Check: (a·b)·(b^{-1}·a^{-1}) = a·(b·b^{-1})·a^{-1} = a·e·a^{-1} = a·a^{-1} = e. Similarly on the other side.

  4. Cancellation law in groups

    If a·b = a·c then left-multiply by a^{-1} to get b = c. Similarly on the right. Cancellation holds in any group.

  5. Lagrange's theorem (statement only, with assumptions)

    If G is a finite group and H is a subgroup of G, then the order of H divides the order of G: |H| divides |G|. (Proof uses partition of G into left cosets of H; include full proof in exam answers.)

Examples and non-examples (explain simply):

  • (Z, +) — integers under addition: group, infinite, abelian. Identity 0, inverse of a is −a.
  • (Z_n, + mod n) — integers modulo n under addition: finite abelian group of order n. Identity 0; inverse of k is n−k (mod n).
  • (Z^+, +) — positive integers under addition: semigroup, because associative and closed, but has no identity (0 not included), so not a monoid.
  • (N_0, ·) with N_0 = {0,1,2,...} under multiplication: monoid if you consider identity 1 is included; 0 causes non-invertibility, so not a group. (Be careful: if your course defines N differently, state which variant you use.)
  • All n×n matrices over R under multiplication: form a monoid (associative, identity I_n). The subset of invertible matrices GL(n, R) is a group under multiplication.
  • The set of permutations on n objects S_n under composition: group of order n!, non-abelian for n ≥ 3.

Diagrams to draw in answers

  • To check a small finite group show its Cayley table (operation table). For Z_4 under addition mod 4: draw a 5×5 table (top row and left column labels 0,1,2,3), fill entries (i+j mod 4). This shows closure, identity row/column and inverses on the table.
  • To illustrate cosets: draw a set G as a large rectangle, mark H as a smaller disjoint blocks; then show left cosets aH partition G.

Formulas

a^n = a·a·...·a (n times) — for n ∈ Z^+; define a^0 = e and a^{-n} = (a^{-1})^n; unitless as algebraic symbol; used in groups for repeated product.

a^{-1}·a = a·a^{-1} = e — defines inverse; e is identity.

|G| — order (size) of group G; unitless; for finite groups |G| is a natural number, for infinite groups |G| denotes an infinite cardinal.

ord(a) = min{ n ∈ Z^+ : a^n = e } — order of element a; unitless; if no such n exists, ord(a) = ∞.

(a·b)^{-1} = b^{-1}·a^{-1} — inverse of a product, in any group.

If a·b = a·c then b = c — left cancellation in groups (requires existence of a^{-1}).

If H ≤ G then |H| divides |G| — Lagrange's theorem (applies when G finite).

Worked examples

Example 1 — Show (Z_6, + mod 6) is an abelian group

  1. Set: Z_6 = {0,1,2,3,4,5}. Operation: a + b computed mod 6.
  2. Closure: sum of two residues mod 6 is another residue mod 6.
  3. Associativity: inherited from integer addition: (a + b) + c ≡ a + (b + c) (mod 6).
  4. Identity: 0, because 0 + a ≡ a (mod 6).
  5. Inverses: for each a, inverse is 6 − a (mod 6). Check e.g., 4 + 2 ≡ 6 ≡ 0 (mod 6).
  6. Commutativity: a + b ≡ b + a (mod 6).

Therefore (Z_6, + mod 6) is a finite abelian group of order 6. Final answer: (Z_6, + mod 6) is an abelian group.

Example 2 — Prove uniqueness of inverse (model exam answer)

Given a group (G, ·), let a ∈ G. Suppose b and c are both inverses of a. Then a·b = e and a·c = e. Compute b = b·e = b·(a·c) = (b·a)·c = e·c = c. Thus b = c. Hence inverse of any element is unique.

Example 3 — Cayley table trace for Z_4 (add mod 4)

Draw 5×5 table. Top labels and left labels: 0,1,2,3. Fill cell (i,j) with (i+j) mod 4. Fill table entries explicitly: row 0: 0,1,2,3; row1:1,2,3,0; row2:2,3,0,1; row3:3,0,1,2. From the table: identity 0 (row and column same as labels), inverse of 1 is 3 etc. This verifies group axioms.

Common mistakes

  • Confusing 0 and 1 in monoid examples: be explicit whether N includes 0. Many students forget to state the identity element.
  • Forgetting to check closure explicitly for a proposed subset when claiming a subgroup.
  • Using Lagrange's theorem backwards: |H| dividing |G| does not imply H exists for every divisor of |G| (converse false in general).

For your exam

Kinds of questions: define terms (semigroup, monoid, group, abelian), give examples and non-examples, prove basic uniqueness theorems, compute Cayley tables, show a set with an operation is/is not a group, show the inverse of a product, apply Lagrange's theorem (state and use), and short proofs about cancellation or order of elements.

What full-mark answers include:

  • Precise definitions with the three axioms named (closure, associativity, identity/inverse where required).
  • Example concretely written with the set, the operation and identity/inverses given.
  • Step-by-step proofs (write each algebraic step and reason: associativity inherited, cancel by multiplying by inverse, etc.).
  • For finite examples, include Cayley table or explicit list of inverses.

Quick check

  1. Is (N_0, +) with N_0 = {0,1,2,...} a monoid, group, or semigroup? 2. In a group G, if a^3 = e and ord(a) is finite, what are the possible orders of a? 3. Compute inverse of product in S_3: if σ = (1 2 3) and τ = (1 2), what is (σ·τ)^{-1}?

Answers: 1. monoid (identity 0) but not a group. 2. order could be 1 or 3 (divisors of 3). 3. (σ·τ)^{-1} = τ^{-1}·σ^{-1}; here τ^{-1} = τ, σ^{-1} = (1 3 2), so (σ·τ)^{-1} = (1 2)·(1 3 2).

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?