Mathematical Proof (Prf1–Prf5)

Introduction

Proof is central to mathematics; but what is proof, and why is it so important?

In simple terms a proof is an explanation of why a statement is true. More specifically the proof is a rigorous and convincing explanation of why some statement is true: rigorous in that it must obey mathematical and logical rules throughout; and convincing in that it should be clear enough to convince other mathematicians of its correctness. Proofs can be one line long, or they can be very complicated and lengthy, or they can be anything in between. In this section we look at a selection of specific methods of proof; more specifically, we will concentrate on:

• Simple deductive proofs
• Proof by contradiction
• Proof by contrapositive
• Disproof by counterexample

Direct deductive proofs

A direct deductive proof runs 'Since A, therefore B, therefore C, ..., therefore Z, which is what we wanted to prove'.

Simple deductive proofs tend to ask us to prove if A then B type statements. The proof begins with a simple statement A that we take to be true and then proceeds through a sequence of smallish, and usually obvious, steps [lots of uses of if...then...] each one following from the previous ones. The proof finishes when it reaches the statement B which is to be proved. Here is an example.

Let us prove:

if $x$ is divisible by 3 then $x^2$ is exactly divisible by 9

We shall start with $x$ is divisible by 3 and keep using if...then... statements until we reach $x^2$ is divisible by 9. Each if...then... carries the truth of the first statement along with it [because we are using logically valid steps] until we reach the final statement, the conclusion. The conclusion must be true because we will have shown that its truth follows directly from the truth of the first statement in the sequence.

Proof:

1. $x$ is divisible by 3
2. if $x$ is divisible by 3 then $x = 3n$, where $n$ is an integer
3. if $x = 3n$ then $x^2 = 9n^2$
4. if $x^2 = 9n^2$ then $x^2$ has 9 as a factor
5. if $x^2$ has 9 as a factor then $x^2$ is divisible by 9

and so we can conclude that

if $x$ is divisible by 3 then $x^2$ is divisible by 9

We can rewrite this proof more succinctly using some formal notation; remember another way of stating if A then B is by saying A implies B, and in symbols, this is written as A $\Rightarrow$ B. We can rewrite our proof as follows (using $\Rightarrow$ rather than mixing in $\Leftrightarrow$):

• $x$ is divisible by 3
• $\Rightarrow x = 3n$, where $n$ is an integer
• $\Rightarrow x^2 = 9n^2$
• $\Rightarrow x^2$ has 9 as a factor

$$\Rightarrow x^2 \text{ is divisible by } 9$$

What we have done here is combine each line with the next, so rather than writing

$$\begin{array}{l} x \text{ is divisible by } 3 \Rightarrow x = 3n \\ x = 3n \Rightarrow x^2 = 9n^2 \\ \text{etc} \end{array}$$

we avoided repeating ourselves line by line by writing:

$$\begin{array}{l} x \text{ is divisible by } 3 \\ \Rightarrow x = 3n \\ \Rightarrow x^2 = 9n^2 \\ \text{etc} \end{array}$$

We can now look at the general structure of these simple deductive proofs. If we are asked to prove $\mathbf{A} \Rightarrow \mathbf{B}$ we move from $\mathbf{A}$ to $\mathbf{B}$ in a series of small steps:

$$\mathbf{A} \Rightarrow \mathbf{P}, \mathbf{P} \Rightarrow \mathbf{Q}, \mathbf{Q} \Rightarrow \mathbf{R}, \mathbf{R} \Rightarrow \mathbf{B}$$

Which we can write more briefly as:

$$\mathbf{A} \Rightarrow \mathbf{P} \Rightarrow \mathbf{Q} \Rightarrow \mathbf{R} \Rightarrow \mathbf{B}$$

As we mentioned above, this works because we make sure that each step inherits truth from the previous step: remember that if $\mathbf{P}$ is true and $\mathbf{P} \Rightarrow \mathbf{Q}$ is true then $\mathbf{Q}$ is true and so on – and we make sure that $\mathbf{P}$ is true and $\mathbf{P} \Rightarrow \mathbf{Q}$ are true by working through a proof of if $\mathbf{A}$ then $\mathbf{B}$ in small steps starting at $\mathbf{A}$ and ending at $\mathbf{B}$.

Proof by contradiction

Another type of proof you need to know about is called "proof by contradiction". We shall start this section by setting out a proof that $\sqrt{2}$ is irrational using this method. We shall then explore how this type of proof works in a little more detail.

To prove: $\sqrt{2}$ is irrational

Proof: We start by assuming that $\sqrt{2}$ is not irrational, that is we assume that $\sqrt{2}$ is rational. If $\sqrt{2}$ is rational it can be written as a fraction in its lowest terms; that is, we can write:

