Log24

Proof 101

From a course description:

“This module aims to introduce the student to rigorous university level mathematics….
    Syllabus: The idea of and need for mathematical statements and proofs…. proof by contradiction… proof by induction…. the infinite number of primes….”

In the December Notices of the American Mathematical Society, Brian (E. B.) Davies, a professor of mathematics at King’s College London, questions the consistency of Peano Arithmetic (PA), which has the following axioms:

From BookRags.com—

Axiom 1. 0 is a number.

Axiom 2. The successor of any number is a number.

Axiom 3. If a and b are numbers and if their successors are equal, then a and b are equal.

Axiom 4. 0 is not the successor of any number.

Axiom 5. If S is a set of numbers containing 0 and if the successor of any number in S is also in S, then S contains all the numbers.

It should be noted that the word “number” as used in the Peano axioms means “non-negative integer.”  The fifth axiom deserves special comment.  It is the first formal statement of what we now call the “induction axiom” or “the principle of mathematical induction.”

Peano’s fifth axiom particularly troubles Davies, who writes elsewhere:

I contend that our understanding of number should be placed in an historical context, and that the number system is a human invention.  Elementary arithmetic enables one to determine the number of primes less than twenty as certainly as anything we know.  On the other hand Peano arithmetic is a formal system, and its internal consistency is not provable, except within set-theoretic contexts which essentially already assume it, in which case their consistency is also not provable.  The proof that there exists an infinite number of primes does not depend upon counting, but upon the law of induction, which is an abstraction from our everyday experience…. 
… Geometry was a well developed mathematical discipline based upon explicit axioms over one and a half millennia before the law of induction was first formulated.  Even today many university students who have been taught the principle of induction prefer to avoid its use, because they do not feel that it is as natural or as certain as a purely algebraic or geometric proof, if they can find one.  The feelings of university students may not settle questions about what is truly fundamental, but they do give some insight into our native intuitions.

— E. B. Davies in
   “Counting in the real world,”
    March 2003 (word format),
    To appear in revised form in
    Brit. J. Phil. Sci. as
   “Some remarks on
    the foundations
    of quantum mechanics”

Exercise:

Discuss Davies’s claim that

The proof that there exists an infinite number of primes does not depend upon counting, but upon the law of induction.

Cite the following passage in your discussion.

It will be clear by now that, if we are to have any chance of making progress, I must produce examples of “real” mathematical theorems, theorems which every mathematician will admit to be first-rate. 

… I can hardly do better than go back to the Greeks.  I will state and prove two of the famous theorems of Greek mathematics.  They are “simple” theorems, simple both in idea and in execution, but there is no doubt at all about their being theorems of the highest class.  Each is as fresh and significant as when it was discovered– two thousand years have not written a wrinkle on either of them.  Finally, both the statements and the proofs can be mastered in an hour by any intelligent reader, however slender his mathematical equipment.

I. The first is Euclid’s proof of the existence of an infinity of prime numbers.

The prime numbers or primes are the numbers

   (A)   2, 3, 5, 7, 11, 13, 17, 19, 23, 29, … 

which cannot be resolved into smaller factors.  Thus 37 and 317 are prime.  The primes are the material out of which all numbers are built up by multiplication: thus

    666 = 2 ^. 3 ^. 3 ^. 37. 

Every number which is not prime itself is divisible by at least one prime (usually, of course, by several).   We have to prove that there are infinitely many primes, i.e. that the series (A) never comes to an end.

Let us suppose that it does, and that

   2, 3, 5, . . . , P
 
is the complete series (so that P is the largest prime); and let us, on this hypothesis, consider the number

   Q = (2 ^. 3 ^. 5 ^{. . . . .} P) + 1.

It is plain that Q is not divisible by any of

   2, 3, 5, …, P;

for it leaves the remainder 1 when divided by any one of these numbers.  But, if not itself prime, it is divisible by some prime, and therefore there is a prime (which may be Q itself) greater than any of them.   This contradicts our hypothesis, that there is no prime greater than P; and therefore this hypothesis is false.

The proof is by reductio ad absurdum, and reductio ad absurdum, which Euclid loved so much, is one of a mathematician’s finest weapons.  It is a far finer gambit than any chess gambit: a chess player may offer the sacrifice of a pawn or even a piece, but a mathematician offers the game.

— G. H. Hardy,
   A Mathematician’s Apology,
   quoted in the online guide for
   Clear and Simple as the Truth:
   Writing Classic Prose, by
   Francis-Noël Thomas
   and Mark Turner,
   Princeton University Press

In discussing Davies’s claim that the above proof is by induction, you may want to refer to Davies’s statement that

Geometry was a well developed mathematical discipline based upon explicit axioms over one and a half millennia before the law of induction was first formulated

and to Hardy’s statement that the above proof is due to Euclid.