Rules of Proof

  • Every statement must be justified.
  • A justification can refer to prior lines of the proof, the hypothesis and/or previously proven statements from the book.
  • Cases are often required to complete a proof which has statements with an "or" in them. Each case should be labelled I, II etc and then the line numbering for each case should start with the same number. Remember, you may justify any statement with an earlier line in the proof (but those earlier lines cannot be from other cases).
  • You may never assume anything except when doing a proof by contradiction. When writing a proof by contradiction the first line is "Assume on the contrary" and then write the negation of the conclusion of what you are trying to prove.
  • A contradiction is reached when a statement contradicts any of the hypotheses, a prior line of the proof, or any known fact (e.g. 1>0).
  • A proof by contradiction is only complete when a contradiction has been reached in every case.
  • If you cannot find a justification and you are sure it is true, you may wish to write a seperate proof on the side to prove that justification and then apply it to your original situation. When you do this, it is called proving a lemma.
  • To prove a statement of the form, "For all x in some set there exists y in some other set such that...", think of x as given information and the fact that it is in a certain set as part of the hypothesis, then in your proof proceed to look for a y. You are not given y, you need to find it and it might be that you can think of a formula for y and then you must prove that this y has all the properties described after the "such that".
  • During a proof you may introduce new variables by saying "Let x be...". You can do this for example by choosing x from a set (this is called the Axiom of Choice) or by giveing a formula for the new variable x. You may not introduce a variable that is given in the hypothesis or already used earlier in the proof.
  • Be careful when writing a proof of a theorem you know well from precalc or calc that you do not use the theorem itself in the middle of the proof. That is called a circular proof and it is incorrect. Similarly when proving something is a limit or an inverse, feel free to use techniques from prior courses to figure out the idea or the "answer" but then you still must write a proof of what you are saying being careful to justify each step from statements in the book.
  • When writing a proof by induction, always remember to write "We will prove this by induction". Then write "when n=1"... and check that case. Then write: "Given: statement with n" and "Show: statement with (n+1) inserted where n was" and proceed to prove this with a two column proof. The usual approach is to try to rewrite one side of an equality in a format which looks like the given statement and then apply the given statement to simplify the equation. When you apply the given statement, you write "by the induction hypothesis" to justify this step.
  • When doing a proof by induction be very careful to make sure that everythign you say works for an arbitrary natural number. It cannot just work for all n bigger than 2. It must include n=1. See the "all horses are the same color" example on Induction notes.