Imagine you are in one of those computer games where there is a wall of spikes coming from the left of the screen, so you are forced to proceed indefinitely until the level ends, always proceeding in the same direction. Suppose the level never ends: when can you escape? Zorn’s lemma asks, and answers, this question. Perhaps a little surprisingly it reveals that perversely however massively infinite and complicated your set is that the only possible means of escape you have is to dart down a hole that looks like the natural numbers, such that wherever the wall of spikes is there is always some amount of space to the right. If there are no such holes, then however stupidly huge the space in which you have to run, you eventually have no chance.

Sometimes Zorn is viewed as being a rather scary complicated theorem because it is equivalent to the axiom of choice. This is totally false: the axiom of choice (large cartesian products of nonempty sets are nonempty) is a really nonscary fact that is equivalent to the axiom of choice. What seems to make Zorn scary is that it gives really specific information about the structures of monstrously large sets, and there’s no way to prove it without first working out what it means to have a pursuit lasting many many infinities and then ending.

Let’s set up a little notation. Suppose we have a set X on which there is some partial order relation < (so for any pair of distinct elements a,b \in X it may be true that one of a<b or b<a holds, or neither could hold). Since we have to keep running to the right, we will be interested in subsets of X that are well ordered: of the form x_1<x_2<.... (where the subscripts could be members of any set, possibly much larger than the integers). We (perhaps slightly abusing standard usage) call such a set a chain.

We say that a chain is an escape tunnel if there is no m \in X such that for every element x in the chain, m \geq x. If there is an escape tunnel, we can trivially escape down it forever. The only interesting case is therefore when X doesn’t have any escape tunnels. It could perhaps be viewed as being a ‘closed’ set in some sense, but bear in mind that it could be absolutely huge, far bigger than anything we could ever visualise. Can we exploit this sheer hugeness to escape, without needing to cheat and run down an escape tunnel?

Well, let’s give it a shot. Suppose we find ourselves on some point x. If we are going to keep running, all we need is some x' such that x'>x. We then just keep going forever, and because our set is really big we can probably keep going. We try going for a while, and locally it looks like we are darting down an escape tunnel, but because there aren’t any escape tunnels, there is some m ahead of us and our planned route which at some point (possibly infinitely far away in the future) the wall of spikes will get to, so we must get there too. So we keep going ‘forever and a day’ in this way.

Ah, but wait a sec. Can a set X of any size support this kind of running forever? After all, a set does have a fixed cardinality. If we run for ages and ages and ages (starting at some point), we might be able to build an arbitrarily large well-ordered subset of X. But the size of such a subset is bounded: it can never be bigger than X.

And yet if we consider the set of well-orderings of subsets of X, and consider the set S of order-isomorphism classes represented, this is itself a well-ordered set, but cannot possibly be order-isomorphic to any of its elements. In other words, S is a well-ordering bigger than any possible on X.

Yet the set of well-ordering types up to and including S is itself well-ordered (1<2<3 is in some obvious sense smaller than 1<2<3<4<5), and if we keep running forever in our space X, our route is at some point bound to be long enough to be a copy of S. But this is impossible, because S is just too big. So at some point we get stuck at some point from which we cannot escape and die, even if X is really massive.

More formally, X has at least one maximal element (‘a point from which we cannot escape’).

There are bits of rigour missing from the argument above, and somehow without developing the dull bits of the theory of ordinals it’s impossible to fill in the gaps, but the intention of this post was to highlight that it’s somehow ultimately a result about really long pursuits in a large space, and that the proof is really not much more idea-wise than you need in the finite case (once you’ve had the idea of blocking off the escape tunnels).


Advertisements