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

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

Subproof.

Assumption: suppose there are finitely many primes

1,

2,,

.

Subproof.

Then we may form the product of these primes =

1

2

and consider +1. +1 must have a prime divisor (by the fundamental theorem of arithmetic) and by inspection cannot be equal to any of

1,

2,,

since +1 has remainder 1 on dividing by

, so is a prime not in the list

1,

2,,

.

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

()

where

()

is a property that might have. Then you should write down the assumption Let be an arbitrary element of and in a subproof prove that

()

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 has been used, use a different letter and prove

()

, 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 () that you have, where () is a property that might have. Then you should think of a new letter (which might be ) and write down the assumption Let be an element of that has the property () 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 that you introduce.

## 4. Using other logical connectives

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.

Rule.

Suppose you wish to prove a statement of the form . Then make an assumption and prove from it in a subproof. Or make the assumption and prove from it in 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.

Rule.

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

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

Rule.

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

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:

Rule.

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

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.

Rule.

To prove a statement make an assumption and prove in a subproof. To use a given assumption , first prove somehow, and then you may deduce that 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 ( ) defined by =(-1) 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 ( ) converges to some limit is

0 ( - )

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

0 ( - )

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

Subproof.

Let be arbitrary.

Remark.

We now need to define a suitable 0 and prove ( - ) . 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 12. Note that 0 .

Remark.

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

Subproof.

Let be arbitrary.

Remark.

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

Subproof.

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

Subproof.

Case 1: suppose 1 - .

In this case 1 is a natural number that shows that ( - ) .

Subproof.

Case 2: suppose 1 - .

Then if 2 - we would have

1 - 2 1 - + 2 - 12+12=1

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

In both cases we have shown ( - ) .

So ( - ) .

So 0 ( - ) .

So 0 ( - ) .

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