What is a proof?

Why examples are not enough, what a proof is built from, and a first proof using the triangle of dots of the tetractys: 1 + 2 + 3 + 4 = 10, and why it continues the same way for every number.

This website contains statements such as “The decagon is the only simplex whose figures have an angle sum equal to its number of corners.” Perhaps someone drew the simplexes up to the hundred-gon. How do we know, then, that a tie does not turn up again at the thousand-gon, or at a number with a hundred digits? Mathematics answers with a proof. This section explains step by step what that is, and proves the most important statements of the site in a way that lets you follow every step yourself.

Why examples are not enough

In 1772 Leonhard Euler found an astonishing formula. If you put the numbers 0, 1, 2, 3 … for n into

f(n) = n^2 + n + 41

you get 41, 43, 47, 53, 61, 71 …, all of them prime. It works forty times in a row. Anyone who stops after twenty examples believes they have found a formula for primes. But at n = 40 the result is

f(40) = 1600 + 40 + 41 = 1681 = 41^2,

which is not prime. In symbols: $f(n)$ is prime for all $n \in \{0, 1, \dots, 39\}$ , but not for all $n \in \mathbb{N}_0$ . How to read such lines is explained in the chapter The language of mathematics.

Forty correct examples prove nothing about the forty-first. That is why this website distinguishes three kinds of statement:

A theorem is proven and holds for all numbers, including those nobody has ever written down.
A finding has been checked for many numbers but not yet proven in general.
An interpretation is a way of reading things. It may be convincing or not, but it can be neither proven nor refuted.

All three have their place. One should simply know which one is in front of you.

What a proof is built from

A proof is a chain of steps in which every step follows necessarily from the previous ones. But the chain has to start somewhere. There are three building blocks:

Axiom

An axiom is a basic assumption that is not proven but placed at the beginning. For example: every natural number has a successor, $\forall n \in \mathbb{N}: \; n + 1 \in \mathbb{N}$ .

Definition

A definition fixes what a word is to mean. For example: the n-th triangular number is $T(n) := \sum_{i=1}^{n} i = 1 + 2 + \dots + n$ .

A theorem, finally, is a statement that follows from axioms and definitions, and the proof is the way there. That is all. Whoever accepts the axioms and checks each step must accept the theorem too, like it or not. This is the peculiar strength of mathematics: a proof does not convince through reputation or majority, but because you can walk through it yourself.

A first proof

The tetractys is the fourth triangular number: 1 + 2 + 3 + 4 = 10. Is there a shortcut for working out a triangular number without adding all the numbers? The Pythagoreans laid out numbers with pebbles, and that is exactly how to find it.

A triangle of dots and a turned copy of it together make a rectangle. The slider changes n. The trick works every time.

The idea in words: lay out the triangle of dots with rows 1, 2, …, n, and next to it a copy turned through half a turn, with rows n, n − 1, …, 1. In each row there are then n + 1 dots together, and there are n rows. Two triangles make a rectangle, and one triangle is half of it. In the notation of mathematics it looks like this:

Theorem 1

For all $n \in \mathbb{N}$

T(n) = \sum_{i=1}^{n} i = \frac{n(n+1)}{2}.

Proof

Let $n \in \mathbb{N}$ . We write the sum once forwards and once backwards:

\begin{aligned} T(n) &= 1 + 2 + \dots + n, \\ T(n) &= n + (n-1) + \dots + 1. \end{aligned}

Adding the terms that stand one above the other, each pair gives $i + (n + 1 - i) = n + 1$ . There are $n$ pairs, so

\begin{aligned} 2\,T(n) &= \sum_{i=1}^{n} \bigl(i + (n+1-i)\bigr) \\ &= n(n+1), \end{aligned}

and dividing by 2 gives the claim.

∎

The two lines one above the other are exactly the two triangles in the picture, the pairs are the rows of the rectangle. For the tetractys this gives $T(4) = \tfrac{4 \cdot 5}{2} = 10$ , for the hundredth triangular number $T(100) = 5050$ , without adding a hundred numbers. The young Carl Friedrich Gauss is said to have found this calculation at school, when his teacher wanted to keep the class busy with exactly this sum.

What matters is why this is a proof and not just one more example. The picture shows one particular n, but no step of the argument depends on which one. The rows always add up to n + 1, for 4 as for a million. A picture is a proof when you can see from it that it would work the same way for every number.

