Does ‘Proof by Computer’ Count?

What is a proof? In the sciences, we formulate a theory and test whether it holds by gathering evidence via experiments. We regard our results as proof. In mathematics, however, the concept of ‘proof’ works a little differently, and increasingly computers are being used in this process. But how does this work, and does it really count as proof? Cas Burton explores…

In mathematics, a proof is a sequence of statements. We start with some simple axioms (such as ‘0 does not equal 1’) and can only add a particular statement to our sequence if it can logically be deduced from the previous statements.

Intermediate Value Theorem:

If you have a continuous function f(x) that is negative at x=0 and positive at x=1, then f(x)=0 at some point between 0 and 1.

Banach-Tarski Paradox:

A solid ball can be chopped up into as few as five pieces and reconstructed into two identical copies of the original ball. The pieces are only moved and rotated.

Suppose you have a map and are trying to colour it in such that any two regions which share a border are different colours. What is the minimum number of colours you need to use?

The Four Colour Theorem (FCT) states that you only need four colours. This does require some conditions on your map. We assume that:

  • Corners where three or more regions meet do not count as borders;
  • Every region is precisely one area – we couldn’t use a map of North America because the mainland US is separated from Alaska by Canada;
  • There are no lakes or oceans.

(If we wanted to use a map of North America, or one that included oceans, we wouldn’t be able to guarantee that the US & Alaska, or bodies of water, were the same colour.)

This theorem was proposed in the 1800s. Over the years, there were many proofs – and disproofs – that ultimately failed. For something that seems to make sense, it was a long time before it was proved in 1976 by Appel and Haken.

Appel and Haken proved that if you needed five colours to colour a map, then a smaller map that needed five colours also existed. So if any map needed five colours, then so would the smallest map possible – but this clearly does not need five, as it’s just one region.

Proving this fact required checking a staggering number of cases – initially over 1,800. Checking each case by hand was inconceivable. In the end, the FCT was proved with help from a computer. It took over a thousand hours for the computer to check every case.

The question is, is this enough to constitute a proof? This was the first major theorem to be proved using a substantial amount of computer assistance. In using a computer to check each case, they had to trust every single program that it used. They had to trust the code, the software – everything. A mistake could easily be lost in so much data. Even now, the shortest proofs still require checking over 600 cases.

The Four Colour Theorem is widely considered proved now. Some still doubt it. Do you?

Cas Burton is a former Mathematics student at St John’s College, Oxford

From the Teacher: Proof by Induction

Following on from Cas Burton’s article on mathematical proofs, in this section Maths teacher Nathusha Srithas introduces us to a set of challenges on ‘Proof by Induction’.

For a statement to be true, a proof must be provided.

  1. John is Mary’s son, therefore, Mary is John’s mother. Prove this statement true. What assumptions are being made?
  2. Prove that the sum of two consecutive numbers is odd.

Proof by Induction

Proof by induction is like a domino effect. A proof by induction is proving the left-hand side is equal to the right-hand side where each step must be justified with:

  1. The statement is true for the base case n=1
  2. If this 1) is true, then an assumption can be made that the statement is true for n=k
  3. Using the assumption from 2), prove that the statement is true for n=k+1
  4. Conclusion

For example: “Prove by induction 5n – 1 is always divisible by 4.”

1- Check for base case n=1
51 – 1 = 4 (this is divisible by 4)
True for n=1

2- As it is true for n=1, assume the statement is true for n=k
So: 5k – 1 is divisible by 4
Hence we can write 5k – 1 = 4m
Leading to 5k = 4m + 1

3- Therefore, when n=k+1
5k+1 -1 + 5(5k) – 1
Where 5k = 4m + 1
Substitute 5(4m+1)-1
=20m+5-1
=20m+4
=4(5m+1)

4- Final conclusions: As 5m+1 is an integer, we have 5k+1 – 1 is divisible by 4, so the statement is true for n=k+1. Since it is true for n=k+1, through induction the statement “5n – 1 is always divisible by 4” is true for n = N.

* N = natural numbers (positive integers)

Nathusha Srithas is a teacher of Mathematics at Villiers High School in Ealing

Challenge

Prove by induction that the sum of the first n positive numbers is equal to half of product of n and n+1.

HINT: Form an equation to make this statement true. Example the sum of the first 10 numbers can be demonstrated as 1+2+3+…+10.

Extensions

Prove by induction the sum of n cube numbers is equal to a quarter of the product of square of n and square of (n+1).

Can proof by introduction be used in the real world? Provide an example.

TO SUBMIT YOUR WORK, PLEASE CLICK HERE!

Further Resources

http://podcasts.ox.ac.uk/narrative-and-proof-two-sides-same-equation

If you enjoyed this article…

You might want to explore our courses in:

Mathematics and Joint Schools | St John’s College, Oxford