Proofs

From Computer Science
Jump to: navigation, search

This page contains some general remarks on writing mathematical proofs.

Organization

When you write a proof, you are writing. Just as with other forms of writing, the proof needs to be organized. You should always have the following components.

  1. State your claim, what you are going to prove.
  2. Indicate that your proof is beginning (typically with a bold "Proof" as a heading or at the beginning of a paragraph or list of bullet points).
  3. Indicate the basic plan for the proof - whether it will be be contradiction, induction, etc. For longer proofs, it is common to give a "proof idea" as well before diving into the formal proof.
  4. Proceed to write the formal steps of the proof - this is the main part of the proof.
  5. When you have finished you should state that you have proved the claim. For example, if doing a proof by contradiction, when you have reached the contradiction, you state that you have reached a contradiction, which means your assumption must be false, and that the claim must be true.

Style

You should use good writing style. A few general requirements...

  • Assume that someone who is not in your class has been sent your work, and they are supposed to be able to follow along. You should not assume that they already know what you are trying to prove (one of the reasons you always should state your claim as the first thing).
  • You should write in complete sentences, in particular for the beginning and end of the proof. This is also part of making sure someone who is not in the class would be able to read your work, understand what you are claiming, and be able to validate that your proof is correct.

Other thoughts

A very good summary of advice is section 1.9 Good Proofs from Mathematics for Computer Science. Very good advice.

In general, do not state things that are not true. You should very carefully check each step of your proof to make sure each step works. If you have a mistake at some point, then the entire rest of the proof may not be valid.