Difference between revisions of "Proofs"

From Computer Science
Jump to: navigation, search
(Organization)
(Other thoughts)
 
(4 intermediate revisions by the same user not shown)
Line 4: Line 4:
 
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.
 
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.
 
# State your claim, what you are going to prove.
 
# State your claim, what you are going to prove.
# 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).
+
# 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).
# Indicate how basic plan for the proof - whether it will be be contradiction, induction, etc.
+
# 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.
# Proceed to write the steps of the proof - this is the main part of the proof.
+
# Proceed to write the formal steps of the proof - this is the main part of the proof.
 
# 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.
 
# 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=
 
=Style=
 
You should use good writing style.  A few general requirements...
 
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 (so you always have to state your claim as the first thing).
+
* 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.
 
* 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 [https://courses.csail.mit.edu/6.042/spring18/mcs.pdf 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.

Latest revision as of 14:00, 13 September 2022

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.