Logic for analysis: proofs

1. Introduction

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 X is the same thing as proving its negation ¬ X , 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.

2. Starting writing proofs

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:

Rule.

Write all the assumptions you are allowed to use at the top of a blank sheet of paper, and write the conclusion you want to reach at the bottom. Now fill in the space in between, either by arguing forwards (working from the top downwards), or by simplifying the required conclusion (working from the bottom upwards), or a combination of these.

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.

Rule.

Use the definitions to re-write the assumptions and conclusion in a proof into other forms that are easier to deal with.

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.

Rule.

In a proof you are allowed to make a new assumption (that must be clearly labelled as such) and prove it wrong by getting a contradiction from it. (This part of the proof could be called a subproof. It too should be clearly identified.) If successful, the assumption and subproof together prove the negation of your original assumption.

Example.

There are infinitely many primes.

Proof.

We use reductio ad absurdum.

Subproof.

Assumption: suppose there are finitely many primes p 1 , p 2 , , p n .

Subproof.

Then we may form the product of these primes k = p 1 p 2 p n and consider k + 1 . k + 1 must have a prime divisor q (by the fundamental theorem of arithmetic) and by inspection q cannot be equal to any of p 1 , p 2 , , p n since k + 1 has remainder 1 on dividing by p i , so q is a prime not in the list p 1 , p 2 , , p n .

And so we get a contradiction.

Therefore there are infinitely many primes.

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.

3. Techniques for proving statements with quantifiers

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.

Rule.

Suppose you wish to prove a statement of the form x X   P ( x ) where P ( x ) is a property that x might have. Then you should write down the assumption Let x be an arbitrary element of X and in a subproof prove that P ( x ) is true from this assumption.

It is important that you use a new letter not used up to this point in the proof. So if x has been used, use a different letter and prove w X   P ( w ) , or something like this with a different letter; this is, as we saw earlier, the same statement.

Rule.

Suppose you wish to make use of an assumption y Y   Q ( y ) that you have, where Q ( y ) is a property that y might have. Then you should think of a new letter (which might be y ) and write down the assumption Let y be an element of Y that has the property Q ( y ) and prove your conclusion from this assumption and your other assumptions.

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 y that you introduce.

4. Using other logical connectives

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

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

Rule.

Suppose you wish to prove a statement of the form A B . Then make an assumption ¬ A and prove B from it in a subproof. Or make the assumption ¬ B and prove A from it in a subproof.

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

Rule.

To use a statement A B that is in your list of assumptions you need to know either ¬ A (in which case you can deduce that B holds) or ¬ B (in which case you can deduce that A holds).

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

Rule.

To prove a statement A it suffices to: (1) prove A in a subproof from assumption B ; and (2) prove A in a subproof from assumption ¬ B . The statement B can be anything. (Sometimes some skill is required in choosing the right B .)

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

Rule.

To prove a statement A B make an assumption A and prove B in a subproof. To use a given assumption A B , first prove A somehow, and then you may deduce that B is true.

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

Rule.

To prove a statement A B make an assumption ¬ B and prove ¬ A in a subproof. To use a given assumption A B , first prove ¬ B somehow, and then you may deduce that ¬ A is true.

5. An example

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

Example.

The sequence ( a n ) defined by a n = ( -1 ) n does not converge to any limit.

Proof.

Remark.

I will sometimes make remarks written like this inside proofs: they are not part of the proof but are just comments indicating some feature of the proof or how I was thinking about it. They are not necessary for a correct proof, and could be deleted completely, but are provided to help you understand it better.

Remark.

The statement that ( a n ) converges to some limit is

l   ε > 0   N   n   ( n N | a n - l | < ε )

So the statement that it does not converge to any limit is

l   ε > 0   N   n   ( n N | a n - l | ε )

We prove this. Since the statement we want to prove starts with a we start a subproof straight away.

Subproof.

Let l be arbitrary.

Remark.

We now need to define a suitable ε > 0 and prove N   n   ( n N | a n - l | ε ) . Since the sequence hops between two points distance two away any ε a bit less than 2 should work. There are no prizes for choosing the "best" ε , however.

Subproof.

Define ε to be 1 2 . Note that ε > 0 .

Remark.

We now want to prove a statement starting N   so we let N be arbitrary.

Subproof.

Let N be arbitrary.

Remark.

We must find a suitable n now. Unfortunately it is not clear what to take, but at least one of N and N + 1 should work.

Subproof.

Define n 1 to be N and n 2 to be N + 1 . Note that n 2 n 1 = N N , so both are greater than or equal to N . We now argue using cases.

Subproof.

Case 1: suppose | a n 1 - l | ε .

In this case n 1 is a natural number that shows that n   ( n N | a n - l | ε ) .

Subproof.

Case 2: suppose | a n 1 - l | < ε .

Then if | a n 2 - l | < ε we would have

| a n 1 - a n 2 | | a n 1 - l | + | a n 2 - l | < 1 2 + 1 2 = 1

by the triangle inequality. But this is impossible as | a n - a n + 1 | = 2 for all n as a n = ( -1 ) n . Thus | a n 2 - l | ε and n 2 is a natural number that shows that n   ( n N | a n - l | ε ) .

In both cases we have shown n   ( n N | a n - l | ε ) .

So N   n   ( n N | a n - l | ε ) .

So ε > 0   N   n   ( n N | a n - l | ε ) .

So l   ε > 0   N   n   ( n N | a n - l | ε ) .

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 | a n 1 - l | < ε and | a n 2 - l | < ε . 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.)