Tricki
a repository of mathematical know-how

I have a problem to solve in real analysis and I do not believe that a fundamental idea is needed

Quick description

This article is about proofs in real analysis that involve nothing more than chasing definitions and carrying out elementary logical operations. In principle, a computer could be programmed to find proofs of this kind, though to a beginner they can seem hard.

Prerequisites

Basic definitions of real analysis.

Note iconContributions wanted This article could use additional contributions. It may be that three examples are enough here, but perhaps more in a similar spirit would be good.

Example 1

Let us consider how to prove the following statement (which is a useful lemma in real analysis).

Proposition 1 Let a_1,a_2,\dots be a sequence that converges to a. Suppose that a_n\leq b for every n. Then a\leq b.

There are two ways of going about this. The first is to consider the contrapositive. That is, in a purely mechanical way, we convert the problem into the following equivalent one:

Version 2. Let a_1,a_2,\dots be a sequence that converges to a. Suppose that a>b. Then there exists n such that a_n>b.

If one is not practised at such conversions, then one may have to do them in stages. For instance, instead of ending with "there exists n such that a_n>b" we might have ended with "it is not the case that a_n\leq b for every n" and only then converted it into the existence statement.

Once we have reformulated the statement, we expand out the one definition that we can expand, namely that of "converges to a". Then we obtain the following.

Version 3. Let a_1,a_2,\dots be a sequence and suppose that for every \epsilon>0 there exists N such that |a_n-a|<\epsilon for every n\geq N. Suppose also that a>b. Then there exists n such that a_n>b.

We now look at Version 3 and focus on the statement we ultimately want to prove: a_n>b. Is there anything that resembles it? Well, we do have an inequality concerning a_n earlier on, namely |a_n-a|<\epsilon, which implies that a_n>a-\epsilon. This will do the job for us if a-\epsilon\geq b. Are we free to choose \epsilon? Yes, since we are told that something holds for every positive \epsilon, and our assumption tells us that a-b is positive. So let us choose \epsilon=a-b and see what we get out of it. We get that there exists N such that a_n>b for every n\geq N (since |a_n-a|<\epsilon, so a_n>a-\epsilon=b). In particular, a_N>b and we are done.

That was a rather long-winded account of the proof, but it was designed to demonstrate that no real thought was needed to solve the problem. To put it another way, there was never a stage at which the correct move to make was not more or less forced.

The one exception to that was perhaps the initial decision to prove the contrapositive of the statement. Here is a different way of going about the proof, though the difference is only skin deep. We make use of the following useful principle, which is discussed in much more detail in the article Create an epsilon of room.

Basic principle often used in analysis. Let a and b be two real numbers. Then a\leq b if and only if a<b+\epsilon for every \epsilon>0.

Given this principle, we can argue as follows. We would like to prove that a<b+\epsilon for every \epsilon>0. An automatic move is to start our argument with the words "Let \epsilon>0." (This move is discussed in the article Convert "every x" into a single arbitrary x.) Since we are given an \epsilon, it is very natural to apply the definition of convergence to that particular \epsilon. It gives us an N such that |a_n-a|<\epsilon for every n\geq N. But we also know that a_n\leq b, so it follows that a<b+\epsilon, as required.

General discussion

The above proofs used five basic techniques, all of them very simple after a bit of practice.

  • Convert "every x" into a single arbitrary x

  • Given a statement, replace it by its contrapositive. (This requires you to be able to write down the negation of a statement, which, after a bit of practice, is an automatic process. See how to negate a mathematical statement if you need help with this.)

  • Given a statement that involves a word like "converges" or "continuous", the definition of which involves epsilons, deltas, quantifiers etc., replace that word by its expanded-out definition.

  • If, amongst the statements you are allowed to assume, you have a statement that begins "\forall \epsilon>0," then make a sensible choice of \epsilon. Usually, there will be a natural choice. (More generally, if you want to use an assumption that starts with"\forall x" then you need to make a sensible choice of x.)

  • Given some statements that you are allowed to assume, and a statement that you are trying to prove, search for resemblances between parts of them. This often helps with deciding which assumptions to use at which stage of the argument, and which values to choose in the previous technique.

