Partial Orders and Lattices

Partial orders

A relation that is reflexive, antisymmetric and transitive is a partial order, and a set with a partial order is a poset, written (A, ≤). Examples: (ℤ, ≤), (P(S), ⊆), and the positive integers under divisibility (a | b).

"Partial" means two elements may be incomparable: neither 2 | 3 nor 3 | 2. If every pair is comparable, the order is total (a chain); a set of pairwise incomparable elements is an antichain.

Hasse diagrams

A Hasse diagram draws a poset compactly: draw a line upward from a to b when b covers a (a < b with nothing strictly between). Reflexive loops and lines implied by transitivity are left out.

The divisors of 12 under divisibility, D₁₂ = {1, 2, 3, 4, 6, 12}, have the cover relations 1–2, 1–3, 2–4, 2–6, 3–6, 4–12 and 6–12:

Special elements

For a poset (A, ≤) and a subset B:

In the divisibility order, a ∨ b = lcm(a, b) and a ∧ b = gcd(a, b). In (P(S), ⊆), the join is union and the meet is intersection.

Lattices

A poset is a lattice if every pair of elements has both a lub and a glb. Every finite lattice has a greatest and a least element.

In a distributive lattice, a complement, when it exists, is unique. A lattice is non-distributive exactly when it contains one of two five-element sublattices: the "diamond" M₃ or the "pentagon" N₅.

Divisor lattices

Dₙ (the divisors of n under divisibility) is always a distributive lattice. It is complemented, and therefore Boolean, exactly when n is square-free (no prime appears twice in n). In D₁₂, the element 2 has no complement: a complement x would need gcd(2, x) = 1, so x is odd (1 or 3), but then lcm(2, x) is 2 or 6, never 12.

from math import gcd

def divisors(n):
    return [d for d in range(1, n + 1) if n % d == 0]

def hasse_edges(n):
    D = divisors(n)
    return [(a, b) for a in D for b in D
            if a != b and b % a == 0 and not any(c not in (a, b) and c % a == 0 and b % c == 0 for c in D)]

def complemented(n):
    lcm = lambda a, b: a * b // gcd(a, b)
    return all(any(gcd(a, b) == 1 and lcm(a, b) == n for b in divisors(n)) for a in divisors(n))

for n in [12, 30, 36, 105]:
    print(f"D{n}: {len(divisors(n))} elements, {len(hasse_edges(n))} Hasse edges, complemented: {complemented(n)}")

D12: 6 elements, 7 Hasse edges, complemented: False
D30: 8 elements, 12 Hasse edges, complemented: True
D36: 9 elements, 12 Hasse edges, complemented: False
D105: 8 elements, 12 Hasse edges, complemented: True

D₃₀ (30 = 2 · 3 · 5) and D₁₀₅ (105 = 3 · 5 · 7) are Boolean: their Hasse diagrams are cubes, with 8 elements and 12 edges, just like the subsets of a 3-element set.

Practice questions