## Thursday, December 28, 2006

### Learning Proof Techniques

Something else that has been on my mind for many years now, that I think has impeded my mathematical development: the whole business of how to actually go about proving something. I feel that, and I am probably not alone in this, I was never really taught strategies for how to develop a proof. Sure, I was taught about some very general techniques: proof by contraction, induction, etc. But no one ever really sat me down said, how are we going to develop this proof. Obviously I was shown the proofs to all sorts of famous theorems and other homework problems. But they just showed us the proof after it was already concocted. But rarely the messy business of how we might have come up with proof. Never the false starts, the random walks, and sheer examples of genius that are required pull the whole thing together. Because, to me, the presentation of the completed proof in a nice linear story-telling manner is a complete distortion of the actual reality that went into creating it.

So, does any one know of any resources that actually address this issue? Am I alone in thinking that this is a real pedagogical problem in mathematics? Or am I just too aware of my own limitations in this area?

SJMiller said...

Following Aaron's example, I'll identify myself first. I'm a friend / colleague / mentor of Leo's (I was a graduate student at Princeton when he was an undergradute), and currently am a professor of mathematics at Brown.

One common failing (in many classes and textbooks) is that the instructor or author forgets that what is second nature to them is so partly because of years of experience in the subject. For certain types of problems, it is 'trivial' that this is the right way to approach them, primarily because we have seen so many similar problems over the years and have thus learned that this is the way to go. But it takes a long time to reach the point where these are trivial. (Anyone interested in a great set of problems and proofs should look at Proofs from THE BOOK; once you see them many of these arguments are trivial, but finding them in the first place...).

When I teach, be it statistics or abstract algebra (I draw my examples from number theory and cryptography), I've made the conscious decision to cover less material and emphasize more how to attack problems. This is as useful a skill as specific knowledge, though harder to acquire. I always ask students in class how we should proceed on a problem; I don't care if they suggest the correct starting point (in fact, it's often better if they don't, as we can then see why a 'natural' approach fails).

There's also an enormous difference b/w research problems (where we might know what is true but don't have a proof) and textbook problems (if section 3.2 is on the chain rule, then almost surely the chain rule will be useful for problems from this section). It's very easy to come to a problem with pre-conceived notions, and this is often good! But keep a skeptical mind. Try some small cases or examples; while these are not proofs (unless you find a counter-example), often by looking at these you can get a good sense of what's going on.

