Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
If the question appears subjective, please help me improve it. –  Marcos Villagra May 16 '11 at 1:56
    
how do I make this community-wiki? –  Marcos Villagra May 16 '11 at 2:24
1  
Hey, cool! I'm really interested in the answers to this question. Also, I can appreciate your #3. (When I think about it, I actually have piles of paper scattered everywhere when I'm intently working on a problem, which then get randomly relocated. Yuck.) I've run into an mistake before from this very issue and ended up wasting a good chunk of time. –  Daniel Apon May 16 '11 at 2:35
    
@Daniel: I had the same problem!! That's why after I finnish with a proof, I immediately write the latex version. Its good to know that I'm not the only messy guy that keeps everything everywhere :-) –  Marcos Villagra May 16 '11 at 2:45
1  
you flag it for moderator attention. –  Suresh Venkat May 16 '11 at 16:11

7 Answers 7

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.

share|improve this answer
3  
I say this all the time to my students, and they think I'm crazy. Of course I actually claim I can smell a bug, which might be part of the problem ;) –  Suresh Venkat May 16 '11 at 16:13
6  
@Suresh: This student thinks you're crazy for different reasons. ;-) –  John Moeller May 16 '11 at 20:16
3  
On the code smell note, things I always try to scrutinize in others' proofs include inequality chains. Often really basic errors have a habit of creeping in amongst the more difficult derivations. –  John Moeller May 16 '11 at 20:20

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).

share|improve this answer
5  
These proofs are very similar to what one would write in a PL research paper. The chain of logic is very explicit. After learning how to read and appreciate PL-style proofs, I've found it difficult to make sense of "normal" math proofs. Such proofs often require that the reader think in the same way the author does, and when you've gotten used to a different proof style, this is simply not the case (for me, at least!) –  Christopher Monsanto May 16 '11 at 5:33
1  
@Christopher Monsanto: PL stands for Programming Languages ? I would appreciate if you can mention such an example (one such paper) to check out :) –  M. Alaggan May 16 '11 at 9:34
5  
I always had the feeling that what Lamport suggest is not compatible with Paul Lockhart's "A Mathematician's Lament" (maa.org/devlin/LockhartsLament.pdf). –  Marcos Villagra May 16 '11 at 13:24

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

share|improve this answer

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.

share|improve this answer
    
Most of your answer focuses on checking proofs by verifying that they become false in situations where they should be false. That doesn't work because it doesn't check that the theorem was true where it was supposed to be true! For example, suppose that I've "proved" that every odd number is divisible by three. I check that my proof fails if I extend to even numbers too: it does, since four is not divisible by three. Hooray, my proof must be correct! –  David Richerby Feb 19 at 9:24

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.

share|improve this answer

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.

share|improve this answer
4  
I'd give this +10 if I could - particularly in complexity theory, flawed proof techniques can often be shown to prove really strong statements like $P \neq NP$, and then it's very easy to guess that your proof technique is wrong. Particularly if your proof technique relativizes! –  Joshua Grochow Feb 19 at 2:34

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 ;).

share|improve this answer
    
I've never used Coq, but I ought to try. In fact, I'm trying to prove some lower bounds with mathematica, but I haven't found the right way. Maybe I need some special packages or something. –  Marcos Villagra May 17 '11 at 0:17
1  
Maybe it a longshot, but if you want to prove some lower bounds with reals, you can check these libraries: coqtail.sourceforge.net/?home/en –  Gopi May 17 '11 at 13:57
    
Agreed, but any programming language works. Most often I do this in reverse. Formulate the problem domain in a programming language (usually Ruby), then use this as a template for my proof. –  Chad Brewbaker Feb 19 at 17:00

protected by Artem Kaznatcheev Feb 19 at 6:25

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.