Partial Ordering

What Is a Partial Order?

A partial order is a relation that is reflexive, antisymmetric, and transitive. Unlike total orders, not every pair of elements needs to be comparable.

Properties (poset):
  Reflexive:     a ≤ a
  Antisymmetric: a ≤ b and b ≤ a → a = b
  Transitive:    a ≤ b and b ≤ c → a ≤ c

Examples of Partial Orders

Subset relation (⊆):
  A ⊆ A ✓
  A ⊆ B and B ⊆ A → A = B ✓
  A ⊆ B and B ⊆ C → A ⊆ C ✓

Divisibility (|):
  a | a ✓
  a | b and b | a → a = b ✓
  a | b and b | c → a | c ✓
  Note: 2 and 3 are NOT comparable (neither divides the other)

Subset of a power set (⊆):
  Always a partial order on any collection of sets

Hasse Diagrams

A Hasse diagram is a simplified graph representation of a partial order. We remove self-loops, remove transitive edges, and draw elements upward.

Example: Divisibility on {1, 2, 3, 4, 6, 12}

        12
       /  \
      4    6
     / \  /
    2   3
     \ /
      1

Reading: 1 divides 2 and 3, 2 divides 4, 3 divides 6, etc.

Maximal, Minimal, Greatest, Least

Maximal:  An element with no element above it
Minimal:  An element with no element below it
Greatest (Maximum): An element ≥ all others
Least (Minimum):    An element ≤ all others

A poset may have multiple maximal/minimal elements
but at most one greatest/least element.