Overview

Rules for writing a single proof

1. Proofs are of statements. The statement to be proven must be given fully at the beginning.
2. The word "Proof" must be the start of the line following the statement to be proven.
3. Each line of the proof must known to be true by one of the justifcations learned in the course.
4. Exceptions to the previous rule must be identified as exceptions in the writing. This is usually done with words such as "We will show ..." or "It will suffice to show ..." or something equivalent.
5. All variables used in the proof must be introduced. Usually the word "let" is used to introduce a variable.
6. No two variables introduced during a proof can be given the same symbol (letter). This rule is harder to get used to than you might think.

To prove "A implies B"

This is the same as proving "If A, then B."
First assume A is true. A valid reason is that it is the hypothesis.
Then work out a proof of B where during the proof you are allowed to use the assumed truth of A.

Logical contructs found in a hypothesis

1. AND: If an "and" is found in a hypothesis, you simply assume both items in the and.
2. If a "for all m, P(m) is true" appears in the hypothesis, then whenever an m appears in the proof, you are allowed to say next that P(m) must be true. Note that the statement "P(m) is true" will appear on that line without the words "for all m." This is why this rule is called "for all elimination."
3. If a "there exists m so that P(m) is true" appears in the hypothesis then you can introduce a symbol (which does not have to be the letter m, but usually it is) with the words: "Let m be such that P(m) is true." You are not allowed to place any other restrictions on m. This explains rule 6 in the rule list above. If you use the "there exists" twice (yes, it happens) then using the same letter in both places gives a restriction on the letters. It forces the assumption that the two introductions are equal. Note that the words "let m be such that P(m) is true" do not have the words "there exists" in them. This is why this rule is called "there exists elimination."

Logical contructs found in a conclusion

1. AND: You must do two proofs. First prove one of the statements and then prove the other.
2. For all: If "for all m, P(m) is true" appears in the conclusion, you must prove P(m) is true for an m that has no restrictions. This is done by saying "Let m be arbitrary" (or "Let m be an arbitrary integer" if the proof is about integers, say) and then proceed to prove P(m) is true. The fact that m could have any value makes the proof valid for all values of m. Thus you can conclude that "for all m, P(m) is true." Since "for all" does not appear in the proof, but appears in the conclusion is why this is called "for all introduction." Note that introducing restrictions on m during the proof invalidates this method. Thus saying "assume m is positive" in the middle of the proof does not allow you to conclude that you have proven P(m) for all m at the end.
3. There exists: If "there exists m so that P(m) is true" appears in the conclusion, you simply have to find an m that makes P(m) true. Thus if you succeed in getting a line in the proof that says that P(m) is true, then you can conclude that "there exists an m for which P(m) is true." Since "there exists" does not appear in the proof, but appears in the conclusion is why this is called "there exists introduction."

Negation

1. AND: "not (P and Q)" is the same as "(not P) or (not Q)." That is, "it is false that P and Q are both true if at least one of P or Q is false."
2. OR: "not (P or Q)" is the same as "(not P) and (not Q)." That is, "it is false that at least one of P or Q is true if both P or Q are false."
3. For all: "not (for m, P(m))" is the same as "there exists m so that not P(m)." That is, "it is false that P(m) holds for every m, if there is some m that makes P(m) false."
4. There exists: "not (there exists m so that P(m))" is the same as "for all m (not P9M))." That is, it is false that some m makes P(m) true, if every m makes P(m) false."