Quick description
Cantor's continuum hypothesis is perhaps the most famous example of a mathematical statement that turned out to be independent of the Zermelo-Fraenkel axioms. What is less well known is that the continuum hypothesis is a useful tool for solving certain sorts of problems in analysis. It is typically used in conjunction with transfinite induction. This article explains why it comes up.
Example 1
Given two infinite sets and of positive integers, let us say that is sparser than if the ratio of the size of to the size of tends to zero as tends to infinity. The relation "is sparser than" is a partial order on the set of all infinite subsets of . Is there a totally ordered collection of sets (under this ordering) such that every infinite subset of contains one of them as a subset?
Let us see how to solve this question rather easily with the help of transfinite induction and the continuum hypothesis. These two techniques take us as far as the first line of the proof, after which a small amount of work is necessary. But here is the first line that gets us started. By the well-ordering principle we can find a one-to-one correspondence between the set of all infinite subsets of and the first ordinal of cardinality . By the continuum hypothesis, this is also the first uncountable ordinal. Therefore,
Let us well-order the infinite subsets of in such a way that each one has countably many predecessors.
Once we have written this, we are well on the way to a just-do-it proof. Let us build a collection of sets that is totally ordered (and in fact well-ordered) by the sparseness relation, and let us take care of each infinite subset of in turn. For each countable ordinal let us write for the infinite subset of that we have associated with . Now let be a countable ordinal and suppose that for every we have chosen a subset , and suppose that we have done this in such a way that whenever the set is sparser than the set . We would now like to find a subset of that is sparser than every single with .
Because there are only countably many sets with , it is straightforward to do this by means of a diagonal argument. Here is one way of carrying it out. For each , let be the function from to that takes to the th element of . Now enumerate these functions as , define a diagonal function by taking to be the smallest element of that is larger than both and . Then let . Then if , we know that for each that corresponds to one of the functions . This proves that is sparser than every with . Therefore, we can construct a collection of infinite sets , one for each countable ordinal , such that is sparser than whenever , and for every . This completes the proof.
General discussion
What are the features of this problem that made the continuum hypothesis an appropriate tool for solving it? To answer this, let us imagine what would have happened if we had not used the continuum hypothesis. Once we had decided to solve the problem in a just-do-it manner, we would have well-ordered the subsets of , and tried, as above, to find a subset for each , with these subsets getting sparser and sparser all the time. But if the number of predecessors of some had been uncountable, then we would not have been able to apply a diagonal argument.
So the feature of the problem that caused us to want to use the continuum hypothesis was that we were engaging in a transfinite construction, and in order to be able to continue we used some result that depended on countable sets being small. In this case, it was the result that for any countable collection of sets there is a set that is sparser than all of them, but it could have been another assertion about countability, such as that a countable union of sets of measure zero has measure zero.
There is sometimes an alternative to using the continuum hypothesis, which is to use Martin's axiom. Very roughly speaking, Martin's axiom tells you that the kinds of statements one likes to use about countable sets, such as that a countable union of sets of measure zero has measure zero, continue to be true if you replace "countable" by any cardinality that is strictly less than . For example, it would give you a strengthening of the Baire category theorem that said that an intersection of fewer than dense open sets is non-empty. If the continuum hypothesis is true, then this is of course not a strengthening, but it is consistent that Martin's axiom is true and the continuum hypothesis false.
Example 2
A special case of Fubini's theorem is the statement that if is a bounded measurable function defined on the unit square , then . That is, to integrate , one can first integrate over and then over , or first over and then over , and the result will be the same in both cases.
One might ask whether it is necessary for to be measurable. Perhaps it is enough if is a measurable function of for fixed and vice versa, and that the functions and are measurable as well. That would be enough to ensure that both the double integrals and exist.
If you try to prove that these two double integrals are equal under the weaker hypothesis, you will find that you do not manage. So it then makes sense to look for a counterexample.
An initial difficulty one faces is that the properties that this counterexample is expected to have are somewhat vague: we want a function of two variables such that certain functions derived from it are measurable. But this measurability is a rather weak property, so it doesn't give us much of a steer towards any particular construction. This is just the kind of situation where it is a good idea to try to prove a stronger result. For example, instead of asking for to be bounded, we could ask for it to take just the values and . And instead of asking for the two double integrals to be different, we could ask for something much more extreme: that for every and for every . (Note that if we can do this, then we will easily be able to calculate the two double integrals. Note also that we won't have to think too hard about making non-measurable: that will just drop out from the fact that Fubini's theorem doesn't apply.)
If takes just the values and , then we could let . Then the condition we are aiming for is that for every the set has measure 0 and for every the set has measure 1.
It is at this point that we might think of using transfinite induction. Let us well-order the interval and try to ensure the above conditions one number at a time.
Suppose then that each real number in has been indexed by some ordinal and write for the real number indexed by . Suppose that for each we have decided what the cross-sections and are going to be. And suppose that we have done this in such a way that always has measure 0 and always has measure 1. Now we would like to choose the cross-sections and with the same property.
We do not have complete freedom to do this, since we have already decided for each whether belongs to and whether belongs to . And this could be a problem: what if the set is not a set of measure zero?
But we can solve this problem by ensuring that initial segments of the well-ordering of do have measure zero. How do we do this? We use the continuum hypothesis. Once again, we make the first line of our proof the following:
Well-order the closed interval in such a way that each element has countably many predecessors.
If we do this, then we find that for each we have made only countably many decisions about which points and belong or do not belong to . Therefore, we can decide about the rest of the points as follows: for every such that the value of is not yet assigned, set it to be , and for every such that the value of is not yet assigned, set it to be . This guarantees that for all but countably many , an for all but countably many . Therefore, for every we have and .
General discussion
If we look at the function that we have just defined, then we see that it has the following simple description. If in the well-ordering we placed on then and if in this well-ordering then . We could have omitted most of the above discussion and simply defined in this way in the first place, pointing out that for each , for all but at most countably many , and for each , for all but at most countably many . The point of the discussion was to show how this clever example can arise as a result of a natural thought process.
However, it is also worth remembering the example, since it gives us a second quite common way of using the continuum hypothesis. To clarify this, let us summarize the two ways we have discussed.
Method 1. In a proof by transfinite induction on a set of cardinality , start with the line, "Let be a well-ordering of such that every element has countably many predecessors," or equivalently, "Take a bijection between and the first uncountable ordinal , and let denote the element of that corresponds to the (countable) ordinal ."
Method 2. Let be a well-ordering of the reals, or some subset of the reals such as , such that each element has countably many predecessors, and use this well-ordering as the basis for some other construction.
It is also worth noting that the function defined in Example 2 is very similar in spirit to the double sequence , where if and otherwise. This sequence has the property that for every and for every . It is discussed as Example 5 in the article on just-do-it proofs.
Comments
Post new comment
(Note: commenting is not possible on this snapshot.)