## Archive for November 24th, 2014

### What is a proof, really?

What is a mathematical proof? Way back when I was a college freshman, 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 I was so much older then, I’m younger than that now.

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 in to 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.

Ridding high school graduates of the “proofs are about logical correctness” misconception is generally a difficult (for both instructor and student) and painful (for the student) process. Just what it entails has been a focus of a study I have been making in my MOOC Introduction to Mathematical Thinking, currently being offered for the fifth time. I describe my most recent observations in a new post on my other blog, MOOCtalk.org,

where this account continues…