Quick description
If you are building a mathematical object in stages and find that (i) you have not finished even after infinitely many stages, and (ii) there seems to be nothing to stop you continuing to build, then Zorn's lemma may well be able to help you.
Prerequisites
Basic concepts of undergraduate mathematics, such as vector spaces.
Example 1
A function from
to
is called additive if
for every
. Clearly any function of the form
is additive. Are there any other additive functions?
An easy induction shows that if then
for every positive integer
. (This is true with
, since
for every
.) It is also easy to prove that
(since e.g.
). And from this it follows that
, so
, for every positive integer
. Another easy induction shows that
for every real number
and every positive integer
. Therefore,
, from which it follows that
for every real number
and every positive integer
. From these observations it follows that if
then
for every rational number
.
At this point it seems to be hard to deduce anything about other values of . Indeed, there doesn't seem to be much obstacle to defining
to be anything we like. If we set
to be
, then an argument similar to the argument of the previous paragraph shows that
for every rational number
, but no number of the form
is rational except when
, so this is not going to conflict with the choices we have already made. We will of course be forced to set
to be
, but there is no problem in doing that.
Let us be slightly more explicit about why this isn't a problem: it is because if then
and
(since otherwise we would find that
, which is rational). This will enable us to see more clearly what is going on later.
The discussion so far strongly suggests that there should be a function that is additive but not of the form . We haven't yet defined one, since by no means every real number is of the form
with
and
rational. But we have produced a partially defined additive non-linear function, and the method we have used is rather flexible. Indeed, if we pick another number, such as
, say, where
is not yet defined, then we can extend the definition to all numbers of the form
with
by setting
for some arbitrarily chosen
.
More generally, we could construct a sequence of numbers with
, with the property that no
is a rational linear combination of
. And then we could define
, for arbitrarily chosen
, which would tell us that
for every sequence
of rational numbers.
The trouble is, even when we have built an infinite sequence in this way, we still haven't defined for all real numbers, since the set of rational linear combinations of those numbers is countable. However, we can still continue to build our function, since we can pick a new real number
that is not a rational linear combination of the
and choose a value for
. And then we can choose
that is not a rational linear combination of the
and
, and so on. But again we find that even if we produce an infinite sequence of
we have still defined
for only countably many real numbers.
A good way of regarding what we are doing is this: we are considering the real numbers as a vector space over the rationals, and we are trying to build a basis for this vector space, where this means a collection of real numbers such that every real number is a rational linear combination of numbers in
in precisely one way. Then if we define the values of
however we like for the numbers in
and define the values of
in the obvious way for rational linear combinations of those numbers, we have a function from
to
that is linear over the rationals, and hence additive, but not necessarily of the form
.
Now , considered as a vector space over
, is certainly infinite-dimensional. In fact, it has uncountable dimension. So does it have a basis? (All we mean by "has uncountable dimension" is "cannot be spanned by countably many vectors," so it is not true by definition that it has a basis.) Inspired by finite-dimensional vector spaces it is tempting to say, "Pick a maximal linearly independent set," since such a set is not just linearly independent but also spans the whole space, since if it didn't we could just pick an element that did not belong to its linear span and we could add it to the linearly independent set, contradicting maximality.
So now we seem to be done: we are looking for a basis of over
, and all we need to do to find a basis of any vector space is take a maximal linearly independent set.
But why should a maximal linearly independent set exist? Isn't that exactly the difficulty we were facing earlier: we could carry on picking more and more rationally independent real numbers but we never seemed to reach the point where we could no longer continue?
Let us now interrupt this example for a more general discussion of Zorn's lemma and how to use it.
General discussion
We are now in a very typical situation where Zorn's lemma can be applied. We would like to build a maximal object, and we feel as though we ought to be able to, because any non-maximal object can easily be extended. The usual statement of Zorn's lemma is as follows. A partially ordered set is a set together with an ordering
of the elements of
that is transitive and antisymmetric (this means that if
and
then
). A typical example is where
is a collection of sets and
if and only if
. (Here I use the symbol "
" to mean "is a subset of" and not "is a proper subset of".) A chain in a partially ordered set
is a totally ordered subset of
: that is, a subset
such that if
then either
or
. An upper bound for a subset
of a partially ordered set
is an element
such that
for every
. And a maximal element in a partially ordered set
is an element
such that the only element
with
is
itself. Zorn's lemma states that if
is a partially ordered set such that every chain in
has an upper bound, then
has a maximal element. (Note that a maximal element does not have to be bigger than everything else: it just mustn't be smaller than anything else.)
In order to see how this rather abstract-looking statement relates to the kind of problem we had earlier, let us imagine that we have a partially ordered set and are looking for a maximal element. We could try to build one as follows. We start with an element
. If it isn't maximal then we find a bigger element
. If that isn't maximal we find a bigger element
, and so on. That gives us an increasing sequence
. Now we seem to be stuck, and indeed sometimes we are stuck. For example, if
is the set of natural numbers with their usual ordering then we might have created the sequence
, which would not help us to find a maximal element — not surprisingly, since
doesn't have a maximal element.
However, does not satisfy the hypothesis of Zorn's lemma, because the sequence
is a chain with no upper bound. If
does satisfy this hypothesis then the sequence
, which is also a chain, has an upper bound, which we could call
. If this is not maximal, then we can find a larger element
. If that is not maximal, then we can find a yet larger element
, and so on.
Example 1, continued
Note the similarity between the position we are now in and the position we were in when we were trying to create a basis for over
. Once again, we can continue to create larger and larger objects, but there seems to be no easy way of saying that the process eventually ends. Or rather, there is an easy way: Zorn's lemma tells us that it ends.
Let us see how Zorn's lemma applies in our example. The objects we were looking at were subsets of that were linearly independent over
. We noted that a maximal linearly independent subset of
spanned the whole of
, where by "maximal" we meant that the set was not contained in any larger linearly independent set. Thus, we were looking at the set of all linearly independent subsets of
, with the partial order
.
All we have to do if we want to apply Zorn's lemma is check that every chain has an upper bound. So let us imagine that we have a collection of linearly independent subsets of
and that for any two of those sets one is contained in the other. What could serve as an upper bound? By definition it has to be a set that contains all the sets in
, so it has to contain their union. We want it to be linearly independent, so the smaller it is, the better. So there is basically only one candidate to try: the union itself. Is the union linearly independent? Well, if
belong to the union, then each
belongs to some linearly independent set
. Because
is a chain, one of these sets
contains all the others. If that is
, then the linear independence of
implies that no non-trivial linear combination of
can be zero, which proves that the union of the sets in
is linearly independent, just as we wanted. Therefore, by Zorn's lemma, there is a maximal linearly independent set. Earlier we observed that such a set was a basis and could be used to create additive functions not of the form
, so our problem is now solved.
Further general remarks
How, one might ask, is Zorn's lemma itself proved? One answer is that it cannot be proved: it is just an axiom. But a slightly more informative answer is that it is equivalent to the axiom of choice and the well-ordering principle. A hint of why this should be can be found in the attempted proof above. There we created an infinite sequence , which we then continued "transfinitely" with the elements
. This transfinite process can continue until a maximal element is reached, but to do so one needs to make infinitely many choices (since there isn't a way of defining the next element of the sequence). Thus, the axiom of choice comes into play. If we knew in advance that
could be well-ordered (that is, given a total ordering such that every non-empty subset had a minimal element), then we could build up the sequence by always taking the minimal element that worked. And it's an easy exercise to use Zorn's lemma to prove that every set has a well-ordering.
One should add that the above sketch of how to use the axiom of choice to prove Zorn's lemma may make the deduction look easier than it really is. In order to justify rigorously that the transfinite induction can continue, one must prove a result known as Hartog's lemma, which states that for every set there is an ordinal with the same cardinality as
. And Hartog's lemma is not a triviality.
Example 2
We asserted above that it was easy to deduce from Zorn's lemma that every set has a well-ordering. Let us justify this claim, since it gives another representative application of Zorn's lemma. Suppose, then, that we have a set and we would like to give it a well-ordering. That is, we would like to define a total ordering on the elements of
such that every non-empty subset
of
has a minimal element.
Once again, we find ourselves in a situation where there are no obvious constraints to building the object we require, other than the "transfinite length of time" needed to complete the process. We just pick an arbitrary element to be the minimal element of
itself, then an arbitrary element
to be the minimal element of
, and so on. In other words, at each stage we would like to choose an element not yet chosen and declare it to be the next element in our ordering.
To convert that rough idea into a Zorn's-lemma argument, we need to define a partial ordering on the set of "incomplete attempts" at defining a well-ordering on . An incomplete attempt means a subset
of
and a well-ordering of that subset. Let us define an attempt to be precisely that: a subset
of
with a well-ordering of the elements of
. The partial ordering on the set of all attempts should reflect the idea of one attempt extending another, so the obvious partial ordering to take is as follows: given two attempts
and
, we say that
if
is an initial segment of
. This means that
is a subset of
, that the ordering associated with
is the same as the ordering associated with
when you restrict it to
, and that every element of
is less than every element of
in the ordering on
.
Does this partially ordered set satisfy the chain condition? Well, if we have a chain of attempts, then we can define an upper bound to be the union of the sets in that chain, with the following ordering:
if there is some attempt
in the chain such that
and
both belong to
and
in
. This ordering is well-defined, because if
is another attempt that contains
and
, then either
or
(since
and
both belong to the chain), and the definition of
guarantees that the orderings on
and
are consistent.
Is the ordering on a well-ordering? Yes, since if
is a non-empty subset of
, then there must be an attempt
in the chain such that
is non-empty.♦ But then
has a minimal element
in
. This must be minimal in
as well.♦ To see why, suppose that
in
. Then there must exist an attempt
in the chain with
. If
then
does not contain
, so we must have
. But this is a contradiction, since
must then be an initial segment of
and we have
with
and
. Therefore,
, and since
is minimal in
we must have
.
We have now shown that is well-ordered, and thereby verified the chain condition. (Note that verifying the chain condition was fairly straightforward: this is true of many applications of Zorn's lemma.) Therefore, by Zorn's lemma, there is a maximal attempt, which we hope will be a well-ordering of the whole of
.
If it is not the whole of , then it is a well-ordering of some proper subset
of
. But we can easily extend this attempt: let
be any element of
and define
to be
, ordering
by taking the ordering we already have on
and stipulating in addition that
for every
. (Of course, we also stipulate that
.) This produces a larger attempt, contradicting the maximality of
. This contradiction completes the proof that (Zorn's lemma implies that) every set can be well-ordered.
Further general remarks
Note that the final step of the last argument, the proof that every maximal attempt must be a well-ordering of the whole of corresponds to the informal observation made earlier that we can keep on and on extending a well-ordering, while the verification of the chain condition corresponds to the fact that if we produce an infinite sequence of attempts then we can take their union and carry on. Again, this is typical of Zorn's-lemma arguments.
So how, in general, does one recognise the need for Zorn's lemma and how does one construct an appropriate partially ordered set in order to apply it? The clues are in the two examples above. Typically, one is trying to build a structure of some kind (such as a basis for a vector space, or a well-ordering of a set). The natural way to do it appears to be to build the structure up in stages, but there are too many stages for this to work straightforwardly. However, once one has an idea of what a stage is and what the building-up process is, one can wheel out Zorn's lemma to finish the job. The partially ordered set will consist of all objects that might conceivably be stages in the construction, and one of these objects will be smaller than another if it might conceivably come before the other in the building-up process. If the resulting partial order satisfies the chain condition and if a maximal element must be a structure of the kind one is trying to build, then the proof is complete.
Comments
The following seems like a
Thu, 09/04/2009 - 23:03 — alex (not verified)The following seems like a natural addition to this article: is every finitely additive probability measure on the integers countably additive? The answer could be a proof of the ultrafilter lemma by appealing to Zorn's lemma, which gives that the answer is no.
Inline comments
The following comments were made inline in the article. You can click on 'view commented text' to see precisely where they were made.
Problem with argument
Sun, 12/04/2009 - 20:34 — randomactsofmath (not verified)If V is any non-empty subset of U, does it follow that it must be an initial segment of some set W in the chain. This does not seem necessary. Does any non-empty subset of U have to contain the minimal element?
There is no assumption here
Tue, 14/04/2009 - 10:25 — gowersThere is no assumption here that
is an initial segment, but
is an initial segment, and if
is non-empty then
must contain the minimal element.
Inline comments
The following comments were made inline in the article. You can click on 'view commented text' to see precisely where they were made.
Identified a typo
Mon, 13/04/2009 - 00:02 — randomactsofmath (not verified)"This must be minimal in V as well " instead of "This must be minimal in U as well".
The claim here is that the
Tue, 14/04/2009 - 10:27 — gowersThe claim here is that the element
is a minimal element of
not just with respect to the ordering on
but also with respect to the ordering on 
How about the theorem that
Thu, 23/04/2009 - 00:44 — Zygmund (not verified)How about the theorem that ideals are contained in maximal ideals in rings with identities? That seems to be in the same spirit.
Or, the existence of minimal prime ideals.