display | more...

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.

• 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.

Here is another take on the subject...

# Wtf is a partial order, or a total order for that matter?

I'm glad you asked. See, some things can be ordered. Sue is taller than Jordi. My love is deeper than the ocean. Five is larger than two. Six divides forty-two. But then again, not everything can be ordered. What is greener, the linoleum pattern in the kitchen floor or the sky? Who divides whom between three and five?

When everything can be compared to everything else, then you have a total order When you have instead a set of things of which some are comparable but others are not, then you have a partial order. The examples of partial orders that mathematicians like are divisibility in the integers and inclusion between sets. They like them because they allow pretty lattice diagrams:

```                   24
|
12
/  \
4    6
\  / \
2   3

Fig. 1 - Divisibility lattice diagram
```

This is a lattice diagram showing a partial order between 2, 3, 4, 6, 12, and 24, where the partial order is given by divisibility. That is, following the lines up indicate that whatever is below the line divides whatever is on top of the line. The neat thing is that you can follow paths in the lattice diagram and get a chain of true statements. E.g. "2 divides 6, and 6 divides 12 so 2 divides 12." This is because order relations have to be transitive. That is, if in an order relation, A is less than B and B is less than C, then it must be the case that A is less than C too. Observe that this is indeed a partial order.

One more lattice diagram, this time for set inclusion:

```
{A, B, C}
/   |     \
/    |      \
{A,B}  {A,C}   {B,C}
| \/      \/   |
| /\      /\   |
|/  \    /  \  |
{A}    {B}    {C}
\     |     /
\    |    /
\   |   /
{ }
Fig. 2 - Inclusion lattice diagram

```

Here, following the lines up the lattice diagram gives you that the set one the bottom end of the line is contained in the set on the top end.

Both of these examples are partial orders. Now, sometimes you may want to extend them to a total order. That is, you need to define ways to compare things that are not comparable under the partial order in such a way that it preserves their relationship under the partial order. This is called extending the partial order to a total order.

It is clear how to do this with the integers under divisibility. Since m divides n only when m is smaller than n, then you can compare integers by their size instead of by their divisibility properties. In this way, you can subsume the partial order of divisibility under the total order of size of integers. It is not so clear how to arrange the sets in a total order while preserving their order structure under inclusion. Should we have that {A} is larger than {B} or that {B} is larger than {A}? A little thought that this problem too can be solved. You can order all sets of different sizes by saying that set X is larger than set Y if set X has more elements than set Y. Sets of the same size can be ordered arbitrarily. Say, {A} is less than {B} is less than {C}. It is easy to see that this preserves the partial order of inclusion, and it does define a total order on sets.

Well, after these two relatively mild examples, we want to know if we can always do this. That is, given any partial order, can we always extend it to a total order, never mind how, but can we do it? The answer is yes... provided you assume a delicate axiom of set theory, the axiom of choice.

# Choice, eh?

Yes, choice. That means infinite sets.

The real issue here isn't for finite partial orders like the lattice diagrams that I drew above. That's the "easy" case. You only need to make finitely many choices. If you take two elements x and y in your set which aren't already comparable, then you need to decide which of the two is bigger. A way to do this (and the basic idea behind topological sort) is to arrange all elements in a lattice diagram by height, where "height" is established by the level in the lattice diagram at which the element appears. For example, in the divisibility lattice diagram, 24 is at height 4 and 6 is at height 2; in the set inclusion diagram, height happens to coincide with the number of elements in the set (plus one, since the empty set with zero elements is at height one, Dijkstra eat your heart out). Anything at the same level can be ordered arbitrarily, from left to right, and all lower levels must be smaller than higher levels. I think it's visually clear that this works (but if it isn't, let me know, and I'll try to explain this again).

Actually, we needn't be as specific as this. When we find two elements that aren't already compared in our lattice diagram (e.g. 3 and 4 in the divisibility diagram), we can define the comparison between them to be whatever we want. Can we say that 3 is bigger than 4? Sure. We only need to be careful to note that this also defines a lot of other comparisons by transitivity, though. In effect, what it does is to collapse the lattice diagram into a line:

```                       24
|
12
|
6
|
3
|
4
|
2
Fig. 3 - A collapsed lattice diagram
```

How did this one choice collapse the entire partial order into a total order? (And observe that it is a valid order, since nothing is divided by something above it in the list.) The answer is that transitivity of the partial order forces this. Since 3 is now larger than 4 and 6 was larger than 3 to begin with (by divisibility) then 6 must now be larger than 4 too by transitivity. Turning to the set inclusion diagram, let's collapse it a bit by declaring that {C} is larger than {A,B}. Then the diagram looks like so:

