Partial Orders & Lattices

A relation on A is a partial order if it is reflexive, antisymmetric and transitive. The pair (A, ≼) is a partially ordered set (poset).

Examples:

• (ℤ, ≤) — the usual order.
• (ℤ⁺, |) — divisibility.
• (P(S), ⊆) — subsets ordered by inclusion.

In a partial order, some pairs may be incomparable: neither 2 | 3 nor 3 | 2. If every pair is comparable, it is a total (linear) order — like ≤ on numbers.

#Hasse diagrams

A Hasse diagram draws a poset compactly:

1. Draw smaller elements lower, so arrows always point up (and are dropped).
2. Omit self-loops (reflexivity is assumed).
3. Omit edges implied by transitivity: draw a → b only if b covers a (nothing in between).

#Special elements

For a poset (A, ≼) and a subset S:

In the divisors of 12: least element 1, greatest element 12. For S = {4, 6}: upper bounds {12}, so lub = 12; lower bounds {1, 2}, so glb = 2. For divisibility, lub = LCM and glb = GCD.

from math import gcd

D = [d for d in range(1, 13) if 12 % d == 0]
leq = lambda a, b: b % a == 0                     # a divides b
def lub(x, y): return min(u for u in D if leq(x, u) and leq(y, u))    # smallest common multiple in D
def glb(x, y): return max(l for l in D if leq(l, x) and leq(l, y))    # largest common divisor in D

print("divisors of 12:", D)
print("lub(4, 6) =", lub(4, 6), "  lcm =", 4 * 6 // gcd(4, 6))
print("glb(4, 6) =", glb(4, 6), "  gcd =", gcd(4, 6))
print("covering pairs (Hasse edges):",
      [(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)])

divisors of 12: [1, 2, 3, 4, 6, 12]
lub(4, 6) = 12   lcm = 12
glb(4, 6) = 2   gcd = 2
covering pairs (Hasse edges): [(1, 2), (1, 3), (2, 4), (2, 6), (3, 6), (4, 12), (6, 12)]

#Lattices

A poset is a lattice if every pair of elements has both a least upper bound and a greatest lower bound.

• (Divisors of n, |) is a lattice (join = lcm, meet = gcd).
• (P(S), ⊆) is a lattice (join = ∪, meet = ∩).
• A poset with two maximal elements and nothing above them is not a lattice.

#Topological sorting

Every finite poset can be extended to a total order that respects it: repeatedly remove a minimal element. This is exactly topological sorting of a DAG — see Graph Algorithms.