How I do Proofs

I was looking through some old papers, and decided to put online some advice that I gave many years ago about how I tackle mathematical proofs. The advice is at How I Do Proofs. This is only lightly edited from the original that I handed out to a course I was teaching in the late 90s.

The course is the one I described at Teaching Linear Algebra. I never got any feedback on my request for improvements, but judging from how well that class did at proofs I believe that the advice was helpful. As one student I asked put it, "Doing proofs is like filling out a shopping list." That is how it should be in a first course where you are learning how to do proofs.

The class where I introduced this advice was fun. I started by handing out printouts of the advice. I then went through the flowchart at a high level. And then I put up a routine theorem from the text, which was the next thing I was supposed to do in the course. And I said, "OK, now that you've all learned how to prove things, you're going to prove this."

You should have seen the shock on their faces! Some started complaining. So I said, "No, seriously. You will all prove this. Just wait and see. It will work."

Then I began. I asked the one person to say what the first step was. A second person to do it. A third person what the next step was. A fourth to do it. And so on. And every time they did something that could be written down, I wrote down exactly what they said. Before long they had proven a result that none of them thought they could prove!

The third of the homework for that night which was on that day's material (if this statement puzzles you, go back to Teaching Linear Algebra and read about the homework strategy in that course) was very heavy on doing proofs. And I can tell that they referred to the handout by one fact. The next day the grader came to me, very puzzled, and asked me to explain this strange piece of reasoning that everyone had used. It was the contrapositive, which is an interesting alternative to proof by contradiction. One of the problems could be solved either with contradiction or the contrapositive, and they all chose the contrapositive because I'd listed it before contradiction.

I considered this a very good thing. One of the major problems that students have with proof by contradiction is that it works too often. Proofs that require a bit of routine algebra or computation can always be rewritten as proof by contradiction. The rewritten proof is correct, but it is unnecessarily confusing and it is better not to have used contradiction. However because contradiction seems to always work, it becomes a sledgehammer that the student always uses. Without noticing that it is sometimes the wrong tool.

The contrapositive doesn't have this drawback. It can solve the same problems as those that "really" needed proof by contradiction. But it doesn't lend itself to solving problems that never needed proof by contradiction. And so students who have been trained to try the contrapositive do not tend to make their simpler proofs over-complicated.

In fact when I drew up the advice I nearly left out contradiction. But it is so widely used that I figured I had to include it. However I tried to subtly discourage its use. And to the best of my knowledge I succeeded, I'm not aware that any students in my class ever used it in any of their proofs.