佐恩引理的使用方法

原文

I am continuing my series of sample articles for the Tricks Wiki with one that is intended to represent a general class of such articles. It is common practice in lecture courses (at least if the ones I attended as an undergraduate are anything to go by) to state useful theorems, lemmas, propositions, etc., without going to much trouble to explain why they are useful. Of course, there are many ways to pick up this further understanding: taking note of where and how such results are used, doing carefully designed exercises, and so on. Nevertheless, it is often the case that more could be done to help people recognise the signs that indicate that a particular result can be applied.

This article, which is principally aimed at undergraduates early on in a mathematics degree, is inspired by an experience I myself had as an undergraduate. I had a sheet of challenging problems (set by Béla Bollobás) and one of them completely stumped me. (I’m sure several of them stumped me but this is the one that sticks in my mind.) I can’t remember exactly what the question was, but it was something of similar difficulty to that of determining whether an additive function from $\mathbb{R}$ to $\mathbb{R}$ was necessarily linear. My supervision partner solved the problem using Zorn’s lemma, which we had been told about in a lecture, and I just sat there in disbelief because it hadn’t even remotely occurred to me that Zorn’s lemma might be useful. At some point in the intervening years, I “got” Zorn’s lemma and now find it straightforward to see where it is needed. This article is intended to speed up that process for other people.

One might argue that it is better to work out how to apply theorems for oneself. I’m in two minds about that. Probably for any individual theorem, if one works out for oneself how to recognise situations where it can be applied then that is better than being told by somebody else. But working it out can take quite a lot of time and effort, so if one has help then one may be able to learn how to apply more theorems, and one may be able to learn about theorems in branches of mathematics other than one’s own. On balance, I think that a series of articles on how to use various important mathematical principles would be a useful resource, one that I would love to have to help me understand better the many areas of mathematics where I feel shaky. So here’s a first attempt at Zorn’s lemma. So far I have only two examples of applications: at some stage it would be good to have several more.

Title: How to use Zorn’s lemma.

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 $f$ from $\mathbb{R}$ to $\mathbb{R}$ is called additive if $f(x+y)=f(x)+f(y)$ for every $x,y\in\mathbb{R}$ . Clearly any function of the form $f(x)=\lambda x$ is additive. Are there any other additive functions?

An easy induction shows that if $f(1)=\lambda$ then $f(n)=\lambda n$ for every positive integer $n$ . (This is because, $f(n+1)=f(n)+f(1)$ .) It is also easy to prove that $f(0)=0$ (since e.g. $f(0)=f(0)+f(0)$ ). And from this it follows that $f(n)+f(-n)=0$ , so $f(-n)=-\lambda n$ , for every positive integer $n$ . Another easy induction shows that $f(mx)=mf(x)$ for every real number $x$ and every positive integer $m$ . Therefore, $mf(x/m)=f(x)$ , from which it follows that $f(x/m)=f(x)/m)$ for every real number $x$ and every positive integer $m$ . From these observations it follows that if $f(1)=\lambda$ then $f(x)=\lambda x$ for every rational number $x$ .

