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.