What is Proof?
There is no doubt about centrality of proof in mathematics. But what is a proof?
We may learn the etymology of the word from The Words of Mathematics by S. Schwartzman:
proof (noun), prove (verb): the Latin adjective probus meant "upright, honest," from the Indo-European root per- "forward, through," with many other meanings. The derived verb probare meant "to try, to test, to judge." One meaning of the verb then came to include the successful result of testing something, so to prove meant "to test and find valid." Similarly, if you approve of something, you test it and find it acceptable. In a deductive system like mathematics, a proof tests a hypothesis only in the sense of validating it once and for all. In early 19th century American textbooks, prove was used in the etymological sense of "check, verify"; for example, multiplication was "proved" by casting out nines.
In a deductive system the word proof has acquired a more definitive meaning. For example, according to The Harper Collins Dictionary of Mathematics:
proof n. a sequence of statements, each of which is either validly derived from those preceding it or is an axiom or assumption, and the final member of which, the conclusion, is the statement of which the truth is thereby established.
Similarly, The Penguin Dictionary of Mathematics stipulates
proof a chain of reasoning using rules of inference, ultimately based on a set of axioms, that lead to a conclusion.
Well, as a great French mathematician put it, When we give a definition, it is to use it. The site is replete with hundreds of solved problems and proven theorems. There are also special collections of simple proofs, and (subjectively) charming proofs, there is a collection of attractive facts with unremarkable proofs and innocently wrongful proofs. There are even proofs without words. The site also explains the notion of syllogism and offers a good sample of Lewis Carroll's Soriteses.
There are many misconceptions about proof. The common educational terminology "paragraph proof" or "two-column proof" is somewhat misleading and often leads to a question "How to teach (learn) proofs?" This question usually indicates a confusion of two distinct activities: finding a proof and communicating a proof. The former is an art, the latter a skill. An existing proof can be written in prose, interspersed with formulas or not, or in two columns. Using one way or another is a matter of taste and convention. Learning to do that is a manageable task for those who mastered the art of finding proofs. Thus the real question to ask is "How to teach (learn) proving?"
My answer to that question is "Start from the simplest". To prove a statement is to establish its validity (or truth) in a convincing way, by an argument. To disprove a statement is to reveal its falseness, perhaps by example, or by proving its negation. Very often all it takes to disprove a statement is to find a counterexample, i.e. an example that satisfies the conditions of the statement, the premises, but not its conclusion. For this reason, disproving something may be easier to start with.
The examples may look silly by stating an obvious falsehood, but they may help remove a cloak of mystery from proof.
Statement: all circles are equal. This is false because two circles, one of radius 1 cm, the other of radius 1 km, are obviously different. Simple as it was, we just proved a theorem: Not all circles are equal. (Eventually we'll prove a theorem used several times at the site that claims that all circles are similar.)
Statement: for any two integers a and b, if
Proving is usually a multistep process. You may not see it through right away. But, as John Mason put it, "... being stuck is an honorable state and is an essential part of improving thinking."
Sometimes one can get stuck right at the beginning, wondering where to start. At this point it pays to believe (better yet know but this comes with experience) that proving, as other kinds of problem solving, is a manageable craft. To sustain such a belief it is very important to adopt a strategy for setting off on a proof. This is like preparing for a hike. The best strategy is to prepare a list of items that will be useful or outright necessary on a trip, see for example [Zen and the Art of Motorcycle Maintenance, Chapter 4]. As you pack the items, you check them up on the list. At every point in time you know exactly what is already in and what is not yet. A great convenience.
I wrote at least a thousand words a day every day from the age of twelve on (p. 15). ... Read poetry every day of your life. Poetry is good because it flexes muscles you don't use very often (p. 36). ... Quantity gives experience. From experience alone can quality come. (p. 123) ... A sense of inferiority, then, in a person, quite often means true inferiority in a craft through simple lack of experience. (p. 127) ...
And on generating ideas he wrote (p. 17):
... along through those years I began to make lists of titles, to put down long lines of nouns. These lists were the provocations, finally, that caused my better stuff to surface. ... The lists ran something like this:
THE LAKE. THE NIGHT. THE CRICKETS. THE RAVINE. THE ATTIC. THE BASEMENT. THE TRAPDOOR. THE BABY. THE CROWD. THE NIGHT TRAIN. THE FOG HORN. THE SCYTHE. THE CARNIVAL. THE CAROUSEL. THE DWARF. THE MIRROR MAZE. THE SKELETON.
I was beginning to see a pattern in the list ...
In the theorem proving and problem solving it's a good strategy to have an (action) list. Here is a problem - what do you do? First of all, make sure you understand the problem [Polya, pp. 6-7, Zeitz, p. 29]. Check yourself with a few questions:
- What is the unknown?
- What are the data?
- What is implicit in the data?
- What is the condition?
- Have I seen a similar problem?
To help with the questions, draw a picture. Ask yourself whether there are any hidden assumption, either in the problem or in your view of the problem. There are indeed strategies and tactics in problem solving in general and in the theorem proving in particular. Polya's strategy is to proceed along four steps
- Understanding the problem
- Devising a plan
- Carrying out the plan
- Looking back
On the first step, ask the routine questions. On the second, depending on the take from the first stage, think of a method that could be used in solving the problem. This will usually come from a list of the methods at your disposal (a partial list from [Klamkin]):
(For more on this see the page on problem solving strategies and tactics.)
The last part of carrying out the plan is where you decide on how to present your proof or solution. The last step -- Looking back -- is educationally and pedagogically the most important of the art of proving and problem solving. This is when one learns the most.
But learn you must, and there is no escaping it: whining does not help. One has to start and stick with it. The great Dutch artist M. C. Escher wrote [Roberts, p. 216] in a reference to H. M. S. Coxeter's Introduction into Geometry:
... abracadabra high abstractions ... Of course, I don't understand one syllable, except for some funny and profound observations at the beginning of each chapter.
However, we learn [ibid.] that "When Escher's inventiveness stalled, he tackled the obstacle much as a mathematician does an intractable problem -- with obstinacy. Mathematicians pose questions that nag and pester, they keep chipping away at a problem, until truth, a solution, presents itself (or the enterprise crumbles and proves impossible.)"
- E. J. Borowski & J. M. Borwein, The Harper Collins Dictionary of Mathematics, Harper Perennial, 1991
- R. Bradbury, Zen in the Art of Writing: Essays on Creativity, Carpa Press, 1993
- H. S. M. Coxeter, Introduction to Geometry, John Wiley & Sons, 1961
- J. Daintith, R. D. Nelson (eds), The Penguin Dictionary of Mathematics, Penguin Books, 1989
- M. Klamkin, Mathematical Creativity in Problem Solving, pp. 73-95 in In Eve's Circles, MAA, 1994
- J. Mason, Thinking Mathematically, Addison-Wesley, 1985
- H. Poincaré, Science and Method, Dover Publications, 2003
- R. M. Pirsig, Zen and the Art of Motorcycle Maintenance, Harper (Modern Classics), 2005
- G. Polya, How To Solve It, Princeton University Press, 2nd ed, 1957
- S. Roberts, King of Infinite Space, Walker & Company, 2006
- D. Ruelle, The Mathematician's Brain, Princeton University Press, 2007
- S. Schwartzman, The Words of Mathematics, MAA, 1994
- P. Zeitz, The Art and Craft of Problem Solving, John Wiley & Sons, 1999