And if you do not trust the picture?

Pictures can deceive, and for large numbers they can no longer be drawn. That is why there is a second route that needs no picture at all, mathematical induction. It works like a row of dominoes:

The first domino falls: for n = 1 the formula is right.
Each domino knocks over the next: if the formula holds for a number n, it also holds for n + 1.

So all the dominoes fall, and the formula holds for every number. As a proof in the notation of mathematics:

Second proof of Theorem 1, by induction

Base case. For $n = 1$ we have $T(1) = 1 = \frac{1 \cdot 2}{2}$ .

Inductive step. Let $n \in \mathbb{N}$ and suppose $T(n) = \frac{n(n+1)}{2}$ (induction hypothesis). Then

\begin{aligned} T(n+1) &= T(n) + (n+1) \\ &= \frac{n(n+1)}{2} + \frac{2(n+1)}{2} \\ &= \frac{(n+1)(n+2)}{2}, \end{aligned}

which is the formula for $n+1$ .

∎

Why we may trust this conclusion is a deep question. It leads straight to the axioms of the natural numbers, which are the subject of the next chapter.

Checked by computer

For some decades now proofs can also be checked by a computer. A proof assistant such as Lean knows the axioms and the permitted rules of inference and lets no step pass that does not follow necessarily. It cannot be bribed: one slip in a calculation, one gap or one case nobody thought of, and it refuses its consent. Mathematicians now use it for large proofs that no single person can survey any more.

On this website important theorems are therefore followed by a box that unfolds to show the proof in Lean. You do not need to read it. It is a seal of approval: this theorem has been checked step by step not only by people but also by a machine. If you are curious you can run and change the code yourself in the browser.

Checked by computer: the proof in Lean

First the triangular number is defined: the zeroth is 0, and the next one comes from adding n + 1. The line with rfl checks the tetractys simply by calculating. The theorem two_triangles is the formula of Theorem 1, multiplied by 2 so that no fractions appear. It is proven exactly as above by induction: zero is the first domino, succ the step from n to n + 1.

/-- The n-th triangular number 1 + 2 + … + n -/
def triangle : Nat → Nat
  | 0 => 0
  | n + 1 => triangle n + (n + 1)

-- The tetractys: 1 + 2 + 3 + 4 = 10
example : triangle 4 = 10 := rfl

/-- Theorem 1: Two triangles make a rectangle
    of n rows and n + 1 columns. -/
theorem two_triangles (n : Nat) :
    2 * triangle n = n * (n + 1) := by
  induction n with
  | zero => rfl
  | succ n ih =>
    -- 2 · triangle n + 2 · (n + 1)
    --   = n · (n + 1) + 2 · (n + 1) = (n + 1) · (n + 2)
    rw [triangle, Nat.mul_add, ih]
    grind

Try it in the browser at live.lean-lang.org ↗How to read Lean

Where the axioms come from

The Pythagoreans probably still proved their theorems about numbers the way the picture above does, with pebbles and seeing. Aristotle reports that the Pythagorean Eurytus copied the numbers of things with pebbles.

The step to axioms was taken around 300 BC by Euclid of Alexandria. His Elements begin with definitions, five postulates and five common notions, and from these they derive, theorem by theorem across thirteen books, the whole of the geometry and number theory of the time. For almost two thousand years the book was the model of rigorous thought as such. The natural numbers themselves received their axioms very late, in 1888 from Richard Dedekind and in 1889 from Giuseppe Peano. In 1899 David Hilbert rewrote Euclid’s geometry once more in strict axiomatic form.

Logically, then, proof comes first, but historically it came after the discoveries it secures. The same holds for this section. The Pythagoreans knew the tetractys long before anyone proved what is remarkable about it. The map at the start of each chapter shows both: where an idea stands in the structure, and when it appeared in history.

How these few building blocks lead to the star figures of the simplexes is shown in the chapter Numbers as figures.

Sources and further reading

Sources

Euclid, Elements, around 300 BC
Richard Dedekind, Was sind und was sollen die Zahlen?, Brunswick 1888
Giuseppe Peano, Arithmetices principia, nova methodo exposita, Turin 1889
David Hilbert, Grundlagen der Geometrie, Leipzig 1899
Leonardo de Moura et al., The Lean Theorem Prover, Automated Deduction, CADE-25, LNCS 9195, Cham 2015