If you find yourself wanting to prove the existence of a real number with certain properties, then almost always you will need to do so by means of a limiting argument of some kind, though sometimes this can be disguised if you use other results in your proof that are themselves proved using limiting arguments. This article gives examples of the main general techniques that are used.
Basic concepts and theorems of analysis. In particular, the notion of a real number, sequences, limits, the supremum of a set, the intermediate-value theorem, the nested-intervals property, the Bolzano-Weierstrass theorem. Some of these are briefly explained in the article but advance familiarity with them would definitely be helpful.
The nested-intervals property of the real numbers is the truth of the following theorem.
Just before we see how to prove this result, let us see why it is not a trivial statement by observing that the corresponding statement for open intervals is false: for example, each of the intervals contains the next one, each is non-empty, and yet no real number is contained in every single one of them.
Note that we are trying to prove that a real number exists with a certain property: the property of belonging to all the intervals Thus, the property we want to prove is naturally regarded as the simultaneous occurrence of a countable sequence of properties where is the property of belonging to the interval In such a situation, we cannot normally hope to create all in one go. Instead, we create some auxiliary and more complicated object such as a convergent sequence or a non-empty set that is bounded above, and define in terms of that. (Given the sequence, one would take to be the limit, and given the set one would take the supremum.)
This instantly makes the task easier. For instance, if we use a sequence, then normally we have to ensure that each term in the sequence satisfies finitely many properties rather than infinitely many, though in this example it is even easier than that since the sequence suggests itself instantly.
Example 1, continued
Here, then, is a proof of Theorem 1.
Proof. The sequence is increasing (though not necessarily strictly increasing) and bounded above (by ). Therefore, it converges. Let be the limit. Then for every , since for every (This follows very easily from a principle that is proved as Example 1 in I have a problem to solve in real analysis and I do not believe that a fundamental idea is needed.) We can also show that for every since for every Therefore, belongs to every interval as required.□
Note that in order to create our real number we used a basic result of real analysis: that bounded monotone sequences converge. This is typical of the way one proves that real numbers exist, and the next few examples will do the same, but using different basic results.
From now on, we shall think of the nested-intervals property not as a theorem but as one of the basic results about real numbers that we are free to use. The next example illustrates not just that different basic results can be used, but that different basic results can be used for the same problem. In fact, we shall give three (not all hugely different) proofs of the intermediate value theorem. (A fourth proof can be found as Example 1 of Discretization followed by compactness arguments.)
Proof using nested intervals. In order to use the nested-intervals property, we must construct some nested intervals in such a way that each one has at least a chance of containing such that In particular, it would be disastrous if every element of one of the intervals was greater than or every element was less than But there is an easy way to ensure that this does not happen. What we do is build a sequence of intervals as follows. We begin by setting and And once we have we let be either the left half of or the right half of That is, we either let and or we let and What governs our decision? Well, by induction we can always make the choice in such a way that and If we've done this up to then we choose the left half of if and the right half if Finally, we let be the intersection of all these intervals, which exists by the nested-intervals property.
Now we appeal to standard theorems about sequences, limits, and continuous functions (all of which are proved in I have a problem to solve in real analysis and I do not believe that a fundamental idea is needed). Since for every and we find that and are both at most so and Since is continuous, it follows that and Since for every it follows that And since for every it follows that So
It might be argued that we used a bit more than the nested intervals there: we used the sequences of their end points. However, we used just the nested intervals to find and using the endpoints was perhaps justified by the fact that the way we chose the intervals was in terms of their endpoints.
A purist might like to prove a general principle in advance about nested intervals and continuous functions. It could say the following. Let be a collection of non-empty closed intervals with lengths tending to zero. Let be a continuous function, and suppose that for each there exists such that Then where is the (unique) element of the intersection of the
Alternatively, one can deduce the following result from the Bolzano-Weierstrass theorem. Let be a collection of non-empty closed intervals. Let be a continuous function and suppose that for each there exists such that Then there exists in the intersection of all the such that In fact, perhaps we can prove that later in this article ...
Example 2, continued
Suppose you wanted to work out the square root of using a very unsophisticated algorithm. Then you could do the following: you first find the largest integer that squares to less than 2, then the largest multiple of that squares to less than then the largest multiple of that squares to less than and so on. What you would produce would be the sequence of longer and longer truncations of the decimal expansion of
An argument of this kind can be turned into a rigorous proof of the intermediate value theorem. It is slightly odd to use decimal expansions for this (though one could) so let's use binary expansions instead. Also, for convenience let's assume that and
Proof using monotone sequences. Let us construct a sequence by taking to be the largest multiple of such that This sequence is monotone increasing, since is the maximum over a larger set than It is also bounded above by Therefore it converges to some limit For each so by the continuity of we have that But the choice of also guarantees that and also converges to so Therefore,
Next, let us prove the result using the fact that every non-empty set that is bounded above has a supremum.
"Proof using the least upper bound principle.'' Let be the set of all such that Then is non-empty, since and bounded above by Therefore, it has a supremum. Let be this supremum. We prove that by showing that cannot be greater than and cannot be less than Let us start with the first assertion. If then let By continuity we can find such that whenever Since is an upper bound for it follows that is also an upper bound for which contradicts the fact that is the least upper bound for
If then let By continuity we can find such that whenever But this implies that is not after all an upper bound for
Now let us prove the nested-intervals property but for arbitrary closed bounded sets.
We are back in the situation of wanting to find a real number that has every one of a countable sequence of properties. There is no obvious way of using the nested-intervals property, because we don't have any intervals. So let us try using sequences instead. An obvious approach would be to make sure that for every If we do that, then the fact that each contains all the succeeding ones will imply that whenever And then the limit of the will also be in since is a closed set.
But hang on – who said that the sequence converged? So far, we have done nothing to ensure that, and it is not completely obvious how we could.
It is in situations like these that the Bolzano-Weierstrass theorem is often useful. If the good properties you have made your sequence have are shared by all its subsequences, then you are free to pass to a subsequence. So all you need to know then is that your sequence has a convergent subsequence, which it does if it is bounded. But if is a subsequence, then so whenever Therefore, the property we were interested in is indeed shared by all subsequences. Moreover, the sequence belongs to the set which is bounded, by hypothesis. Therefore, we are done.[proof]
The point of this article is that there are several theorems in basic real analysis that end by asserting that a real number exists with a certain property (such as being the limit of a sequence, or the supremum of a set, or the limit of a subsequence of a sequence, or a point where a continuous function takes a given value). If you are trying to prove that a real number exists with a certain property, and if the existence of this real number is not completely obvious, then instead of trying to prove it directly, try instead to find a sequence, set, or continuous function to which you can apply one of these theorems.
More advanced techniques
We will be much briefer in this section, because the techniques we discuss here are discussed more fully in the article entitled How to change "for all x there exists y" into "there exists y such that for all x".
Let be translates of the Cantor set. Is it possible for to equal the whole of ?
The answer is no, and there are several ways that one might consider going about the proof. Note that proving that their union is not the whole of amounts to finding a real number for which countably many properties hold simultaneously: property is the property of not belonging to Thus, we are on familiar territory.
A perfectly good way of going about the problem is to use the ideas of the previous section. We shall try to construct a nested sequence of non-empty closed intervals in such a way that the intersection does not belong to any And this is not too hard, once we make the following observation about the Cantor set itself: every interval of positive length in contains a non-empty closed subinterval that is disjoint from the Cantor set. This of course applies to every translate of the Cantor set as well. Click here if you want the proof. To prove this, let and pick such that and has two consecutive s somewhere in its ternary expansion. Then any number sufficiently close to has at least one in its ternary expansion, so does not belong to the Cantor set. This gives us an interval of positive length not contained in and by shortening it if necessary we can make sure that this interval is closed and contained in the interval
So now all we do is use this fact to construct inductively a sequence of closed intervals of positive length in such a way that is disjoint from By the nested-intervals property, these intervals have a non-empty intersection, and any point in this intersection is disjoint from all the
Now the point of this section is that we can sometimes avoid going through this kind of argument over and over again by encapsulating it as a general principle and just applying that principle. And the principle that works here is the Baire category theorem. (Note: the Wikipedia article just linked to is a bit dry and formal, but in due course the non-existent Tricki article How to use the Baire category theorem should get written. Also, the article on reversing quantifiers mentioned just before this example contains some information about how to use the theorem.)
In one of its versions, the Baire category theorem is about a certain notion of smallness. The basic idea is that the sets cannot cover all of because (i) they are all small, (ii) a countable union of small sets is small, (iii) is large. So what does "small" mean in this context? Well, it turns out to mean something like "what comes out of the proof just given". Here is a more formal definition ...
A subset of is called nowhere dense if there is no non-empty open interval for which is dense in That is, for every non-empty open interval you can find a non-empty open subinterval such that A proof very similar to the proof above can be used to show that no countable union of nowhere dense sets can equal the whole of and this is what the Baire category theorem says. (However, it has various equivalent versions and can be generalized to any complete metrizable topological space.) But this shows that countable unions of nowhere dense sets form a class of sets that is closed under countable unions (since a countable union of countable unions of nowhere dense sets is a countable union of nowhere dense sets). Thus, if we define a set to be meagre if it is a countable union of nowhere dense sets, and interpret "small" to mean "meagre", we have our three properties above.
So if you know the Baire category theorem, then solving the problem above becomes easy: all you have to do is check that a translate of the Cantor set is meagre, which it is because it is nowhere dense.
Another proof, which is more advanced, is to use measure theory to give us a different notion of smallness that is in some ways more intuitive (though this impression is slightly misleading). Roughly speaking, the Cantor set has "length zero" and a countable union of sets of length zero also has length zero. But has infinite length. I will say little more about this, other than that it can be made to work. Once one has the theory of Lebesgue measure available, this proof is almost trivial. It follows quickly from the definition of Lebesgue measure that the Cantor set has measure zero, and a basic theorem of measure theory is that a countable union of sets of measure zero has measure zero.
Which of these two proofs is the "real" reason that you cannot cover with translates of the Cantor set? If you are inclined to say that the second is more natural, then observe that you can vary the construction of the Cantor set by removing smaller and smaller proportions of at each stage, so that you end up with a nowhere dense set of positive measure. If you do that, then the second proof stops working but the first one carries on just fine.
In fact, Erdős has shown that there is a bijection from to that takes sets of measure zero to meagre sets, such that its inverse takes meagre sets to sets of measure zero. This proves that there is a kind of equivalence between what you can prove using measure-zero arguments and what you can prove using Baire-category arguments.