$\sqrt{2} = \frac{a}{b}$

where $a$ and $b$ have no factors in common. Squaring both sides gives us:

$2 = \frac{a^2}{b^2}$

which gives:

$2b^2 = a^2$

From this we can see that $a^2$ is even. For $a^2$ to be even, $a$ itself must be even (this step could itself be proved but it is a generally accepted statement). And if $a$ is even then $a^2$ is divisible by 4. If $a^2$ is divisible by 4 then $b^2$ must also be even. For $b^2$ to be even, $b$ must be even. Thus, we have $a$ is even and $b$ is even. This contradicts the assumption that $\frac{a}{b}$ is a fraction in its lowest terms. This assumption must, therefore, have been false; that is, our assumption that $\sqrt{2}$ is rational must have been false so $\sqrt{2}$ must, in fact, be irrational.

What have we done here? We have taken what we wanted to prove, that $\sqrt{2}$ is irrational, and assumed that it is not true. We have then, through a series of valid logical steps, derived a contradiction. In this case our contradiction is found between our assumption that $\sqrt{2}$ is rational and so can be expressed as a fraction in its lowest terms and the conclusion that both $a$ and $b$ are even. As we have used nothing but valid logical steps from start to finish, our assumption must have been incorrect. Our assumption was that $\sqrt{2}$ is rational and this must have been incorrect.

We can now set out the general structure of proof by contradiction:

• We are asked to prove some statement A.
• We start by assuming not A is true.
• We then show that not A leads us to two contradictory statements, B and not B.
• As B and not B cannot both be true our assumption that not A was true must have been an error.
• If not A is false, then A must be true.

Exercise O

1. Replace 2 by 9 in the proof that $\sqrt{2}$ is irrational. Why does the proof no longer work?
2. Can you adapt the proof that $\sqrt{2}$ is irrational to show that $\sqrt{p}$ is irrational for all prime $p$?

Proof by contrapositive

If we are asked to prove if A then B we can try to prove the contrapositive instead as sometimes this can turn out to be much easier. Remember that the contrapositive of if A then B is if not B then not A and these statements are logically equivalent – i.e. both expressions say the same thing. Because if not B then not A is the very same thing as if A then B we can prove the contrapositive of a statement instead of proving the statement itself.

Here is an example. Prove the following by using the statement's contrapositive:

for any non zero integer x: if $x^3$ is odd then $x$ is odd

The contrapositive of this statement says

for any non zero integer x: if $x$ is not odd then $x^3$ is not odd

And we note that for integers 'not odd', means 'even' so we need to prove

for any non zero integer x: if $x$ is even then $x^3$ is even

We can construct this proof:

1. If $x$ is even then $x = 2p$ for some integer $p$
2. If $x = 2p$ then $x^3 = 8p^3$
3. And as $8p^3 = 2(4p^3)$ and as $p$ is an integer then $4p^3$ is an integer
4. Therefore $x^3 = 2 \times \text{integer}$
5. Therefore $x^3$ is even
6. Therefore we can state 'if $x^3$ is odd then $x$ is odd' is true.

Disproof by counterexample

A counterexample to a statement is an example that shows clearly that the statement must be false. We can show that a statement is false merely by finding a counterexample to the statement. This can be useful as it is a quick way of showing a statement is false. It is also good practice to get into the habit of taking statements you meet apart and trying to discern, using examples, why they are true or false. Here is an example.

Example

Statement: all prime numbers are odd.

Counterexample: 2 is a counterexample because 2 is prime but it is even.

Conclusion: the statement all prime numbers are odd is false.

What about finding a counterexample to more complex statements? How might we set about finding a counterexample to a statement of the form if A then B? First we need to keep in mind that a counterexample is an example where the statement [in this case our statement is if A then B] is false, so we need to find an example for A and for B such that if A then B is false: the only way that if A then B can be false is if we can find an example of statement A that is true and an example of statement B that is false. Let us look at an example of this.

Example

Find a counterexample to the statement: if $x < y$ then $x^2 < y^2$

To find a counterexample to this statement, we need to find values of $x$ and $y$ that make $x < y$ true but which make $x^2 < y^2$ false. A simple counterexample would be: $x = -2$ and $y = 1$.

Exercise P

1. What would constitute a counterexample to a statement of the form:

   • (a) A and B
   • (b) A or B
   • (c) A only if B
   • (d) A iff B

2. Find a counterexample, if one exists, to each of the following:

   • (a) all prime numbers are odd and greater than 4
   • (b) all prime numbers are odd or greater than 37
   • (c) x is prime if and only if x is odd
   • (d) x is odd only if x is prime
   • (e) x is prime only if x is odd
   • (f) for all positive odd integers x: x is prime or x is divisible by some integer k < x