December 2, 2005

• 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.

  • 5:55 am
  • Leave a comment