What is a proof

Proofs are the cornerstones of the whole of maths. With proofs you can build an entire pyramid out of a few small pebbles, and an upside-down one at that.

The point of proofs

Proofs matter in maths for several reasons. The main one is that without proofs we cannot confirm any idea or hypothesis that occurs to us. We might, for example, believe that there are only finitely many prime numbers, but without a proof this remains an empty statement. On the other hand, even unproved statements make sense in maths (and elsewhere). We simply say that if we assume there are only finitely many primes, then… some other theory holds.

But then we must not be surprised if someone proves after a while that there are infinitely many primes, as we will show below, and our whole theory collapses like a house of cards. Proofs let us build houses of cards that never collapse.

The reason proofs are taught in schools is that whoever understands a proof also understands the topic itself. It is hard to understand a topic thoroughly without understanding the proofs. I highlighted the word “understanding” on purpose: if you learn proofs by heart the day before an exam and then spew them out onto paper the next day, that does not mean you are any closer to understanding the subject.

When you are learning a topic, proofs answer the question “why does it work like this?” If you understand why something works, you remember it more easily, and after a while you will understand the topic far better than someone who learned it by rote, the “pour in, pour out” way. The question is whether that is your goal.

What is a proof

A proof is defined formally in mathematical logic, for example using syntactic entailment, but a much simpler definition will do for us.

At the start of every proof we need a statement that we want to prove. We denote this statement by the magic symbol ϕ. It is a Greek letter, read “phi”. We also need a set of axioms and assumptions, which we denote Ax, and from which we will prove the statement ϕ. The set of axioms is what we already know, what we assume to be true. These can be things like “every even number is divisible by two”. The set can also contain, for example, formulae for rearranging expressions that have been proved elsewhere and that we already assume to be true, such as:

$(a + b)^{2} = a^{2} + 2 a b + b^{2}; a, b \in R$

Now we gradually transform the statements in the set Ax until we obtain the statement ϕ. All the steps must be logically correct and must follow basic propositional logic. For example, if we wanted to prove the formula above, we would take the expression

$(a + b)^{2}$

and transform it using equivalent steps until we reach the expression on the right-hand side. Here is how it goes:

$(a + b)^{2} = (a + b) \cdot (a + b) = a \cdot a + a \cdot b + b \cdot a + b \cdot b =$

$= a \cdot a + 2 a b + b \cdot b = a^{2} + 2 a b + b^{2}$

In the first step we wrote the power as a product, in the second step we expanded the brackets, in the third step we added the like terms and in the last step we wrote the product as a power. Each step was an elementary manipulation that we were allowed to make, and we assume that each of these elementary manipulations is contained in the set Ax.

What matters is that every step must be valid and must rest on something we already know. A mathematical proof is a bit like evolution: through gradual small changes we get from one expression to another.

Trivial proofs

A trivial proof (or obvious proof) is the technical term for a proof that does not fit on the board, so it gets skipped and the student learns it from the lecture notes as homework. :-) Seriously though, trivial proofs are proofs that typically follow from a definition in a single trivial step.

Let’s try it on an example: take the set of positive integers, that is, the set of numbers ℤ⁺ = {1, 2, 3, …}. We can now say that every fraction of the form

$\frac{q}{p}; q, p \in Z^{+}$

is a valid fraction, that is, we will not find any pair of numbers q, p for which the fraction would make no sense. How would we prove it? First we need to work out when a fraction makes no sense. A fraction makes no sense when the denominator is zero (we cannot divide by zero). So we need to prove that p ≠ 0 for every possible p. But we know that p is taken from the positive integers, which we defined as ℤ⁺ = {1, 2, 3, …}. The set of positive integers does not contain zero, so p will always be different from zero.

$\forall p \in Z^{+} : p \neq 0$

And that is the proof done. We know that if both the numerator and the denominator of a fraction are positive integers, the fraction is valid.

Trivial proofs usually really are trivial, but only if you know the surrounding context. For example, if you do not understand the notion of a set, or do not know what it means for p to be an element of the set ℤ⁺, then even this proof was not trivial for you. So trivial proofs are not characterised by being simple so much as by being short and following easily from some context (of any difficulty).

