What a proof is and why mathematicians prove things

Up to now most of your mathematics has been about getting answers: solving an equation, differentiating a function, finding the area under a curve. Behind every one of those techniques sits a body of statements that someone has proved, and this course is about that other half of mathematics. A proof is a complete, step-by-step argument showing that a statement must be true, given definitions and facts already accepted. It is not a collection of examples, a picture, a computer search or an appeal to authority, although all of those can help you find a proof. It is a chain of reasoning in which every link can be checked.

Learning to read and write proofs is the main skill that separates first-year calculus from upper-year mathematics. Courses such as MATH-241 (Real Analysis I), MATH-322 (Abstract Algebra I) and MATH-351 (Number Theory) assume you can do it, and MATH-221 (Linear Algebra II) already asks for short proofs. This course gives you the tools in a deliberate order: logic and quantifiers first, then the standard proof techniques, then induction, then the language of sets, functions and relations in which modern mathematics is written. It ends with Cantor's discovery that some infinite sets are larger than others, one of the most surprising results in all of mathematics and a showcase for every technique in the course.

Evidence is not proof

Consider the expression \(n^2 + n + 41\). For \(n = 0\) it gives 41, which is prime. For \(n = 1\) it gives 43, for \(n = 2\) it gives 47, for \(n = 3\) it gives 53. All prime. In fact the values are prime for every \(n\) from 0 to 39, forty cases in a row. Leonhard Euler noticed this pattern in the eighteenth century. It is tempting to conclude that the expression always produces primes, but at \(n = 40\) it gives \(40^2 + 40 + 41 = 1681 = 41^2\), which is not prime. You can see why without computing: \(40^2 + 40 + 41 = 40(40 + 1) + 41 = 41 \cdot 40 + 41 = 41 \cdot 41\).

Forty confirming cases did not establish the pattern. Some patterns break much later. The Pólya conjecture, about how often numbers have an odd versus an even number of prime factors, was checked for all numbers up to many millions before C. B. Haselgrove showed in 1958 that it fails, and the first counterexample turned out to be around 906 million. Mathematicians therefore treat examples as a way to form conjectures and to find proofs, never as a substitute for them.

The opposite also happens: a statement can be true even when it seems impossible to check. There are infinitely many prime numbers. No amount of computing can confirm that, because a computer can only list finitely many. Yet Euclid proved it more than two thousand years ago with an argument that fits in a paragraph, and you will see it in lesson 5. Proof is the only tool that reaches statements about infinitely many cases.

Statements, definitions and theorems

A mathematical statement, also called a proposition, is a sentence that is either true or false, though we may not know which. 'Seven is prime' is a statement (true). 'Every even number greater than 2 is a sum of two primes' is a statement; it is Goldbach's conjecture, and nobody yet knows whether it is true. 'Is seven prime?' is not a statement, and neither is 'x is prime', because its truth depends on what \(x\) is. Sentences with variables like that are called open sentences or predicates, and lesson 3 shows how quantifiers such as 'for all' and 'there exists' turn them into statements.

Proofs rest on definitions, so definitions must be exact. In this course we use the following, and you should learn them word for word.

• An integer \(n\) is even if there is an integer \(k\) with \(n = 2k\). It is odd if there is an integer \(k\) with \(n = 2k + 1\).

• An integer \(a\) divides an integer \(b\), written \(a \mid b\), if there is an integer \(k\) with \(b = ak\).

• An integer \(p > 1\) is prime if its only positive divisors are 1 and \(p\). An integer \(n > 1\) that is not prime is composite.

• A real number \(x\) is rational if there are integers \(a\) and \(b\) with \(b \ne 0\) and \(x = a/b\). A real number that is not rational is irrational.

Look at what the definition of even does. It turns a vague idea, 'divisible by two', into something you can use in algebra: if you are told that \(n\) is even, you may write \(n = 2k\) for some integer \(k\) and calculate with it. Almost every proof in the first half of this course starts by unpacking definitions in exactly this way.

Once a statement has been proved it is called a theorem. A small theorem used to prove a bigger one is a lemma, and an easy consequence of a theorem is a corollary. These words describe the role a result plays, not how hard it was to prove. A statement believed to be true but not yet proved is a conjecture. Axioms are the starting statements that we accept without proof, such as the basic rules of arithmetic for integers; in this course we take the usual algebra of integers, rational numbers and real numbers as given.

A first proof

Here is a short theorem and a complete proof. Read it slowly and notice that every step is justified.

Theorem. The sum of two even integers is even.

Proof. Let \(m\) and \(n\) be even integers. By the definition of even, there are integers \(j\) and \(k\) with \(m = 2j\) and \(n = 2k\). Then \(m + n = 2j + 2k = 2(j + k)\). Since \(j + k\) is an integer, \(m + n\) has the form \(2 \cdot (\text{an integer})\), so \(m + n\) is even. \(\blacksquare\)

Several features of this proof are typical. It begins by naming the objects ('Let \(m\) and \(n\) be even integers'), so that the reader knows what we are talking about and that \(m\) and \(n\) are arbitrary, not particular numbers like 4 and 10. It uses different letters, \(j\) and \(k\), for the two unknown integers; using \(k\) for both would wrongly force \(m = n\). It ends by matching the definition of the conclusion exactly. And it marks the end with a symbol, here \(\blacksquare\); some books write QED, from the Latin quod erat demonstrandum, 'which was to be shown'.

