Posts Tagged 'mathematical proofs'

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…

Advertisements

How mountain biking can provide the key to the Eureka moment

Because this blogpost covers both mountain biking and proving theorems, it is being simultaneously published by the Mathematical Association of America in my Devlin’s Angle series. 

In my post last month, I described my efforts to ride a particularly difficult stretch of a local mountain bike trail in the hills just west of Palo Alto. As promised, I will now draw a number of conclusions for solving difficult mathematical problems.

Most of them will be familiar to anyone who has read George Polya’s classic book How to Solve It. But my main conclusion may come as a surprise unless you have watched movies such as Top Gun or Field of Dreams, or if you follow professional sports at the Olympic level.

Here goes, step-by-step, or rather pedal-stroke-by-pedal-stroke. (I am assuming you have recently read my last post.)

BIKE: Though bikers with extremely strong leg muscles can make the Alpine Road ByPass Trail ascent by brute force, I can’t. So my first step, spread over several rides, was to break the main problem – get up an insanely steep, root strewn, loose-dirt climb – into smaller, simpler problems, and solve those one at a time.

MATH: Breaking a large problem into a series of smaller ones is a technique all mathematicians learn early in their careers. Those subproblems may still be hard and require considerable effort and several attempts, but in many cases you find you can make progress on at least some of them. The trick is to make each subproblem sufficiently small that it requires just one idea or one technique to solve it.

In particular, when you break the overall problem down sufficiently, you usually find that each smaller subproblem resembles another problem you, or someone else, has already solved.

When you have managed to solve the subproblems, you are left with the task of assembling all those subproblem solutions into a single whole. This is frequently not easy, and in many cases turns out to be a much harder challenge in its own right than any of the subproblem solutions, perhaps requiring modification to the subproblems or to the method you used to solve them.

BIKE: Sometimes there are several different lines you can follow to overcome a particular obstacle, starting and ending at the same positions but requiring different combinations of skills, strengths, and agility. (See my description last month of how I managed to negotiate the steepest section and avoid being thrown off course – or off the bike – by that troublesome tree-root nipple.)

MATH: Each subproblem takes you from a particular starting point to a particular end-point, but there may be several different approaches to accomplish that subtask. In many cases, other mathematicians have solved similar problems and you can copy their approach.

BIKE: Sometimes, the approach you adopt to get you past one obstacle leaves you unable to negotiate the next, and you have to find a different way to handle the first one.

MATH: Ditto.

BIKE: Eventually, perhaps after many attempts, you figure out how to negotiate each individual segment of the climb. Getting to this stage is, I think, a bit harder in mountain biking than in math. With a math problem, you usually can work on each subproblem one at a time, in any order. In mountain biking, because of the need to maintain forward (i.e., upward) momentum, you have to build your overall solution up in a cumulative fashion – vertically!

But the distinction is not as great as might first appear. In both cases, the step from having solved each individual subproblem in isolation to finding a solution for the overall problem, is a mysterious one that perhaps cannot be appreciated by someone who has not experienced it. This is where things get interesting.

Having had the experience of solving difficult (for me) problems in both mathematics and mountain biking, I see considerable similarities between the two. In both cases, the subconscious mind plays a major role – which is, I presume, why they seem mysterious. This is where this two-part blogpost is heading.

BIKE: I ended my previous post by promising to

“look at the role of the subconscious in being able to put together a series of mastered steps in order to solve a big problem. For a very curious thing happened after I took the photos to illustrate this post. I walked back down to collect my bike from … where I’d left it, and rode up to continue my ride.

It took me four attempts to complete that initial climb!

And therein lies one of the biggest secrets of being able to solve a difficult math problem.”

BOTH: How does the human mind make a breakthrough? How are we able to do something that we have not only never done before, but failed many times in attempts to do so? And why does the breakthrough always seem to occur when we are not consciously trying to solve the problem?

The first thing to note is that we never experience the process of making that breakthrough. Rather, what we experience, i.e., what we are conscious of, is having just made the breakthrough!

The sensation we have is a combined one of both elation and surprise. Followed almost immediately by a feeling that it wasn’t so difficult after all!

What are we to make of this strange process?

Clearly, I cannot provide a definitive, concrete answer to that question. No one can. It’s a mystery. But it is possible to make a number of relevant observations, together with some reasonable, informed speculations. (What follows is a continuation of sorts of the thread I developed in my 2000 book The Math Gene.)

The first observation is that the human brain is a result of millions of years of survival-driven, natural selection. That made it supremely efficient at (rapidly) solving problems that threaten survival. Most of that survival activity is handled by a small, walnut-shaped area of the brain called the amygdala, working in close conjunction with the body’s nervous system and motor control system.

In contrast to the speed at which our amydala operates, the much more recently developed neo-cortex that supports our conscious thought, our speech, and our “rational reasoning,” functions at what is comparatively glacial speed, following well developed channels of mental activity – channels that can be built up by repetitive training.

Because we have conscious access to our neo-cortical thought processes, we tend to regard them as “logical,” often dismissing the actions of the amygdala as providing (“mere,” “animal-like”) “instinctive reactions.” But that misses the point that, because that “instinctive reaction organ” has evolved to ensure its owner’s survival in a highly complex and ever changing environment, it does in fact operate in an extremely logical fashion, honed by generations of natural selection pressure to be in synch with its owner’s environment.

Which leads me to this.

Do you want to identify that part of the brain that makes major scientific (and mountain biking) breakthroughs?

I nominate the amygdala ­– the “reptilean brain” as it is sometimes called to reflect its evolutionary origin.

I should acknowledge that I am not the first person to make this suggestion. Well, for mathematical breakthroughs, maybe I am. But in sports and the creative arts, it has long been recognized that the key to truly great performance is to essentially shut down the neo-cortex and let the subconscious activities of the amygdala take over.