Example 2

The next example is slightly more complicated, but it still involves nothing more than playing around with statements using the five techniques just mentioned.

Proposition 2 Let f be a function from \mathbb{R} to \mathbb{R}. Then the following two statements are equivalent.
  • f is continuous.
  • If (a_n) is any sequence that converges to a limit a, then f(a_n) converges to f(a).

Forward implication. Let us begin by assuming that f is continuous and see how to prove the statement about sequences.

The first step is to choose a single arbitrary convergent sequence to work with. In other words,

  • let (a_n) be a sequence that converges to a limit a.

Now we would like to prove that f(a_n) converges to f(a). So let us expand out this definition and see what it gives us.

  • For every \epsilon>0 there exists N such that, for every n\geq N, |f(a_n)-f(a)|<\epsilon. [Statement to be proved.]

To prove this, let's choose a single arbitrary \epsilon:

  • Let \epsilon>0. [Fixing an arbitrary \epsilon.]

How do we find an N that will work? We'd better use our assumption that a_n converges to a, and in order to do that we had better expand out the definition of "converges to".

  • For every \eta>0 there exists M such that, for every m\geq M, |a_m-a|<\eta. [a_m converges to a.]

(We used different letters because we do not yet know how \eta will relate to \epsilon.)

To get from this assumption to a statement about f(a_n) and f(a), we will have to use the assumption that f is continuous (since the statement to be proved has no reason to be true if f is just an arbitrary function). So we had better write out the definition of continuity, again using different letters.

  • For every \theta>0 and every x there exists \delta>0 such that, for every y, if |x-y|<\delta then |f(x)-f(y)|<\theta. [f is continuous.]

Now we have got to the stage where we must look for resemblances between parts of statements (which we can turn into more than mere resemblances by appropriate choices of variables that we are allowed to choose).

The final statement that we want, when shorn of all its quantifiers, is |f(a_n)-f(a)|<\epsilon. This resembles |f(x)-f(y)|<\theta. So a natural choice of \theta is \epsilon. So let us deduce from the continuity assumption that

  • for every x there exists \delta>0 such that, for every y, if |x-y|<\delta then |f(x)-f(y)|<\epsilon.

In order to apply this, what should we choose as our x? What fixed number do we have? There's only one, and it is a, so let's plug that in too:

  • there exists \delta>0 such that, for every y, if |a-y|<\delta then |f(a)-f(y)|<\epsilon.

Finally, we would like to replace y by a_n. This we can easily do as follows:

  • there exists \delta>0 such that, for every n, if |a-a_n|<\delta then |f(a)-f(a_n)|<\epsilon.

Now our focus shifts to the statement that |a-a_n|<\delta, since if we can prove that, then we will have the statement we need. Since f is no longer involved, it is time to use the definition of convergence that we wrote down earlier. What shall we choose as our \eta? Obviously we should choose \delta. Thus, we obtain the consequence that

  • there exists M such that, for every m\geq M, |a_m-a|<\delta.

Combining this with the previous assertion, we deduce that

  • there exists M such that, for every m\geq M, |f(a)-f(a_m)|<\epsilon.