At this point it seems to be hard to deduce anything about other values of $f(x)$ . Indeed, there doesn’t seem to be much obstacle to defining $f(\sqrt 2)$ to be anything we like. If we set $f(\sqrt 2)$ to be $\mu$ , then an argument similar to the argument of the previous paragraph shows that $f(x\sqrt 2)=\mu x$ for every rational number $x$ , but no number of the form $x\sqrt 2$ is rational except when $x=0$ , so this is not going to conflict with the choices we have already made. We will of course be forced to set $f(x+y\sqrt 2)$ to be $\lambda x+\mu y$ , 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 $x+y\sqrt 2=x'+y'\sqrt 2$ then $x=x'$ and $y=y'$ (since otherwise we would find that $\sqrt 2=(x'-x)/(y-y')$ , 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 $f(x)=\lambda x$ . We haven’t yet defined one, since by no means every real number is of the form $x+y\sqrt 2$ with $x$ and $y$ 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 $\pi$ , say, where $f$ is not yet defined, then we can extend the definition to all numbers of the form $x+y\sqrt 2+z\pi$ with $x,y,z\in\mathbb{Q}$ by setting $f(x+y\sqrt 2+z\pi)=\lambda x+\mu y+\nu z$ for some arbitrarily chosen $\nu$ .

More generally, we could construct a sequence of numbers $t_1,t_2,\dots$ with $t_1=1$ , with the property that no $t_n$ is a rational linear combination of $t_1,t_2,\dots,t_{n-1}$ . And then we could define $f(t_i)=\lambda_i$ , for arbitrarily chosen $\lambda_i$ , which would tell us that $f(t_1x_1+\dots+t_nx_n)=\lambda_1x_1+\dots+\lambda_nx_n$ for every sequence $x_1,\dots,x_n$ of rational numbers.

The trouble is, even when we have built an infinite sequence in this way, we still haven’t defined $f$ 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 $s_1$ that is not a rational linear combination of the $t_i$ and choose a value for $f(s_1)$ . And then we can choose $s_2$ that is not a rational linear combination of the $t_i$ and $s_1$ , and so on. But again we find that even if we produce an infinite sequence of $s_i$ we have still defined $f$ 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 $B$ of real numbers such that every real number is a rational linear combination of numbers in $B$ in precisely one way. Then if we define the values of $f$ however we like for the numbers in $B$ and define the values of $f$ in the obvious way for rational linear combinations of those numbers, we have a function from $\mathbb{R}$ to $\mathbb{R}$ that is linear over the rationals, and hence additive, but not necessarily of the form $f(x)=\lambda x$ .

Now $\mathbb{R}$ , considered as a vector space over $\mathbb{Q}$ , 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 $\mathbb{R}$ over $\mathbb{Q}$ , 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 $X$ together with an ordering $\leq$ of the elements of $X$ that is transitive and antisymmetric (this means that if $x\leq y$ and $y\leq x$ then $x=y$ ). A typical example is where $X$ is a collection of sets and $x\leq y$ if and only if $x\subset y$ . (Here I use the symbol “ $\subset$ ” to mean “is a subset of” and not “is a proper subset of”.) A chain in a partially ordered set $X$ is a totally ordered subset of $X$ : that is, a subset $Y$ such that if $y,z\in Y$ then either $y\leq z$ or $z\leq y$ . An upper bound for a subset $Y$ of a partially ordered set $X$ is an element $u$ such that $y\leq u$ for every $y\in Y$ . And a maximal element in a partially ordered set $X$ is an element $x_0$ such that the only element $x\in X$ with $x_0\leq x$ is $x_0$ itself. Zorn’s lemma states that if $X$ is a partially ordered set such that every chain in $X$ has an upper bound, then $X$ 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 $X$ and are looking for a maximal element. We could try to build one as follows. We start with an element $x_1$ . If it isn’t maximal then we find a bigger element $x_2$ . If that isn’t maximal we find a bigger element $x_3$ , and so on. That gives us an increasing sequence $x_1,x_2,\dots$ . Now we seem to be stuck, and indeed sometimes we are stuck. For example, if $X$ is the set of natural numbers with their usual ordering then we might have created the sequence $1,2,3,\dots$ , which would not help us to find a maximal element — not surprisingly, since $\mathbb{N}$ doesn’t have a maximal element.

However, $\mathbb{N}$ does not satisfy the hypothesis of Zorn’s lemma, because the sequence $1,2,3,\dots$ is a chain with no upper bound. If $X$ does satisfy this hypothesis then the sequence $x_1,x_2,x_3,\dots$ , which is also a chain, has an upper bound, which we could call $x_\omega$ . If this is not maximal, then we can find a larger element $x_{\omega+1}$ . If that is not maximal, then we can find a yet larger element $x_{\omega+2}$ , 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 $\mathbb{R}$ over $\mathbb{Q}$ . 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 $\mathbb{R}$ that were linearly independent over $\mathbb{Q}$ . We noted that a maximal linearly independent subset of $\mathbb{R}$ spanned the whole of $\mathbb{R}$ , 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 $\mathbb{R}$ , with the partial order $\subset$ .

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 $Y$ of linearly independent subsets of $\mathbb{R}$ 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 $Y$ , 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 $t_1,\dots,t_n$ belong to the union, then each $t_i$ belongs to some linearly independent set $L_i\in Y$ . Because $Y$ is a chain, one of these sets $L_i$ contains all the others. If that is $L_j$ , then the linear independence of $L_j$ implies that no non-trivial linear combination of $t_1,\dots,t_n$ can be zero, which proves that the union of the sets in $Y$ 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 $f(x)=\lambda x$ , 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 $x_1,x_2,x_3,\dots$ , which we then continued “transfinitely” with the elements $x_\omega,x_{\omega+1},x_{\omega+2},\dots$ . 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 $X$ 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.

Example 2: Let us justify this last statement, since it gives another representative application of Zorn’s lemma. Suppose, then, that we have a set $X$ and we would like to give it a well-ordering. That is, we would like to define a total ordering on the elements of $X$ such that every non-empty subset $Y$ of $X$ 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 $x_1$ to be the minimal element of $X$ itself, then an arbitrary element $x_2$ to be the minimal element of $X\setminus\{x_1\}$ , 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 $X$ . An incomplete attempt means a subset $Y$ of $X$ and a well-ordering of that subset. Let us define an attempt to be precisely that: a subset $Y$ of $X$ with a well-ordering of the elements of $Y$ . 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 $Y$ and $Z$ , we say that $Y\leq Z$ if $Y$ is an initial segment of $Z$ . This means that $Y$ is a subset of $Z$ , that the ordering associated with $Y$ is the same as the ordering associated with $Z$ when you restrict it to $Y$ , and that every element of $Y$ is less than every element of $Z\setminus Y$ in the ordering on $Z$ .

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 $U$ of the sets in that chain, with the following ordering: $u\leq u'$ if there is some attempt $Y$ in the chain such that $u$ and $u'$ both belong to $Y$ and $u\leq u'$ in $Y$ . This ordering is well-defined, because if $Z$ is another attempt that contains $u$ and $u'$ , then either $Y\leq Z$ or $Z\leq Y$ (since $Y$ and $Z$ both belong to the chain), and the definition of $\leq$ guarantees that the orderings on $Y$ and $Z$ are consistent.

Is the ordering on $U$ a well-ordering? Yes, since if $V$ is a non-empty subset of $U$ , then there must be an attempt $Y$ in the chain such that $V\cap Y$ is non-empty. But then $V\cap Y$ has a minimal element $v$ in $Y$ . This must be minimal in $U$ as well. To see why, suppose that $v'\in V\setminus Y$ and $v'< v$ . Then there must exist an attempt $W$ in the chain with $v'\in W$ . Since $v'\notin Y$ it follows that $Y$ does not contain $W$ , so we must have $Y\leq W$ . Therefore, $Y$ must be an initial segment of $W$ and we have $v'< v$ with $v'\in W\setminus Y$ and $v\in Y$ . This is a contradiction.

We have now shown that $U$ 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 $X$ .

If it is not the whole of $X$ , then it is a well-ordering of some proper subset $Y$ of $X$ . But we can easily extend this attempt: let $z$ be any element of $X\setminus Y$ and define $Z$ to be $Y\cup\{z\}$ , ordering $Z$ by taking the ordering we already have on $Y$ and stipulating in addition that $y\leq z$ for every $y\in Y$ . (Of course, we also stipulate that $z\leq z$ .) This produces a larger attempt, contradicting the maximality of $Y$ . 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 $X$ , 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.

This entry was posted on August 12, 2008 at 1:25 pm and is filed under Mathematical pedagogy, Mathematics on the internet. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

佐恩引理的使用方法 How to Use Zorn's Lemma (2008)

佐恩引理的使用方法
How to Use Zorn's Lemma (2008)