This writeup does assume you know about partial orders and total orders. If you don't -- not to worry, it's really short and simple.
Theorem. Every partial order can be extended to a total order. That is: Suppose → is a partial order on a set X. Then there exists a total order ⇒ on X that extends → as a relation:
- If x,y∈X and x→y, then x⇒y.
Proof.
-
When X is finite, we can just point at an algorithm that does the job. The topological sort is such an algorithm (it's even reasonably efficient).
-
Now suppose X is infinite. This case requires some strong axiom like the axiom of choice (slightly weaker axioms will also do the job), or an equivalent such as Zorn's lemma. But we'll just use a consequence, the compactness theorem for first-order logic. It's less well-known, and considerably shorter.
Consider the language of orders on X: This has as constants all elements of X and a 2-place relation (predicate) a<b "a comes before b". A partial order on X is a model of the relevant axioms for a partial order, and a total order on X is a model of the relevant axioms for a total order.
Create the set
Φ = { ∀x.∀y. x<y → ~(y<x),
∀x.∀y.∀z. x<y & y<z → x<z,
∀x.∀y. x<y | x=y | y<x } ∪
{ a<b | a,b∈X, a→b }
Note that the first set in the union is the total order axioms, and the second set just lists the entire partial order.
For any finite subset F⊆Φ we immediately see that F is satisfiable and has a model! Just take all elements of X'⊆X appearing in F (there will be finitely many) and extend the partial order → on X' to a total order ⇒ on X' using the topological sort algorithm.
By the compactness theorem for first-order logic, Φ is satisfiable and has a model. Consider the ordering on X inside this model. It is a total ordering, since it satisfies the axioms of total ordering. And it extends →, because whenever a→b it satisfies that a<b.
QED.