Proof

Cartoon about mathematical proof

Mathematics is largely based on logic – a structure of rules used for reasoning.

Most of maths is written as statements: words or symbols which contain information.

A statement may be true or false, and is made from axioms, assumptions and arguments.

An axiom is a statement which is assumed to be true, and is used to then develop a system. All logical systems must state their axioms.

An assumption, or premise, is a statement which may in reality be true or false but is taken to be true for the argument which follows.

Cartoon about axioms and assumptions

An argument is a set of statements which use logic to show how one particular statement occurs.

A proposition is a statement whose truth is to be shown by the use of an argument.

A conjecture is a proposition which appears to be true, but has not yet been proved.

A theorem is a statement which has been proved to be true.

A lemma is a theorem which is used in the proof of another theorem.

A lemming is a small rodent which jumps off cliffs.

Cartoon about lemmas and lemmings

The converse of a theorem or statement takes the conclusion as the starting point, and the starting point as the conclusion.

The inverse of a statement changes its polarity.

The contrapositive of a statement is the negation of the converse.

Diagram of statement, converse, inverse and contrapositive

The negation of a statement is made by putting a NOT in it!

Example

If it rains today, we shall have cake tomorrow.
inverse: If it does not rain today, we shall not have cake tomorrow.
converse: We shall have cake tomorrow if it rains today.
contrapositive: We shall not have cake tomorrow if it does not rain today.

A proof is a sequence of statements which lead to the establishment of the truth of one final statement.

A proof may be valid or invalid, depending on whether or not the arguments used are correct. One counter-example will show a statement to be invalid, which will make the proof invalid.

Notation

Proof has its own notation:

\[ \therefore\;\text{ therefore} \] \[ \because\;\text{ because or since} \] \[ \exists\;\text{ there exists} \] \[ \ni\;\text{ contains as member} \] \[ \in\;\text{ is an element of} \] \[ \notin\;\text{ is not an element of} \]

\[ \forall\;\text{ for all} \] \[ \neg\;\text{ Not} \] \[ \land\;\text{ And} \] \[ \lor\;\text{ Or} \] \[ \Rightarrow\;\text{ Implies} \] \[ \Leftarrow\;\text{ Is implied by} \] \[ \Leftrightarrow\;\text{ is equivalent to, if and only if} \]

\[ \,b|\,a \quad\text{meaning “b divides a”} \] \[ \text{so}\qquad a = kb,\quad k \in W \]

Direct proof

This is proof in which all the assumptions used are true, and all the arguments are valid.

A series of linked implications lead from a given statement to a declared goal. The original statement is given to be true, implying the declared goal is also true.

Example

Given \(x\) is an even number, prove \(x^2\) is an even number.

\[ \text{ x is even} \] \[ \Rightarrow\; x = 2k,\quad k \in W \] \[ \Rightarrow\; x^{2} = (2k)^{2} \] \[ \Rightarrow\; x^{2} = 4k^{2} \] \[ \Rightarrow\; x^{2} = 2(2k^{2}) \] \[ \text{Since x is even (given)} \] \[ \therefore\; x^{2}\ \text{is even} \]

Example

Prove that the arithmetic series with first term \(a\) and common difference \(d\) can be summed as shown:

\[ S_n = \frac{n}{2}\bigl(2a + (n-1)d\bigr). \]

Write the sum forwards and backwards:

\[ S_n = a + (a+d) + (a+2d) + \cdots + \bigl(a + (n-1)d\bigr), \]

\[ S_n = \bigl(a + (n-1)d\bigr) + \bigl(a + (n-2)d\bigr) + \cdots + a. \]

Add term by term:

\[ 2S_n = \bigl(2a + (n-1)d\bigr) + \bigl(2a + (n-1)d\bigr) + \cdots \quad (\text{n terms}) \]

\[ 2S_n = n\bigl(2a + (n-1)d\bigr) \quad \Rightarrow \quad S_n = \frac{n}{2}\bigl(2a + (n-1)d\bigr). \]

Indirect proof (proof by contradiction)

One assumption is made which is the negation of the statement to be proved. Valid arguments are then used to arrive at a statement which is clearly false. This contradiction then makes the original assumption false, thus making the statement to be proved true.

Example

Show by contradiction that the square root of any prime number is irrational.

\[ \text{Assume that a prime number } p \text{ exists} \] \[ \text{with a rational square root.} \] \[ \sqrt{p} = \frac{a}{b} \] \[ \Rightarrow\; p = \frac{a^{2}}{b^{2}} \] \[ \Rightarrow\; b^{2} = 1 \quad\text{since } p \text{ is an integer} \] \[ \therefore\; p = a^{2} \] \[ \Rightarrow\; p \text{ cannot be a prime number} \] \[ \text{A contradiction exists,} \] \[ \text{thus the square root of any prime number is irrational.} \]

Proof by contrapositive

Similar to proof by contradiction, however this time the contrapositive is used: instead of a contradiction, the aim is to prove that if statement A implies statement B, then NOT B implies NOT A.

Example

Prove that if \(x = 89\) then \(x\) is not divisible by 3.

\[ \text{If } x \text{ is divisible by 3, then it has no remainder} \] \[ \Leftrightarrow\; \text{If } x \text{ has a remainder upon division by 3,} \] \[ \qquad\text{then } x \text{ is not divisible by 3.} \] \[ 89 \div 3 \text{ has a remainder} \] \[ \Rightarrow\; 89\;\cancel{\div} \;3 \] \[ \Rightarrow\; x\;\cancel{\div} \;3 \]

Proof by induction

A conjecture is made and shown to be true for numbers \(n\) and \(n+1\).
Then it is shown to be true for a specific low number.
This then leads to the conclusion that it will be true for all values of \(n \ge\) the specific value proved in step 2.

Note: The order of these steps does not matter.

Example

\[ \text{Prove by induction that } 2^{n} > n,\quad \forall n \in \mathbb{N} \]

\[ \text{Assume it is true when } n = k \] \[ 2^{k} > k \] \[ \Rightarrow\; 2 \times 2^{k} > 2k \] \[ \Rightarrow\; 2^{k+1} > 2k \] \[ \Rightarrow\; 2^{k+1} > k + k \] \[ \text{but } k \ge 1 \text{ since } n \in \mathbb{N} \] \[ \Rightarrow\; 2^{k+1} > k + 1 \] \[ \Rightarrow\; \text{the statement is valid for } n = k + 1 \]

\[ \text{Let } n = 1 \] \[ \text{then } 2 > 1 \text{ so the statement is valid.} \] \[ \text{The statement is true for } n = k \text{ (given), } n = k+1 \text{ and } n = 1 \] \[ \therefore\; \text{by induction, } 2^{n} > n,\quad \forall n \ge 1,\; n \in \mathbb{N} \]

Proof by exhaustion

Cartoon about proof by exhaustion

Here, a proof is made by showing that the statement holds for every single possible case.