Apart from the fact that we have written M and m instead of N and n, this is exactly what we were trying to prove, so we are done. (One might perhaps add to the list of techniques the practice of changing the names of bound variables whenever we want.

Reverse implication. Now let us prove the converse. That is, we have a function f such that f(a_n)\rightarrow f(a) whenever a_n\rightarrow a and we would like to prove that f is continuous.

Once again, we expand out the statement that we are trying to prove.

  • For every \epsilon>0 and every x there exists \delta>0 such that, for every y, if |y-x|<\delta then |f(x)-f(y)|<\epsilon. [Statement to be proved.]

General discussion

At first it seems hard to use the statement about sequences, since we do not appear to have a sequence. However, there is a standard method of producing a sequence, which should be given as a further simple technique.

  • If you have a statement of the form "For every \eta>0 there exists x such that P(x,\eta)," and if P(x,\eta) implies P(x,\eta') whenever \eta<\eta', then convert the statement into "For every n\in\N there exists x such that P(x,1/n)."

It is obvious that the first statement implies the second. The second implies the first too since given \eta you can choose n such that 1/n<\eta to get x such that P(x,1/n), which implies that P(x,\eta).

From the second statement you can define a sequence (x_n) by choosing each x_n to satisfy the statement P(x,1/n).

Example 2, continued

How do we apply this technique to the problem at hand? We don't seem to have a statement that we can assume, apart from statements that already involve sequences, and our whole problem is how to get sequences involved. Another problem is that we do not have a statement of the form "For every \eta>0 there exists x such that P(x,\eta)."

We can deal with both problems at once by proving the contrapositive instead. So now we are trying to prove that if f is not continuous then there is a convergent sequence a_n\rightarrow a such that f(a_n) does not converge to f(a). Thus, our new assumption is that f is not continuous, which expands out to

  • there exist \epsilon>0 and x\in\R such that for every \delta>0 there exists y such that |x-y|<\delta but |f(x)-f(y)|\geq\epsilon. [New assumption after switching to contrapositive]

We can apply our sequence-producing technique to the statement "For every \delta>0 there exists y such that |x-y|<\delta but |f(x)-f(y)|\geq\epsilon. That is, P(y,\delta) is the statement that |x-y|<\delta and |f(x)-f(y)|\geq\epsilon, for some fixed choice of \epsilon and x. It's definitely the case that if \delta<\delta', then P(y,\delta) implies P(y,\delta'), so let us convert the above statement into a statement about sequences.

  • there exist \epsilon>0 and x\in\R such that for every n\in\N there exists y such that |x-y|<1/n but |f(x)-f(y)|\geq\epsilon.

That isn't quite a statement about sequences, but we complete the transformation as follows.

  • There exist \epsilon>0 and x\in\R and a sequence (y_n) such that, for every n\in\N, |x-y_n|<1/n and |f(x)-f(y_n)|\geq\epsilon. [Sequence version of new assumption.]

At this point we could just say that it's obvious that y_n tends to x and f(y_n) does not tend to f(x), so we're done. But just to spell out the thought process, here is the new statement that we want to prove.

  • There exists a sequence (a_n) converging to a limit a, such that f(a_n) does not converge to f(a).

Expanding that out, we get the following.

  • There exist a and a sequence (a_n) such that (i) for every \eta>0 there exists N\in\N such that, for everey n\geq N, |a_n-a|<\eta, and (ii) there exists \theta>0 such that for every M\in\N there exists m\geq M such that |f(a_m)-f(a)|\geq\theta.

Since we have a sequence (y_n) and a real number x given to us on a plate, it makes sense to try to show that (i) and (ii) apply with a_n=y_n and a=x. And this is very easy to check: for the first property we choose N such that 1/N<\eta and we are done, and for the second we take \theta=\epsilon and we are done.

General discussion

There are many more statements in basic real analysis whose proofs are of this kind, so it is important to become fluent at producing such proofs. But the benefit of this fluency is not just that it makes one able to prove easy statements: it is also very helpful to apply these techniques to hard statements as well, because they have the effect of isolating the real difficulty. Also, the collection of results provable in a semi-automatic way can be greatly expanded if one allows oneself some further statements, such as the Bolzano-Weierstrass theorem or the intermediate value theorem, as permitted assumptions. Then an approach that often works well is to go as far as one can with just the assumptions of the problem, and to bring in these other results if and when one gets stuck. But this will be discussed on other pages.