What is a mathematical proof?
By Keith Devlin @profkeithdevlin
With the start of the new academic year, a new cadre of mathematics students will make their first encounter with university level math. For many, it will be traumatic. Not least, for those intending to be math majors. Typically, such students did well at high school, and arrive at university or college fully expecting to do just as well. And many (maybe most) will do so. But for most of them, the transition from school to university will not be a smooth one. (It certainly was not for me when I made it.)
The emphasis on definitions and concepts, together with the degree of formality and rigor, make university-level mathematics (for majors) very different from high school. If that shift in emphasis does not occur in the first year (and for many American undergraduates it won’t), it definitely will at the start of the second year.
High among the notions that cause not a few students to wonder if perhaps math is not the subject for them, is mathematical proof. Though it is the bedrock of professional pure mathematics, the concept of proof is barely touched on outside university mathematics departments. The closest a typical high school graduate may have come to this notion is what mathematicians call “plausibility arguments.”
So what exactly is a mathematical proof? Way back when I was a university mathematics undergraduate, I could give you a precise answer: A proof of a statement S is a finite sequence of assertions S(1), S(2), … S(n) such that S(n) = S and each S(i) is either an axiom or else follows from one or more of the preceding statements S(1), …, S(i-1) by a direct application of a valid rule of inference.
But that was then. After a lifetime in professional mathematics, during which I have read a lot of proofs, created some of my own, assisted others in creating theirs, and reviewed a fair number for research journals, the one thing I am sure of is that the definition of proof you will find in a book on mathematical logic or see on the board in a college level introductory pure mathematics class doesn’t come close to the reality.
For sure, I have never in my life seen a proof that truly fits the standard definition. Nor has anyone else.
The usual maneuver by which mathematicians leverage that formal notion to capture the arguments they, and all their colleagues, regard as proofs is to say a proof is a finite sequence of assertions that could be filled into become one of those formal structures.
It’s not a bad approach if the goal is to give someone a general idea of what a proof is. The trouble is, no one has ever carried out that filling-in process. It’s purely hypothetical. How then can anyone know that the purported proof in front of them really is a proof?
I wrote about this dilemma in my MAA “Devlin’s Angle” column way back in 1996, in an article titled Moment of Truth.
I picked up the theme again in 2003 with my Devlin’s Angle piece When is a Proof?
These days I have a very pragmatic perspective on what a proof is, based on the way people use them in the day-to-day world of mathematics:
Proofs are stories that convince suitably qualified others that a certain statement is true.
If I present you with a proof, and you have the appropriate background knowledge and ability, you can – usually with some time and effort – as a result of reading my story, become convinced that what I claim is true.
But if you take that as your working definition of proof, you have to acknowledge it is fundamentally about communication, not truth. In particular, whether an argument classifies as a proof depends as much on the intended reader as on its creator.
Of course, in order to function in that way, the “story” has to be pretty heavily constrained.
Moreover, the creators and the consumers of those stories have to be familiar with the genre. That part takes time to acquire.
On the other hand, once a person becomes familiar with both the genre and the particular mathematical focus, reading and understanding those stories becomes natural and fluent.
The system works – as any professional mathematician will affirm. It’s how mathematics advances.
To an outsider, however, the whole thing is usually incomprehensible.
Today, many proofs stretch over several pages, not infrequently hundreds of pages. A key feature that allows such proofs to function effectively in the mathematical community is that many steps are left out.
In some cases this is because the step has already been established, either by the same author in a previous piece of work, or by someone else. In such cases, the author simply refers the reader to that source.
In other cases, the author judges that the intended reader should be capable of supplying the missing steps on the fly. The author may provide a hint to help the reader provide the missing steps, but not always.
There is, then, a huge element of audience design in constructing effective proofs. A proof designed for an undergraduate mathematics class is in general very different from one constructed to present at a research seminar.
To the beginner, trying to make the transition from high school mathematics to university level, coming to terms with real proofs is not only difficult, it can be traumatic, with a once comforting illusion of crisp, clean certainty rapidly giving way to a panicked feeling of sinking into shifting quicksand.
At this point, it can be of some comfort to learn that Euclid screwed up big-time when he penned his famous geometry proofs in Elements. Yes, those iconic proofs may seem logically sound, and indeed for two thousand years were held up as models of logically sound reasoning. But as David Hilbert observed in the late Nineteenth Century, Euclid’s arguments are riddled with logical holes.
To give just one example, he often tells you to construct a point by intersecting an arc of a circle with a straight line. But how do you know there is an intersection? Sure, when you draw the arc and the line on a sheet of paper, the arc may cross over the line. But do they actually intersect? That is, do they have an actual (dimensionless) point in common?
That is not only not obvious, it takes a lot of work to answer. (The answer is, it depends on the underlying number system. But it requires some deep machinery not developed until the Nineteenth Century.)
Of course, high school teachers rarely, if ever, tell their students that the geometry proofs they are presented as models are at best sketches of how proofs can be constructed. As a result, those students typically enter university with a totally false impression of what a proof is. In particular, they believe proofs are fundamentally and exclusively about truth, and that they are either right or wrong.
In reality, proofs are about truth, but not fundamentally, and definitely not exclusively. The key property of a proof is not that it is logically correct (it almost certainly is not, but more pertinent, how could you ever be sure it is?), rather that it is expressed in a manner that enables a suitably qualified reader to fill in any holes they notice, to check any steps they have any doubt about, and to correct any errors they find (as they surely will if they dig deep enough).
It’s very much like software engineering, where the most important thing about a program is not that it is bug free (it almost certainly is not), rather that – in addition to working – it is structured and annotated so that someone else can come along later and either fix bugs or else modify the code to do something else.
Before I sign off, I should note that, if you are an undergraduate student reading this post, you should be prepared to provide the “definition” I gave at the start of this discussion, if asked to do so on an exam. It is a sound notion, and an important one. Formulating it was an important milestone in the development of mathematics. But in terms of mathematical praxis, its role is that of a shining lantern on a hill — something we should constantly aspire to when it comes to determining truth in mathematics. But it is as well to be aware that, in the human world of mathematical activity, actual proofs that people produce and read are merely approximations to that ideal.
NOTE: This month’s post is a lightly edited version of a post in my blog profkeithdevlin, which I published on November 24, 2014. Some things bear repeating.