Copyright wordpress
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 to 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 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 because, .) 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. 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 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 and . Then there must exist an attempt in the chain with . Since it follows that does not contain , so we must have . Therefore, must be an initial segment of and we have with and . This is a contradiction. 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. 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.
