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 $\neg 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.

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},\dots ,{p}_{n}$.

**Subproof.**

Then we may form the product of these primes $k={p}_{1}{p}_{2}\dots {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},\dots ,{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},\dots ,{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

.

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 $\exists $ quantifier on the *assumptions* side and the
other involves a statement with the $\forall $ quantifier on
the *conclusion* side. We'll start with the latter.

Rule.

Suppose you wish to prove a statement of the form
$\forall x\in XP\left(x\right)$

where $P\left(x\right)$ 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\left(x\right)$ 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
$\forall w\in XP\left(w\right)$

, 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
$\exists y\in YQ\left(y\right)$

that you have, where $Q\left(y\right)$
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\left(y\right)$

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 $\exists $-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*.

The connective and

rarely causes problems.
If we know $A\wedge B$ is true then we know that
$A$ and $B$ are both true, and if we need to prove
$A\wedge 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\vee 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\vee B$

. Then make an assumption $\neg A$
and prove $B$ from it in a subproof. Or
make the assumption $\neg B$
and prove $A$ from it in a subproof.

The point is, by making the assumption $\neg A$, we now
know that if
$A\vee B$

is going to be true then it had better
be the $B$ part that is true.

Rule.

To use a statement
$A\vee B$

that is in your list of
assumptions you need to know either $\neg A$ (in which case
you can deduce that $B$ holds) or $\neg 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 $\neg A$ also gives the
same conclusion. This is rather like using $A\vee \neg A$
as an assumption and using *reductio ad absurdum*. (The
statement $A\vee \neg 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 $\neg B$. The statement $B$ can be anything. (Sometimes some skill is required in choosing the right $B$.)

Since we saw that an implication $A\Rightarrow B$ is really
a form or or

statement, $\neg A\vee B$, we can use the $\vee $
rules for implication too. When written out for implications, these rules
are really very nice and quite memorable:

Rule.

To prove a statement $A\Rightarrow B$ make an assumption $A$ and prove $B$ in a subproof. To use a given assumption $A\Rightarrow 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\Rightarrow B$ is equivalent to its contrapositive $\neg B\Rightarrow \neg A$. (This is straightforward to see using the the facts that the following statements are equivalent: $A\Rightarrow B$; $\neg A\vee B$; $\neg \neg B\vee \neg A$; $\neg B\Rightarrow \neg A$.) This gives some other options for dealing with implication.

Rule.

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

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 $\left({a}_{n}\right)$ defined by ${a}_{n}={\left(-1\right)}^{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 $\left({a}_{n}\right)$ converges to some limit is

$$\exists l\in \mathbb{R}\forall \epsilon 0\exists N\in \mathbb{N}\forall n\in \mathbb{N}(n\u2a7eN\Rightarrow \left|{a}_{n}-l\right|\epsilon )$$So the statement that it does not converge to any limit is

$$\forall l\in \mathbb{R}\exists \epsilon 0\forall N\in \mathbb{N}\exists n\in \mathbb{N}(n\u2a7eN\wedge \left|{a}_{n}-l\right|\u2a7e\epsilon )$$We prove this. Since the statement we want to prove starts with a $\forall $ we start a subproof straight away.

**Subproof.**

Let $l\in \mathbb{R}$ be arbitrary.

Remark.

We now need to define a suitable $\epsilon >0$ and prove $\forall N\in \mathbb{N}\exists n\in \mathbb{N}(n\u2a7eN\wedge \left|{a}_{n}-l\right|\u2a7e\epsilon )$. Since the sequence hops between two points distance two away any $\epsilon $ a bit less than $2$ should work. There are no prizes for choosing the "best" $\epsilon $, however.

**Subproof.**

Define $\epsilon $ to be $\frac{1}{2}$. Note that $\epsilon >0$.

Remark.

We now want to prove a statement starting $\forall N\in \mathbb{N}\dots $ so we let $N$ be arbitrary.

**Subproof.**

Let $N\in \mathbb{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}\u2a7e{n}_{1}=N\u2a7eN$, so both are greater than or equal to $N$. We now argue using cases.

**Subproof.**

Case 1: suppose $\left|{a}_{{n}_{1}}-l\right|\u2a7e\epsilon $.

In this case ${n}_{1}$ is a natural number that shows that $\exists n\in \mathbb{N}(n\u2a7eN\wedge \left|{a}_{n}-l\right|\u2a7e\epsilon )$.

**Subproof.**

Case 2: suppose $\left|{a}_{{n}_{1}}-l\right|<\epsilon $.

Then if $\left|{a}_{{n}_{2}}-l\right|<\epsilon $ we would have

$$\left|{a}_{{n}_{1}}-{a}_{{n}_{2}}\right|\u2a7d\left|{a}_{{n}_{1}}-l\right|+\left|{a}_{{n}_{2}}-l\right|<\frac{1}{2}+\frac{1}{2}=1$$by the triangle inequality. But this is impossible as $\left|{a}_{n}-{a}_{n+1}\right|=2$ for all $n$ as ${a}_{n}={\left(-1\right)}^{n}$. Thus $\left|{a}_{{n}_{2}}-l\right|\u2a7e\epsilon $ and ${n}_{2}$ is a natural number that shows that $\exists n\in \mathbb{N}(n\u2a7eN\wedge \left|{a}_{n}-l\right|\u2a7e\epsilon )$.

In both cases we have shown $\exists n\in \mathbb{N}(n\u2a7eN\wedge \left|{a}_{n}-l\right|\u2a7e\epsilon )$.

So $\forall N\in \mathbb{N}\exists n\in \mathbb{N}(n\u2a7eN\wedge \left|{a}_{n}-l\right|\u2a7e\epsilon )$.

So $\exists \epsilon >0\forall N\in \mathbb{N}\exists n\in \mathbb{N}(n\u2a7eN\wedge \left|{a}_{n}-l\right|\u2a7e\epsilon )$.

So $\forall l\in \mathbb{R}\exists \epsilon 0\forall N\in \mathbb{N}\exists n\in \mathbb{N}(n\u2a7eN\wedge \left|{a}_{n}-l\right|\u2a7e\epsilon )$.

This proof is complicated to write down fully, but the idea of taking $\epsilon $ to be
smaller than the distance between the two values 1 and -1 is clear.
(Taking $\epsilon =1$ would have been OK too, but there are no prizes for
giving the best

$\epsilon $.) Note that
there is an implicit embedded

reductio ad absurdum inside the proof
where we had assumed both $\left|{a}_{{n}_{1}}-l\right|<\epsilon $ and
$\left|{a}_{{n}_{2}}-l\right|<\epsilon $. 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.)