Partial orders, Hasse diagrams, and lattices (intro)

A partial order is a binary relation ≤ on a set S that satisfies three axioms. These axioms formalize what it means for a comparison to be well-behaved, even when not all elements are comparable. The pair (S, ≤) is called a partially ordered set, abbreviated poset. When every pair of elements is comparable, the poset becomes a total order (or linear order), but in general a poset may contain incomparable pairs—elements a and b where neither a ≤ b nor b ≤ a holds.

1. Reflexivity For every element a ∈ S, we require a ≤ a. Every element is related to itself. This is the mildest axiom—it simply ensures that "≤" includes equality.

2. Antisymmetry If a ≤ b and b ≤ a, then a = b. Two distinct elements cannot each dominate the other; this prevents cycles (other than self-loops) and distinguishes partial orders from preorders.

3. Transitivity If a ≤ b and b ≤ c, then a ≤ c. Comparisons chain together. This axiom is the engine of deductive reasoning about order: if you know two links, you can infer the third.

4. Covering Relation We say b covers a (written a ≺ b) if a < b and there is no c with a < c < b. Covers are the "edges" of a Hasse diagram—the minimal steps in the order.

5. Incomparability Two elements a and b are incomparable (written a ∥ b) if neither a ≤ b nor b ≤ a. Incomparability is what makes partial orders strictly more general than total orders.

KEY TAKEAWAY: Think of a poset like a corporate org chart. Every person is comparable to those in their direct chain of command (reflexive, antisymmetric, transitive), but two managers in different departments may have no hierarchical relationship at all—they are incomparable. A total order would be a single unbranching chain of command where everyone reports to exactly one person above them.