Compare this with a non-proof: '4 + 6 = 10, 2 + 8 = 10, 12 + 20 = 32, all even, so the sum of two even numbers is even.' Each line is true, but the argument only covers three cases out of infinitely many. The proof above covers all of them at once, because \(j\) and \(k\) stand for any integers.

The shape of a proof

Most theorems have the form 'if \(P\), then \(Q\)', where \(P\) is the hypothesis and \(Q\) the conclusion. Even 'the sum of two even integers is even' secretly has this form: if \(m\) and \(n\) are even integers, then \(m + n\) is even. A direct proof assumes \(P\) and reasons forward to \(Q\). A good way to find one is to work from both ends: write down what \(P\) gives you (unpack the definitions), write down what \(Q\) requires (unpack those definitions too), and look for a bridge between them.

For example, to prove 'if \(n\) is odd then \(n^2\) is odd', the hypothesis gives \(n = 2k + 1\), and the conclusion requires \(n^2 = 2(\text{something}) + 1\). Squaring gives \(n^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1\), and the bridge is complete. Scratch work like this is how proofs are found; the written proof then presents the bridge in order from hypothesis to conclusion.

How to read a proof

Reading a proof is an active skill. Keep a pencil handy and check every line. Ask: what is being assumed here, and where did it come from? Which definition or earlier result justifies this step? Could I explain this step to someone else? When a proof says 'clearly' or 'it follows that', fill in the missing step yourself. A useful test is to try the argument on a specific example: take \(m = 6\), \(n = 14\) in the first proof, so \(j = 3\) and \(k = 7\), and check that \(m + n = 2(3 + 7)\). The example does not prove anything, but it makes the general argument concrete.

It also helps to ask where each hypothesis was used. If a proof never uses one of the hypotheses, either the hypothesis is unnecessary (and the theorem is stronger than stated) or the proof has a mistake. In the divisibility example both hypotheses were used, once each.

How to write a proof

Proofs are written in sentences, with mathematical symbols used inside sentences, not instead of them. A string of equations with no words is hard to follow and often hides a gap. The following conventions are standard and you should adopt them now.

• State what you are going to prove, and say which method you are using if it is not a direct proof ('We argue by contradiction', 'We use induction on \(n\)').

• Introduce every variable before you use it: 'Let \(n\) be an odd integer', 'there is an integer \(k\) such that'.

• Justify each step by a definition, a hypothesis, an earlier result or a piece of algebra.

• Use 'we' and the present tense: 'we have', 'we show', 'then'.

• Write in a natural order from what you know to what you want; leave your scratch work out of the final version.

• Mark the end of the proof.

A proof is written for a reader, and the right level of detail depends on who that reader is. In this course, imagine a classmate who knows the definitions but has not seen the problem. Every step should be one that classmate could check without help.

Checking a conjecture with a computer

Computers cannot prove a statement about all integers, but they are excellent at two things that come before a proof: finding counterexamples and building confidence. The code below tests Euler's expression \(n^2 + n + 41\) and the claim 'the sum of two odd squares is never a perfect square' for small values. The first search finds the failure at \(n = 40\). The second finds nothing, which suggests a theorem worth proving; you will prove it in lesson 6.

def is_prime(m):
    if m < 2:
        return False
    d = 2
    while d * d <= m:
        if m % d == 0:
            return False
        d += 1
    return True

# Euler's prime-producing expression
first_fail = next(n for n in range(1000) if not is_prime(n * n + n + 41))
print("n^2 + n + 41 is prime for n = 0 ..", first_fail - 1)
print("first failure at n =", first_fail, "value", first_fail**2 + first_fail + 41)

# is a sum of two odd squares ever a perfect square?
squares = {k * k for k in range(1, 3000)}
hits = [(a, b) for a in range(1, 400, 2) for b in range(a, 400, 2)
        if a * a + b * b in squares]
print("odd a, b < 400 with a^2 + b^2 a perfect square:", len(hits))

n^2 + n + 41 is prime for n = 0 .. 39
first failure at n = 40 value 1681
odd a, b < 400 with a^2 + b^2 a perfect square: 0

Treat output like this as a hint about what is true. When a search finds nothing, the next step is to ask why, and the answer to 'why' is usually the idea of the proof. Here the idea is to look at remainders on division by 4: an odd square always leaves remainder 1, so a sum of two odd squares leaves remainder 2, and no square leaves remainder 2.

A little history

The idea that mathematical claims should be proved from accepted starting points goes back at least to the Greek mathematicians. Euclid's Elements, written around 300 BCE, organized the geometry and number theory of its time as a chain of definitions, postulates and propositions, each proved from what came before. It was used as a textbook for more than two thousand years. In the nineteenth century mathematicians such as Augustin-Louis Cauchy and Karl Weierstrass rebuilt calculus on precise definitions after its earlier, more intuitive foundations led to paradoxes. Around 1900 David Hilbert promoted the axiomatic method across all of mathematics, and the language of sets introduced by Georg Cantor became the common framework in which definitions are written. That is the language you will learn in lessons 9 to 12.

Today proofs are also checked by computer. Proof assistants such as Lean and Coq can verify every step of a formal proof, and large projects have used them to confirm results like the four colour theorem and the Kepler conjecture on packing spheres. Formal proofs are written in a different style from the ones in this course, but they rest on the same logic.