Also, the more widely read you are, the more 'similarities' you'll be able to see. Of course, this all comes back to experience. And, in fact, sometimes experience is bad! There have been numerous occasions where I've solved problems by invoking high powered results, and some of my students (who don't know those results) are able to find far more elementary solutions.

Aryeh said...

Glad to have Aaron and Steve on board.

Aaron, you bring up a very important -- indeed, central -- question in math education. I've much, much to say on the subject; the rambling restraint is on.

Proving theorems is an art. We even have theorems telling us that the theorem-proving process can't be automated! So how does one go about proving a theorem? Better yet, how does one even look for reasonable conjectures to prove?

I share your frustration with published/taught proofs. When I present proofs (whether my own or others'), I accompany every step with commentary: "Straightforward to verify, basic algebra/calculus. Verify by induction. Alert! Clever trick here! Observe this decomposition... Note that A is actually a type of B..."

In my experience, difficult proofs have "Aha!" moments. You've tried
the obvious approaches and failed (naturally -- if the obvious had
worked, it wouldn't be a difficult proof). After days/weeks/months/years of "false starts, the random walks" and
flashes of inspiration one finds the right approach. In my experience proving things and understanding others' proofs, the transitions between these "Aha!" moments are fairly straightforward. Once you
understand those key observations, the stuff inbetween can usually be
filled in by any moderately competent mathematician.

This reality is almost always totally concealed in published papers. I wish I could draw the reader's attention to such "aha!" points in my proofs, but the standard practice is to present the results in a linear, monotonous form.

[Angry old man Dijkstra
vehemently opposed such flashes of insight; he insisted that a proof
be "forced" -- that is, have a structure where every step ineluctably follows from the previous one. He called counter-intuitive, ad-hoc contrivances "rabbits" (which the mathemagician pulls out of his hat)
and disparaged them mercilessly. I am not sure that rabbits can
actually be banished from really deep proofs, but that's a topic for
another post.]

The bottom line is that proving theorems is about experience and
mathematical maturity. As you get to know your field, you develop
intuitions for how these esoteric objects behave. I am not sure it's
really possible to educate students specifically how to prove
theorems. You give them a bunch of techniques (in analysis:
approximate by dense, well-behaved functions, in linear algebra:
diagonalize). Much of math is about finding normal forms (Cantor
normal form for ordinals, Jordan normal form for matrices,
Lebesgue-Radon-Nikodym decomposition of measures, Krohn-Rhodes decomposition of automata); any new normal form is, almost ipso facto, a deep result. A normal form gives you much insight into the structure
of an otherwise chaotic set of objects, planting the seeds for new
intuitions and connections.

The issue of how to formulate interesting/promising conjectures will have to wait for another post.

Aryeh said...

A brief comment on Steve's post. Among the most grievous failings I've observed as a student is a lack of rigor on the professor's part. When mathematicians talk among themselves, they often use vague and imprecise language, because "we know what we mean". Well, the students often don't -- so it's really important to painstakingly dot all the i's (or leave the dot off if it's a iota). Especially since "natural" intuitions are all too often misleading; when grading, I often write on student papers, "not only is this not obvious, but it's also not true".

I can't overstate the importance of finding the "hard" special cases when struggling with a proof. This too is an art...

SJMiller said...

About where to learn proof techniques: several books have recently come out. One is: Theorems, Corollaries, Lemmas, and Methods of Proof (Richard Rossi), another is How to prove it (Polya); there are others (but don't have access to all my files).

Too often one can follow a proof line by line and not see the 'big picture' or the 'key idea' underlying it. Sometimes it is extremely well hidden. Someone just showed me a popular book on the Riemann Zeta Function, and it proved the functional equation 'without' using unique factorization! It took me about 10 minutes to see where it had 'secretly' assumed it. The real question is: did the author realize he was making an assumption but was willing to do so for the audience, or did the author not realize what he did? I think it is a real disservice to hide these steps. They should be emphasized (like Leo's Ahas).

After reading a proof it's nice to step back and try and think about why the proof worked, what was the key step / idea. A proof should probably be read at least 3 times (a first cursory scan to get the main ideas, then a careful reading trying to understand all the details but not stopping too long if something doesn't click, and then slowly getting all the details).

Of course, none of this answers the question of how to prove something new. We can build our techniques, but finding out which pieces to use together, as well as when and how.... What works for me and some colleagues is to be familiar with a rich landscape which will facilitate seeing connections, and being well versed in various techniques.

Aryeh said...

I can't resist pointing out that this whole discussion is making one huge assumption: it is perfectly obvious and unambiguous what constitutes a mathematical proof. That was certainly not the case throughout the centuries, and is not even fully resolved now (did Perelman really prove Poincare?). For an excellent and riveting account of this aspect of the philosophy of math, see Proofs and Refutations by Imre Lakatos.

[Though the situation is certainly much better now than before. I'd say about 99.99% of the time the mathematical community is in perfect agreement as to the status of an assertion (true/false/open). Some proofs are very difficult and take a long time for humans to verify -- fortunately, automatic proof
verification is much easier than coming up with the proofs in the first place!]

Aaron Greenhouse said...

Lots to reply to here, and I don't have the time to do it right now, except to say the following. I think I would be much better at proving things if my teachers had spent more time explaining to us "proofs" that were wrong. I think there is much to be learned there, because obviously we didn't set out to create a bad proof.

Anonymous said...

Thurston has written on this topic, expressing similar sentiments of not actually knowing how to go about proving something despite having gone through many proofs.

You can find his article at http://arxiv.org/PS_cache/math/pdf/9404/9404236.pdf

I hope that long line works; if not, the arxiv number is 9404236.

Aryeh said...

Thanks for the fascinating pointer, Ken. It's on my list of things to digest, as soon as the pressure lightens up a bit...