Counterexample

A counterexample is probably the simplest way to prove that a given statement is not true. The word “not” is important here. A counterexample can point out a case where the statement fails, but in general no number of examples is enough when there are infinitely many elements we could test.

Example: “every positive integer is greater than ten”. How do we prove that this is not true? A counterexample to our statement is the number five, for instance. Five is a positive integer and it is not greater than ten. We cannot prove the statement by listing several positive integers that are greater than ten. You cannot say “the positive integers 11, 12, 13, 123 and 5,345 are greater than 10, so the statement is true”. That does not work. We have merely picked a few examples for which our statement holds, which says nothing about the other numbers we have not mentioned at all.

Second example: every man taller than two metres has brown or blue eyes. I suspect that hardly anyone is able to find a counterexample. What does that tell us about the statement? Well, nothing at all. If we cannot find a counterexample, it does not necessarily mean that the statement is true. A counterexample may exist somewhere, we just happen not to be able to find it. Failing to find a counterexample does not prove that the statement is true.

Direct proof

The basic type of proof is the direct proof. We simply follow the definition and transform the initial statement until we get the statement we want. Typically we want to prove a statement in the form of an implication A ⇒ B, where A is some starting point, an assumption, and B is the statement we want to derive, to prove. If statement A holds, then statement B holds. Often we are given only statement B, that is, what we want to prove, and we have to choose a suitable statement A ourselves.

What follows is a procedure in which we use implications to derive further statements, and the last statement is statement B. Schematically, it could be written like this:

$A \Rightarrow A_{1} \Rightarrow A_{2} \Rightarrow A_{3} \Rightarrow \dots \Rightarrow A_{n} \Rightarrow B$

As an example, let’s prove that the statement

$a > 1 \Rightarrow a^{2} > 1$

holds. Now step by step:

Since a>1, it certainly also holds that a>0 and a ≠ 0 (we are really just weakening the condition).
Since a is not equal to zero and is positive, we can safely multiply the whole inequality by a. If a were zero, the strict inequality would not be preserved (we would get 0>0), and if it were negative, we would have to reverse the inequality. After multiplying by a we get a²>a.
At this point we know that a>1 and we also know that a²>a. If we put these two together, we get a²>a>1.
From here we simply remove the middle expression and have a²>1. We could allow ourselves to do this because a is greater than one and a² is greater than a. If a² is greater than a and a is greater than one, then a² is certainly greater than one.

Symbolically, we could write it like this:

$a > 1 \Rightarrow a > 0 \Rightarrow a^{2} > a \Rightarrow a^{2} > a > 1 \Rightarrow a^{2} > 1.$

Indirect proof

An indirect proof makes more use of the properties of implication. If we need to prove a statement of the form A ⇒ B, we can use the contrapositive and prove

$\neg B \Rightarrow \neg A .$

This approach can sometimes be more convenient than, say, a direct proof. A similar approach is used by proof by contradiction, to which every indirect proof can be converted. Let’s try to prove indirectly the statement

$a - b = 0 \Rightarrow a = b .$

Now we take the contrapositive of the implication:

$\begin{array}{rcl} \neg (a = b) & \Rightarrow & \neg (a - b = 0) \\ a \neq b & \Rightarrow & a - b \neq 0 \end{array}$

If a ≠ b, we can split b into the sum b = a + x, where x is the distance of b from a. The expression changes like this:

$a \neq (a + x) \Rightarrow a - (a + x) \neq 0; x \neq 0$

We subtract the as that we can:

$0 \neq x \Rightarrow - x \neq 0; x \neq 0$

Since x ≠ 0, also −x ≠ 0, so the implication holds. The statement is proved, which means that the original statement holds as well:

$a - b = 0 \Rightarrow a = b .$

Other proof techniques include the proof by contradiction already mentioned, or proof by induction.

Further sources

Mathematical proof on Wikipedia

Chapters: What is a proof, Proof by contradiction, Mathematical induction

« Previous: Pascal’s triangle

Next: Proof by contradiction »