How to shoot down your proofs

Question

What are general guidelines for checking your proofs? I believe this is important for graduate students like me. I already know what we need to do to prove something, but you always have to check everything before you send it out. Even to your own advisor.

I've developed myself some strategies by trial and error, and got a lot of advice from my advisor. But this is always a very tedious work. Normally, when you finish with something, you just want to go on to the next problem, but you still have to stick to the current problem until everything is perfect. Here I present an example of my own list of tricks:

1. Fill in the details. A lot of mistakes are in places were you write "it is clear that...", "without loss of generality...", etc.
2. Try some numbers. Try extreme cases, like "what happens when I set $n=1$ or $n=1000$".
3. Keep a clean notebook. Write every day on it, and compare it with your rough notes. I try to write also in latex, I've found many mistakes this way.

What are the general strategies that you apply for checking your proofs?

The objective of this question is to make it a community-wiki.

Answer 1

Software engineers have a notion they call "code smells". These are symptoms in the code that may indicate a deeper problem. Software engineers collect mental lists of smells to be aware of (i.e. excessively long methods or too many parameters). It does not necessarily mean there is a problem, but simply indicate that the writer might want to double check.

I propose that we ought to also consider "proof smells". This will not give you an algorithm for checking your proofs but it gives a language and a metaphor for recognizing possible problems in proofs. Some examples of proofs smells:

1. The adverbs "Clearly", "Obviously", etc.
2. Reference to the proof of a previous result instead of a reference to the result itself.
3. Flippant use of a result with many technical preconditions.

There are also more subtle smells. For example, if a proof uses the binomial theorem to expand an expression and then later uses the binomial theorem to return to a closed form, then maybe there is a direct manipulation on the closed form that gives the same result.

My suggestion is to collect a (mental or written) list of such smells and check for them as you read through your work. The nice side effect of this approach is that it will also make you a better reader.

Note: My hope in this answer was to give intuitive side to the rigorous answer supplied by Lamport's How to Write a Proof referenced in M. Alaggan's answer.

Answer 2

There is a very good paper by Leslie Lamport (How to write a proof). It is actually a proposal by him on a style of writing detailed proofs in such a way that:

(1) Allows detecting errors in a straight-forward way

(2) Makes it clear which assumptions and theorems used in which parts, which makes it pretty easy to see what happens if you want to (for instance) use weaker assumptions

There is also some community experience and inspiring commentary on this technique on MO which shows positive experience in general (and some other resources as well).

Update: there is a new version How to write a 21st century proof.

Answer 3

Dick Lipton has a nice article titled 'How to Prove a proof is a proof'

Answer 4

I seem to remember reading a popular account long ago of how physicists deal with an analogous problem. Who knows how accurate the following version of it is; corrections are welcome. But I found the underlying strategy quite remarkable.

They explained how they came to believe in black holes. Black holes were initially purely mathematical constructs, like other strange objects in physics like wormholes. Their strategy was striking: they would mathematically throw other objects at the object to be tested. Wormholes failed their tests because they found that the wormhole would collapse even in the presence of a normal physical object, maybe an asteroid. But black holes passed this test: the black hole would survive having an asteroid thrown at it. So they tried throwing a star at it. Same result. Finally, they threw another black hole at the black hole and it survived. As a result of this, they grew confident enough in the existence of black holes to actually start looking for them in the real universe.

So the relevance and application of the strategy above is to start throwing things at your proof. Does it survive sanity checks? If you remove a necessary assumption, does it collapse as it should? Does it collapse as it should when it's applied to cases outside its scope? Does it withstand reasonable generalizations and specializations? Have a look at the list of heuristics in Polya's How to Solve It. Try mutating your proof with these heuristics and see if it stands and falls as it should.

Answer 5

I think one of the safest approaches is to come up with multiple independent proofs. Then you can be confident that your main result is correct, even if you have a mistake in some details of a proof.

Answer 6

One technique I've found useful is to think about what other results would the proof strategy be able to prove. If I'm easily able to adapt the proof strategy to prove a big open problem or even a problem that isn't open but which has a much too complicated solution compared to the complexity of the proof strategy, then that's a big reason to doubt the proof.

Answer 7

I always re-check my proofs with a proof-checker like COQ or ISABELLE. If you can prove your proof in any of these programming language, you can be sure your proof is correct. As simple as a lambda-term ;).