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.

Clarity and Certainty

“At the age of 12 I experienced a second wonder of a totally different nature: in a little book* dealing with Euclidean plane geometry, which came into my hands at the beginning of a schoolyear. Here were assertions, as for example the intersection of the three altitudes of a triangle in one point, which — though by no means evident — could nevertheless be proved with such certainty that any doubt appeared to be out of the question. This lucidity and certainty [Klarheit und Sicherheit] made an indescribable impression upon me….  For example I remember that an uncle told me the Pythagorean theorem before the holy geometry booklet* had come into my hands. After much effort I succeeded in ‘proving’ this theorem on the basis of the similarity of triangles … for anyone who experiences [these feelings] for the first time, it is marvellous enough that man is capable at all to reach such a degree of certainty and purity [Sicherheit und Reinheit] in pure thinking as the Greeks showed us for the first time to be possible in geometry.”

— from “Autobiographical Notes” in Albert Einstein: Philosopher-Scientist, edited by Paul Arthur Schilpp

“Although our intellect always longs for clarity and certainty, our nature often finds uncertainty fascinating.”

— Carl von Clausewitz at Quotes by Clausewitz

For clarity and certainty, consult All About Altitudes (and be sure to click the “pop it up” button).

For murkiness and uncertainty, consult The Fog of War.

Happy birthday, Albert.

* Einstein’s “holy geometry booklet” was, according to Banesh Hoffman, Lehrbuch der Geometrie zum Gebrauch an höheren Lehranstalten, by Eduard Heis (Catholic astronomer and textbook writer) and Thomas Joseph Eschweiler.

From The Unknowable (1999), by Gregory J. Chaitin, who has written extensively about his constant, which he calls Omega:

"What is Omega? It's just the diamond-hard distilled and crystallized essence of mathematical truth! It's what you get when you compress tremendously the coal of redundant mathematical truth…" 

Charles H. Bennett has written about Omega as a cabalistic number.

Here is another result with religious associations which, historically, has perhaps more claim to be called the "diamond-hard essence" of mathematical truth: The demonstration in Plato's Meno that a diamond inscribed in a square has half the area of the square (or that, vice-versa, the square has twice the area of the diamond).

From Ivars Peterson's discussion of Plato's diamond and the Pythagorean theorem:

"In his textbook The History of Mathematics, Roger Cooke of the University of Vermont describes how the Babylonians might have discovered the Pythagorean theorem more than 1,000 years before Pythagoras.

Basing his account on a passage in Plato's dialogue Meno, Cooke suggests that the discovery arose when someone, either for a practical purpose or perhaps just for fun, found it necessary to construct a square twice as large as a given square…."

From "Halving a Square," a presentation of Plato's diamond by Alexander Bogomolny, the moral of the story:

SOCRATES: And if the truth about reality is always in our soul, the soul must be immortal….

From "Renaissance Metaphysics and the History of Science," at The John Dee Society website:

Galileo on Plato's diamond:

"Cassirer, drawing attention to Galileo's frequent use of the Meno, particularly the incident of the slave's solving without instruction a problem in geometry by 'natural' reason stimulated by questioning, remarks, 'Galileo seems to accept all the consequences drawn by Plato from this fact…..'"

Roger Bacon on Plato's diamond:

"Fastening on the incident of the slave in the Meno, which he had found reproduced in Cicero, Bacon argued from it 'wherefore since this knowledge (of mathematics) is almost innate and as it were precedes discovery and learning or at least is less in need of them than other sciences, it will be first among sciences and will precede others disposing us towards them.'"

It is perhaps appropriate to close this entry, made on All Hallows' Eve, with a link to a page on Dr. John Dee himself.