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.
Basic definitions of real analysis.
Let us consider how to prove the following statement (which is a useful lemma in real analysis).
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 be a sequence that converges to . Suppose that Then there exists such that
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 such that " we might have ended with "it is not the case that for every " 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 ". Then we obtain the following.
Version 3. Let be a sequence and suppose that for every there exists such that for every Suppose also that Then there exists such that
We now look at Version 3 and focus on the statement we ultimately want to prove: Is there anything that resembles it? Well, we do have an inequality concerning earlier on, namely which implies that This will do the job for us if Are we free to choose ? Yes, since we are told that something holds for every positive and our assumption tells us that is positive. So let us choose and see what we get out of it. We get that there exists such that for every (since so ). In particular, 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 and be two real numbers. Then if and only if for every
Given this principle, we can argue as follows. We would like to prove that for every An automatic move is to start our argument with the words "Let " (This move is discussed in the article Convert "every x" into a single arbitrary x.) Since we are given an it is very natural to apply the definition of convergence to that particular It gives us an such that for every But we also know that so it follows that as required.
The above proofs used five basic techniques, all of them very simple after a bit of practice.
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 "," then make a sensible choice of Usually, there will be a natural choice. (More generally, if you want to use an assumption that starts with"" then you need to make a sensible choice of )
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.
The next example is slightly more complicated, but it still involves nothing more than playing around with statements using the five techniques just mentioned.
- is continuous.
- If is any sequence that converges to a limit then converges to
Forward implication. Let us begin by assuming that 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 be a sequence that converges to a limit
Now we would like to prove that converges to So let us expand out this definition and see what it gives us.
For every there exists such that, for every , [Statement to be proved.]
To prove this, let's choose a single arbitrary :
Let [Fixing an arbitrary ]
How do we find an that will work? We'd better use our assumption that converges to , and in order to do that we had better expand out the definition of "converges to".
For every there exists such that, for every , [ converges to .]
(We used different letters because we do not yet know how will relate to )
To get from this assumption to a statement about and we will have to use the assumption that is continuous (since the statement to be proved has no reason to be true if is just an arbitrary function). So we had better write out the definition of continuity, again using different letters.
For every and every there exists such that, for every , if then [ 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 This resembles So a natural choice of is So let us deduce from the continuity assumption that
for every there exists such that, for every , if then
In order to apply this, what should we choose as our ? What fixed number do we have? There's only one, and it is , so let's plug that in too:
there exists such that, for every , if then
Finally, we would like to replace by This we can easily do as follows:
there exists such that, for every , if then
Now our focus shifts to the statement that since if we can prove that, then we will have the statement we need. Since is no longer involved, it is time to use the definition of convergence that we wrote down earlier. What shall we choose as our ? Obviously we should choose Thus, we obtain the consequence that
there exists such that, for every ,
Combining this with the previous assertion, we deduce that
there exists such that, for every ,
Apart from the fact that we have written and instead of and 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 such that whenever and we would like to prove that is continuous.
Once again, we expand out the statement that we are trying to prove.
For every and every there exists such that, for every if then [Statement to be proved.]
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 there exists such that " and if implies whenever then convert the statement into "For every there exists such that "
It is obvious that the first statement implies the second. The second implies the first too since given you can choose such that to get such that which implies that
From the second statement you can define a sequence by choosing each to satisfy the statement
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 there exists such that ."
We can deal with both problems at once by proving the contrapositive instead. So now we are trying to prove that if is not continuous then there is a convergent sequence such that does not converge to Thus, our new assumption is that is not continuous, which expands out to
there exist and such that for every there exists such that but [New assumption after switching to contrapositive]
We can apply our sequence-producing technique to the statement "For every there exists such that but That is, is the statement that and for some fixed choice of and It's definitely the case that if then implies so let us convert the above statement into a statement about sequences.
there exist and such that for every there exists such that but
That isn't quite a statement about sequences, but we complete the transformation as follows.
There exist and and a sequence such that, for every , and [Sequence version of new assumption.]
At this point we could just say that it's obvious that tends to and does not tend to 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 converging to a limit , such that does not converge to
Expanding that out, we get the following.
There exist and a sequence such that (i) for every there exists such that, for everey and (ii) there exists such that for every there exists such that
Since we have a sequence and a real number given to us on a plate, it makes sense to try to show that (i) and (ii) apply with and And this is very easy to check: for the first property we choose such that and we are done, and for the second we take and we are done.
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.