Posets, Lattices, Boolean Algebra and Groups — Hasse Diagrams, LUB/GLB and Algebraic Structures

This lesson covers the "structures" part of discrete maths: ways to order things that aren't simply in a line (task dependencies, versions, sets), and sets with operations that behave nicely (the algebra behind cryptography, error-correcting codes and circuits). These topics are regular in GATE and university papers.

1. Partially ordered sets (posets)

A partial order ≤ on a set is reflexive, antisymmetric and transitive (lesson 1). "Partial" because some pairs may be incomparable.

Examples: "divides" on {1, 2, 3, 4, 6, 12}; ⊆ on subsets; "must finish before" on tasks. With "divides", 4 and 6 are incomparable (neither divides the other).

A total order (chain) compares every pair — like ≤ on numbers.

2. Hasse diagrams

Draw the poset without clutter:

• put smaller elements lower;
• draw an edge only for covering relations (a < b with nothing in between);
• omit self-loops and edges implied by transitivity.

D = [1, 2, 3, 4, 6, 12]
leq = lambda a, b: b % a == 0          # a "divides" b

covers = [(a, b) for a in D for b in D
          if a != b and leq(a, b) and not any(c not in (a, b) and leq(a, c) and leq(c, b) for c in D)]
print("Hasse edges:", covers)
print("incomparable pairs:", [(a, b) for i, a in enumerate(D) for b in D[i + 1:] if not leq(a, b) and not leq(b, a)])

Hasse edges: [(1, 2), (1, 3), (2, 4), (2, 6), (3, 6), (4, 12), (6, 12)]
incomparable pairs: [(2, 3), (3, 4), (4, 6)]

3. Special elements and bounds

Maximal ≠ greatest: in {2, 3, 4} under divides, 3 and 4 are both maximal, but there's no greatest element.

4. Lattices

A lattice is a poset in which every pair has both a LUB and a GLB. Divisors of n under "divides" always form a lattice (join = lcm, meet = gcd). The power set under ⊆ is a lattice (join = ∪, meet = ∩).

from math import gcd

D = [1, 2, 3, 4, 6, 12]
lcm = lambda a, b: a * b // gcd(a, b)
print("join(4, 6) = lcm =", lcm(4, 6), "| meet(4, 6) = gcd =", gcd(4, 6))
print("is a lattice:", all(lcm(a, b) in D and gcd(a, b) in D for a in D for b in D))

S = [1, 2, 3, 4, 6]          # remove 12: is it still a lattice?
print("without 12 is a lattice:", all(lcm(a, b) in S for a in S for b in S), "(4 and 6 have no join)")

join(4, 6) = lcm = 12 | meet(4, 6) = gcd = 2
is a lattice: True
without 12 is a lattice: False (4 and 6 have no join)

Special lattices you'll meet: bounded (has top and bottom), distributive, complemented (every element a has a′ with a ∨ a′ = top and a ∧ a′ = bottom). A lattice that is both distributive and complemented is a Boolean algebra — the power set of a set is the classic example, and Boolean algebra of bits (∨ = OR, ∧ = AND, ′ = NOT) is the foundation of digital circuits (COA track).

5. Algebraic structures

A set with an operation *:

Examples:

• (strings, concatenation) → monoid (identity = empty string; no inverses).
• (integers, +) → abelian group (identity 0, inverse −a).
• ({0, 1, 2, 3, 4}, + mod 5) → abelian group.
• ({1, 2, 3, 4}, × mod 5) → abelian group (5 is prime, so every element has an inverse).
• ({1, 2, 3}, × mod 4) → not closed (2 × 2 = 0).

Let's check the group axioms automatically:

from itertools import product

def check(S, op):
    closure = all(op(a, b) in S for a, b in product(S, S))
    assoc = closure and all(op(op(a, b), c) == op(a, op(b, c)) for a, b, c in product(S, S, S))
    identity = next((e for e in S if all(op(e, a) == a == op(a, e) for a in S)), None)
    inverses = identity is not None and all(any(op(a, b) == identity for b in S) for a in S)
    commutative = all(op(a, b) == op(b, a) for a, b in product(S, S))
    kind = ("abelian group" if inverses and commutative else "group" if inverses else
            "monoid" if identity is not None and assoc else "semigroup" if assoc else "not even a semigroup")
    return f"closed={closure} identity={identity} -> {kind}"

print("Z5 under + mod 5   :", check([0, 1, 2, 3, 4], lambda a, b: (a + b) % 5))
print("{1..4} under x mod 5:", check([1, 2, 3, 4], lambda a, b: a * b % 5))
print("{0..3} under x mod 4:", check([0, 1, 2, 3], lambda a, b: a * b % 4))
print("{1,2,3} under x mod 4:", check([1, 2, 3], lambda a, b: a * b % 4))

Z5 under + mod 5   : closed=True identity=0 -> abelian group
{1..4} under x mod 5: closed=True identity=1 -> abelian group
{0..3} under x mod 4: closed=True identity=1 -> monoid
{1,2,3} under x mod 4: closed=False identity=1 -> not even a semigroup

6. Cyclic groups and subgroups

• Order of a group = number of elements; order of an element a = smallest k with aᵏ = identity.
• A group is cyclic if one element (a generator) produces all elements by repeated operation. (Z₅, +) is cyclic, generated by 1 (or 2, 3, 4).
• Lagrange's theorem: the order of any subgroup divides the order of the group. So a group of prime order has no non-trivial subgroups and is cyclic.

These ideas power cryptography: Diffie–Hellman key exchange and elliptic-curve crypto (used in UPI and HTTPS) work inside large cyclic groups.

Common mistakes

• Drawing transitive edges in a Hasse diagram.
• Confusing maximal (nothing above) with greatest (above everything).
• Calling a monoid a group without checking that every element has an inverse.
• Forgetting to check closure first.

Quick recap

• Poset = reflexive + antisymmetric + transitive; Hasse diagram shows only covering edges.
• LUB = join, GLB = meet (for divisibility: lcm and gcd); lattice = every pair has both.
• Boolean algebra = complemented distributive lattice.
• Semigroup ⊂ monoid ⊂ group ⊂ abelian group (closure, associativity, identity, inverses, commutativity).
• Cyclic groups have a generator; Lagrange: subgroup order divides group order.