```                   {A, B, C}
/        \
{A,C}      {B,C}
\       /
\     /
{C}
|
{A,B}

/    \
{A}    {B}
\    /
{ }

Fig. 4 - Another collapsed lattice diagram
```

Two more arbitrary choices are required to completely collapse this lattice diagram into a straight line, into a total order. Namely, we would need to decide which one should be bigger between {A} and {B} and also decide which one is bigger between {A,C} and {B,C}. The fact that we can always make these arbitrary choices as long as we stick to whatever consequences those choices entail by transitivity in order is something I shall now restate as a lemma.

Lemma: Let X and Y be elements in a partial order such that X and Y are not comparable under the partial order. It is then possible to define a comparison between X and Y arbitrarily, either X > Y or X < Y, but this choice may force other order comparisons that were not in the original partial order. The expanded order relation is still a partial order, possibly a total order.

Proof: Without loss of generality, suppose that X and Y were not comparable but then we defined X < Y, the case X > Y being entirely analogous. We need to check that defining X < Y doesn't cause any contradictory relation in our partial order. Suppose that it did. Now, defining X < Y also entails that for any Z such that Y < Z then also X < Z, by transitivity. For there to be a contradiction, it would need to be the case that originally X > Z, but then this would mean that X > Z > Y meaning that originally X > Y to begin with, i.e. X and Y were already comparable and we weren't free to define a comparison on them. The case of a contradictory relationship on the other side, if instead Z < X, entailing that Z < Y but originally Y < Z also entails that Y < X, meaning again that X and Y were already comparable to begin with. Thus, neither of these cases is possible and we are free to define new order relations on our partial order without breaking anything.

It is clear that we still have a partial order when X < Y, if we specifically include new order relations besides X < Y that are required by transitivity. We may possibly run out choices in which case we would have a total order.

This lemma shows that it's trivial to extend a finite partial order to a total order. Just take any two elements that aren't comparable, define whatever comparison you want with them, and all the other comparisons that this new definition entails. This will collapse your lattice diagram partially, and if it still isn't totally collapsed into a straight line, then do it again; define order arbitrarily on whatever isn't ordered, etc. For finite sets, we will only need to do this finitely many times, and we'll have our total order.

But what about infinite sets?

# Yeah, what about infinite sets?

Well, for infinite sets, we may need to make infinitely many arbitrary choices. This is why we would need the axiom of choice. I am almost tempted to say, "axiom of choice, QED", but I'm going to be a bit more formal than that and actually show specifically how to use the axiom of choice. Well, no, I lied a little. I won't use the axiom of choice, but rather an equivalent formulation of it that helps in these contexts: Zorn's Lemma.

Let X be a set. Recall that a chain on X is a bunch of elements of X given in increasing order. Zorn's lemma says that if you have a set X such that every (infinite) chain in X has an upper bound in X, then X contains a maximal element (i.e. an element that has nothing larger than it in X).

To apply Zorn's lemma in our case, we need to define our set X, an order relation on X, and prove that every chain in X has an upper bound. Let Y be any other set.

• I define X to be the set of partial orders on Y.
• I define X to be ordered by set-theoretic inclusion. Since a partial order is a set of order comparisons, this defines one partial order a to be larger than another partial b if a contains all of the order comparisons of b (and then some, possibly).
• For any chain a1 < a2 < ... of partial orders in X, I define a to be the union of all these partial orders. We need to prove that a is again a partial order. This is clear, since all comparisons in a exist at some level ai where they follow the rules of a partial order because ai is a partial order. Also, since every ai is contained in the union a, by definition of the order relation on the partial orders X, ai < a. This means that a is an upper bound for this chain.

By Zorn's lemma, X has a maximal element m. We finally need to prove that m is a total order on Y. This is easy, because if there were two elements x and y in m that weren't comparable, then we could define an arbitrary comparison x < y and add that comparison to m, making m bigger, and contradicting the fact that m was maximal (i.e. there was nothing bigger than m in X).

So there you have it. Zorn's lemma lets us make infinitely many arbitrary choices and extend a partial order to a total order. Now I feel content in proclaiming QED.

# So is this"considerably shorter" than ariels' proof?

Erm, perhaps no, because I was trying to explain too much. Let me just rewrite the entire proof in a more austere style:

Theorem: Every partial order x on a set Y can be extended to a total order.

Proof: Let X be the set of all partial orders on Y that contain x; X itself ordered by set-theoretic inclusion. For any chain C in X, define a to be the union of all elements in C. Clearly a is an upper bound for C, and a is itself a partial order, since all order comparisons in a exist at some level of the chain C. Thus, a is in X. By Zorn's lemma, X contains a maximal element m. Also, m contains x since m is in X, and m is a total order, for if it were missing a comparison, we could increase m by adding that comparison. QED.

Log in or register to write something here or to contact authors.