Szpilrajn extension theorem

Remarks

For a finite set, take a minimal element of $X$, put it first, and repeat with the remaining elements; this is topological sorting. For an infinite set, apply Zorn's lemma to the set of partial orders on $X$ that contain $\le$, ordered by inclusion. A maximal such order is total: if $a$ and $b$ were incomparable in it, adding the pairs $(u, v)$ with $u \preceq a$ and $b \preceq v$ would give a strictly larger partial order. The same argument shows more: if $a$ and $b$ are incomparable for $\le$, then some linear extension puts $a$ before $b$. Hence $\le$ is the intersection of all its linear extensions. Example: the divisibility order on $\set{1, 2, 3, 6}$ has the linear extensions $1, 2, 3, 6$ and $1, 3, 2, 6$, and $2$ and $3$ are incomparable because they appear in both relative orders.

Going deeper

For a student

The theorem is what makes the order dimension of a poset well defined: the set of all linear extensions realizes the order. For finite posets the proof is an algorithm, and counting the linear extensions is a central problem of order combinatorics. For infinite sets the proof uses the axiom of choice through Zorn's lemma.