Read this short proof:

Claim. The sum of two even numbers is even.

Proof. Let $m$ and $n$ be even numbers. Then there are integers $a$ and $b$ such that $m=2a$ and $n=2b$. Hence $m+n=2a+2b=2(a+b)$. Since $a+b$ is an integer, $m+n$ is even. $\blacksquare$

Take away the calculations and a skeleton of words is left: let, then there are, hence, since, and a little black square at the end. None of them is mathematics in the sense of calculating, and all of them are indispensable. They are what tell the reader what each line is doing: introducing an object, drawing a consequence, invoking a fact, closing.

Euclid’s six parts

The Greeks already wrote proofs with a fixed structure. In the fifth century, the philosopher Proclus, commenting on the Elements, described the six parts of a Euclidean proposition:

Part (in Greek) What it does In the proof above
prótasis, enunciation states, in general, what will be proved “the sum of two even numbers is even”
ékthesis, setting-out picks a case and gives it a name “let $m$ and $n$ be even”
diorismós, specification says what is to be proved about that case (implicit) “$m+n$ is even”
kataskeué, construction adds whatever is needed “there are $a$ and $b$ with $m=2a$, $n=2b$”
apódeixis, proof chains the consequences “$m+n=2(a+b)$”
sympérasma, conclusion returns to the general statement “$m+n$ is even”

The cleverest part is the setting-out. The statement speaks of all even numbers; the setting-out picks two, $m$ and $n$, and treats them as if they were particular. But since nothing was assumed about them other than being even, everything proved about $m$ and $n$ holds for any even numbers. The word “let” is the bridge between the general and the particular. It is the same generalising letter of chapter 3, now put to work inside a proof.

What was to be shown

Euclid ended each proposition with a formula: hóper édei deîxai, “which was to be shown”. When the proposition was a construction, like that of the equilateral triangle presented in chapter 1, the formula changed to hóper édei poiêsai, “which was to be done”. The Latin translators rendered the two as quod erat demonstrandum and quod erat faciendum, and abbreviated them: Q.E.D. and Q.E.F.

In the twentieth century, the Hungarian-American mathematician Paul Halmos replaced the letters with a sign: a small black square, $\blacksquare$. He said he took the idea from magazines, which used such a mark to show the end of an article. Readers call the sign the tombstone, or simply the halmos. Halmos also popularised the abbreviation iff, “if and only if”.

An older sign, less used today, is $\therefore$, “therefore”. It appears in 1659, in the German Algebra of the Swiss Johann Rahn, and English books later gained its inverted sibling, $\because$, “because”. These are signs that represent no mathematical object: they represent the movement of reasoning.

Words that open and close

Some words of a proof work like parentheses. Look at the classic proof that there is no largest even number:

Proof. Suppose, for contradiction, that there is a largest even number, $N$. Then $N+2$ is also even, and $N+2>N$. This contradicts the choice of $N$. Hence there is no largest even number. $\blacksquare$

The “suppose” opens a provisional hypothesis, which is not true: inside it, such an $N$ exists. The “contradiction” closes the hypothesis, and the “hence” that follows is already outside, where $N$ no longer exists. Inside the parenthesis, the letter $N$ has a meaning; outside, it does not. This is exactly the scope of the bound letters that chapter 3 studied in sums and integrals, now applied to whole sentences.

A reader who does not notice these openings and closings gets lost. A student who reads the proof above as a sequence of true statements concludes that there is a largest even number, called $N$, and is then confused by the contradiction. Twentieth-century logic, with Gerhard Gentzen, drew proofs as trees precisely to make visible where each hypothesis opens and closes.

Exercise: write it with the six parts

Prove that the sum of two odd numbers is even, marking the parts.

Enunciation: the sum of two odd numbers is even. Setting-out: let $m$ and $n$ be odd. Specification: we want to show that $m+n$ is even. Construction: there are integers $a$ and $b$ with $m=2a+1$ and $n=2b+1$. Proof: $m+n=2a+2b+2=2(a+b+1)$. Conclusion: since $a+b+1$ is an integer, $m+n$ is even. $\blacksquare$

Exercise: where does it open and where does it close?

In the proof below, mark where the provisional hypothesis begins and ends.

Suppose that $\sqrt2=\frac pq$, with the fraction in lowest terms. Then $p^2=2q^2$, so $p^2$ is even and $p$ is even: $p=2r$. Then $4r^2=2q^2$, $q^2=2r^2$, and $q$ is also even. But then $p$ and $q$ have the factor $2$ in common, against the choice of the fraction. Hence $\sqrt2$ is not a fraction.

The hypothesis opens at “suppose” and closes at “against the choice of the fraction”. Everything in between, $p$, $q$, $r$, exists only inside the parenthesis. The final “hence” is outside and states something true without using any of those letters.

Chapter index · ← The chain of equalities: how an identity is proved · Examples do not prove: Euler, Pascal and induction →