Revision of Creating real numbers using limiting arguments from Sat, 18/04/2009 - 23:38

Quick description

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.

Prerequisites

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.

This article is incomplete. I am actively working on this article so it won't be incomplete for too much longer.

Example 1

The nested-intervals property of the real numbers is the truth of the following theorem.

Theorem 1 Let $[u_1,v_1],[u_2,v_2],\dots$ be a collection of non-empty closed intervals, and suppose that each one contains the next as a subset. Then the intersection of all the intervals is non-empty.

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 $(0,1),(0,1/2),(0,1/3),\dots$ contains the next one, each is non-empty, and yet no real number is contained in every single one of them.

General discussion

Note that we are trying to prove that a real number $x$ exists with a certain property: the property of belonging to all the intervals $[u_n,v_n].$ Thus, the property we want to prove is naturally regarded as the simultaneous occurrence of a countable sequence of properties $P_1,P_2,\dots,$ where $P_n$ is the property of belonging to the interval $[u_n,v_n].$ In such a situation, we cannot normally hope to create $x$ 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 $x$ in terms of that. (Given the sequence, one would take $x$ 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 $u_1,u_2,\dots$ is increasing (though not necessarily strictly increasing) and bounded above (by $v_1$ ). Therefore, it converges. Let $x$ be the limit. Then $x\geq u_n$ for every $n$ , since $u_m\geq u_n$ for every $m\geq n.$ (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 $x\leq v_n$ for every $n,$ since $u_m\leq v_m\leq v_n$ for every $m\geq n.$ Therefore, $x$ belongs to every interval $[u_n,v_n],$ as required.□

General discussion

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.)

Example 2

Theorem 2 Let $f$ be a continuous function from a closed interval $[a,b]$ to $\R$ and suppose that $f(a)<t$ and $f(b)>t.$ Then there exists $c$ such that $a<c<b$ and $f(c)=t.$

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 $c$ such that $f(c)=t.$ In particular, it would be disastrous if every element of one of the intervals was greater than $t,$ or every element was less than $t.$ But there is an easy way to ensure that this does not happen. What we do is build a sequence of intervals $[a_n,b_n]$ as follows. We begin by setting $a_0=a$ and $b_0=b.$ And once we have $[a_n,b_n],$ we let $[a_{n+1},b_{n+1}]$ be either the left half of $[a_n,b_n]$ or the right half of $[a_n,b_n].$ That is, we either let $a_{n+1}=a_n$ and $b_{n+1}=(a_n+b_n)/2$ or we let $a_{n+1}=(a_n+b_n)/2$ and $b_{n+1}=b_n.$ What governs our decision? Well, by induction we can always make the choice in such a way that $f(a_n)\leq t$ and $f(b_n)\geq t.$ If we've done this up to $n,$ then we choose the left half of $[a_n,b_n]$ if $f((a_n+b_n)/2)\geq t$ and the right half if $f((a_n+b_n)/2)<t.$ Finally, we let $c$ 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 $a_n\leq c\leq b_n$ for every $n,$ and $b_n-a_n=2^{-n}(b-a),$ we find that $|a_n-c|$ and $|b_n-c|$ are both at most $2^{-n}(b-a),$ so $a_n\rightarrow c$ and $b_n\rightarrow c.$ Since $f$ is continuous, it follows that $f(a_n)\rightarrow f(c)$ and $f(b_n)\rightarrow f(c).$ Since $f(a_n)\leq t$ for every $n,$ it follows that $f(c)\leq t.$ And since $f(b_n)\geq t$ for every $n,$ it follows that $f(c)\geq t.$ So $f(c)=t.$

General discussion

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 $c,$ 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 $I_1\supset I_2\supset I_3\supset\dots$ be a collection of non-empty closed intervals with lengths tending to zero. Let $f$ be a continuous function, and suppose that for each $n$ there exists $x_n\in I_n$ such that $f(x_n)\leq t.$ Then $f(x)\leq t,$ where $x$ is the (unique) element of the intersection of the $I_n.$

Alternatively, one can deduce the following result from the Bolzano-Weierstrass theorem. Let $I_1\supset I_2\supset I_3\supset\dots$ be a collection of non-empty closed intervals. Let $f$ be a continuous function and suppose that for each $n$ there exists $x_n\in I_n$ such that $f(x_n)\leq t.$ Then there exists $x$ in the intersection of all the $I_n$ such that $f(x)\leq t.$ In fact, perhaps we can prove that later in this article ...

Example 2, continued

Suppose you wanted to work out the square root of $2$ 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 $0.1$ that squares to less than $2,$ then the largest multiple of $0.01$ that squares to $2,$ and so on. What you would produce would be the sequence $1, 1.4, 1.41, 1.414, 1.4142,\dots,$ of longer and longer truncations of the decimal expansion of $2.$

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 $a=0$ and $b=1.$

Proof using monotone sequences. Let us construct a sequence $a_0,a_1,a_2,\dots$ by taking $a_n$ to be the largest multiple $2^{-n}j$ of $2^{-n}$ such that $f(2^{-n}j)\leq t.$ This sequence is monotone increasing, since $a_n$ is the maximum over a larger set than $a_{n-1}.$ It is also bounded above by $1.$ Therefore it converges to some limit $c.$ For each $n,$ $f(a_n)\leq t,$ so by the continuity of $f$ we have that $f(c)\leq t.$ But the choice of $a_n$ also guarantees that $f(a_n+2^{-n})>t,$ and $a_n+2^{-n}$ also converges to $c,$ so $f(c)\geq t.$ Therefore, $f(c)=t.$

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 $C$ be the set of all $x$ such that $f(x)<t.$ Then $C$ is non-empty, since $a\in C,$ and bounded above by $b.$ Therefore, it has a supremum. Let $c$ be this supremum. We prove that $f(c)=t$ by showing that $f(c)$ cannot be greater than $t$ and cannot be less than $t.$ Let us start with the first assertion. If $f(c)>t,$ then let $\epsilon=f(c)-t.$ By continuity we can find $\delta>0$ such that $f(x)>f(c)-\epsilon=t$ whenever $|x-c|<\delta.$ Since $c$ is an upper bound for $C,$ it follows that $c-\delta$ is also an upper bound for $C,$ which contradicts the fact that $c$ is the least upper bound for $C.$

If $f(c)<t,$ then let $\epsilon=t-f(c).$ By continuity we can find $\delta>0$ such that $f(x)<f(c)+\epsilon=t$ whenever $|x-c|<\delta.$ But this implies that $c$ is not after all an upper bound for $C.$

Example 3

Now let us prove the nested-intervals property but for arbitrary closed bounded sets.

Theorem 3 Let $F_1\supset F_2\supset F_3\supset\dots$ be non-empty closed bounded sets. Then the intersection $\bigcup_{n=1}^\infty F_n$ is non-empty.

We are back in the situation of wanting to find a real number $x$ 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 $x_n\in F_n$ for every $n.$ If we do that, then the fact that each $F_n$ contains all the succeeding ones will imply that $x_m\in F_n$ whenever $m\geq n.$ And then the limit of the $x_m$ will also be in $F_n,$ since $F_n$ is a closed set.

But hang on – who said that the sequence $(x_m)$ 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 $x_{k_1},x_{k_2},\dots$ is a subsequence, then $k_m\geq m,$ so $x_{k_m}\in F_n$ whenever $m\geq n.$ Therefore, the property we were interested in is indeed shared by all subsequences. Moreover, the sequence $(x_n)$ belongs to the set $F_1,$ which is bounded, by hypothesis. Therefore, we are done.

General discussion

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.