Logic for analysis: proofs

We have seen how to write down statements concerning the convergence of sequences in a previous web page. We now look at how such statements may be proved. You will also learn how to disprove such statements here, as to disprove a statement is the same thing as proving its negation , and we learnt how to find this negation in the previous web page.

The objective is to give you a number of rules-of-thumb that will enable you to write down such proofs in as painless a way as possible. I will follow these rules in all the examples I do in this course, and you may use them in this course and in any other you do in this university.

Many of the rules-of-thumb for writing down proofs are plain common sense and are exactly the sort of thing you were learning last term in the first part of this module. For example, it is important to learn to argue forwards, starting with the assumptions and ending with the conclusion. Or at least that is how the finished proof should look. Of course it is not always easy to write the proof out straight away in this way, so I suggest:

Much of the initial part of proof-writing involves working out what the assumptions and conclusion actually mean. This may not be easy, and is certainly part of the exercise, so don't try to skip this step. In fact, if you do it right it really will help you in the next part of proof-writing.

That presumes you have learnt the definitions, or at least have them to hand. Occasionally a new definition may be given as part of a question, and you would be expected to read and use it.

One of the most common ways of writing proofs, is to use proof-by-contradiction or reductio ad absurdum. This allows you to make a brand new assumption and prove it wrong by getting a contradiction.

I shall indicate subproofs by indenting the text like this, and sometimes with a vertical line down the left margin where the indent is. It is important to indicate such subproofs somehow because you are not allowed to use any statement proved in a subproof once the subproof has finished. The reason for this is that any such statement may depend on an erroneous assumption such as there are only finitely many primes.

The real joy about breaking proofs into subproofs (like we did for reductio ad absurdum above) is that statements involving quantifiers become much easier to prove using subproofs. In fact the statements actually tell you the form the proof must take, and once you have written this down there is usually only one or two more lines to write down before the proof is finished.

There are two rules here to learn, one involves a statement with the ∃ quantifier on the assumptions side and the other involves a statement with the ∀ quantifier on the conclusion side. We'll start with the latter.

It is important that you use a new letter not used up to this point in the proof. So if has been used, use a different letter and prove

()

Once again, it is essential to use a brand new letter that hasn't been used before. Feel free to choose whatever you like. Purists would say that you should introduce a subproof for this ∃-rule as well, but it shouldn't matter provided that the conclusion you are trying to get to doesn't involve the new letter that you introduce.

The connective and rarely causes problems. If we know is true then we know that and are both true, and if we need to prove then we need to prove and we need to prove .

On the other hand, or can occasionally be awkward. The difficulty is that if we are trying to prove we may not know in advance which of or to go for. The solution again is to use a subproof.

The point is, by making the assumption , we now know that if is going to be true then it had better be the part that is true.

A variation on this is proof by cases. Here we make an assuption that some statement holds and show that this gives us our required conclusion, and then show that the assumption also gives the same conclusion. This is rather like using as an assumption and using reductio ad absurdum. (The statement is obviously always true.)

Since we saw that an implication is really a form or or statement, , we can use the rules for implication too. When written out for implications, these rules are really very nice and quite memorable:

Finally, you may have seen elsewhere the very useful fact that an implication is equivalent to its contrapositive . (This is straightforward to see using the the facts that the following statements are equivalent: ; ; ; .) This gives some other options for dealing with implication.

It is potentially more difficult to show a sequence does not converge to any limit than it does converge. This is because there is an extra quantifier involved (because we need to consider all possible limits).

This proof is complicated to write down fully, but the idea of taking to be smaller than the distance between the two values 1 and -1 is clear. (Taking =1 would have been OK too, but there are no prizes for giving the best .) Note that there is an implicit embedded reductio ad absurdum inside the proof where we had assumed both _{1 -} and _{2 -} . This could have been written more formally as a proper reductio ad absurdum. (It's OK to have one reductio ad absurdum inside another provided you keep track of the assumptions and don't make use of any statement proved in a subproof that has closed.)