Taking this as a working hypothesis for mathematical (or mountain biking) problem solving, we can readily see why those moments of great breakthrough come only after a long period of preparation, where we keep working away – in conscious fashion – at trying to solve the problem or perform the action, seemingly without making any progress.

We can see too why, when the breakthrough (or the great performance) comes, it does so instantly and surprisingly, when we are not actively trying to achieve the goal, leaving our conscious selves as mere after-the-fact observers of the outcome.

For what that long period of struggle does is build a cognitive environment in which our reptilean brain – living inside and being connected to all of that deliberate, conscious activity the whole time – can make the key connections required to put everything together. In other words, investing all of that time and effort in that initial struggle raises the internal, cognitive stakes to a level where the amygdala can do its stuff.

Okay, I’ve been playing fast and loose with the metaphors and the  anthropomorphization here. We’re really talking about biological systems, simply operating the way natural selection equipped them. But my goal is not to put together a scientific analysis, rather to try to figure out how to improve our ability to solve novel problems. My primary aim is not to be “right” (though knowledge and insight are always nice to have), but to be able to improve performance.

Let’s return to that tricky stretch of the ByPass section on the Alpine Road trail. What am I consciously focusing on when I make a successful ascent?

BIKE: If you have read my earlier account, you will know that the difficult section comes in three parts. What I do is this. As I approach each segment, I consciously think about, and fix my eyes on, the end-point of that segment – where I will be after I have negotiated the difficulties on the way. And I keep my eyes and attention focused on that goal-point until I reach it. For the whole of the maneuver, I have no conscious awareness of the actual ground I am cycling over, or of my bike. It’s total focus on where I want to end up, and nothing else.

So who – or what – is controlling the bike? The mathematical control problem involved in getting a person-on-a-bike up a steep, irregular, dirt trail is far greater than that required to auto-fly a jet fighter. The calculations and the speed with which they would have to be performed are orders of magnitude beyond the capability of the relatively slow neuronal firings in the neocortex. There is only one organ we know of that could perform this task. And that’s the amygdala, working in conjunction with the nervous system and the body’s motor control mechanism in a super-fast constant feedback loop. All the neo-cortex and its conscious thought has to do is avoid getting in the way!

These days, in the case of Alpine Road, now I have “solved” the problem, the only things my conscious neo-cortex has to do on each occasion are switching my focus from the goal of one segment to the goal of the next. If anything interferes with my attention at one of those key transition moments, my climb is over – and I stop or fall.

What used to be the hard parts are now “done for me” by unconscious  circuits in my brain.

MATH: In my case at least, what I just wrote about mountain biking accords perfectly with my experiences in making (personal) mathematical problem-solving breakthroughs.

It is by stepping back from trying to solve the problem by putting together everything I know and have learned in my attempts, and instead simply focusing on the problem itself – what it is I am trying to show – that I suddenly find that I have the solution.

It’s not that I arrive at the solution when I am not thinking about the problem. Some mathematicians have expressed their breakthrough moments that way, but I strongly suspect that is not totally true. When a mathematician has been trying to solve a problem for some months or years, that problem is always with them. It becomes part of their existence. There is not a single waking moment when that problem is not “on their mind.”

What they mean, I believe, and what I am sure is the case for me, is that the breakthrough comes when the problem is not the focus of our thoughts. We really are thinking about something else, often some mundane detail of life, or enjoying a marvelous view. (Google “Stephen Smale beaches of Rio” for a famous example.)

This thesis does, of course, explain why the process of walking up the ByPass Trail and taking photographs of all the tricky points made it impossible for me to complete the climb. True, I did succeed at the fourth attempt. But I am sure that was not because the first three were “practice.” Heavens, I’d long ago mastered the maneuvers required. It was because it took three failed attempts before I managed to erase the effects of focusing on the details to capture those images.

The same is true, I suggest, for solving a difficult mathematical problem. All of those techniques Polya describes in his book, some of which I list above, are essential to prepare the way for solving the problem. But the solution will come only when you forget about all those details, and just focus on the prize.

This may seem a wild suggestion, but in some respects it may not be entirely new. There is much in common between what I described above and the highly successful teaching method of R.L. Moore. For sure you have to do a fair amount of translation from his language to mine, but Moore used to demand that his students did not clutter their minds by learning stuff, rather took each problem as it came and then try to solve it by pure reasoning, not giving up until they found the solution.

In terms of training future mathematicians, what these considerations imply, of course, is that there is mileage to be had from adopting some of the techniques used by coaches and instructors to produce great performances in sports, in the arts, in the military, and in chess.

Sweating the small stuff will make you good. But if you want to be great, you have to go beyond that – you have to forget the small stuff and keep your eye on the prize.

And if you are successful, be sure to give full credit for that Fields Medal or that AMS Prize where it is rightly due: dedicate it to your amygdala. It will deserve it.


I'm Dr. Keith Devlin, a mathematician at Stanford University, an author, the Math Guy on NPR's Weekend Edition, and an avid cyclist. (Yes, that's me cycling on the Marin Headland.)

RSS MOOCtalk

Twitter Updates

  • RT @jayrosen_nyu: I feel like I spent all of 2017 on exactly this. Kasparov puts it well in his thread. Our civic emergency is real— and es… 5 hours ago
  • RT @dangillmor: They Think You're Stupid, Part 45,008: Corker is shocked, shocked to discover that he'd personally benefit after switching… 5 hours ago

New book 2012

New book 2011

New e-book 2011

New Book 2011

December 2017
M T W T F S S
« Jan    
 123
45678910
11121314151617
18192021222324
25262728293031

%d bloggers like this: