Proof traits

• explicit/specific (non-vague)
• logically sound, including complete
• lacking irrelevant statements
• understandable to the reader
• self-contained (may assume basic things; anything else needs explicit reference to previous work or must be written out in the proof)

Proof kinds

• Direct proof: Assume hypothesis and march to conclusion.
• Contradiction: If proving a single clause, assume its negation and prove something that contradicts laws of mathematics. If proving A->B, assume not B and (implicitly or explicitly) A, and prove something that contradicts one of those two assumptions or general laws of mathematics.
• Contraposition: Arguably a special case of contradiction; used only for proving implications, A->B. Assume not B and prove not A.
• Induction: Theorem asserts something about an infinite collection, such as all natural numbers. Prove it for the lowest value (starting point) and then show that if you know it for n you can prove it for n+1. Conclude it holds for all values.

Proof tips

• Bi-implication is often easiest to prove as two separate implications, possibly using different methods.
• Existence: Either show the statement holds for a specific value or kind of value (e.g. all even numbers), or draw a contradiction from the assumption that it holds for no value.
• Universal: Leave the value as a variable and use only properties common to all possible instances of the variable.
• “For all x there exists y” (AE): Universally-quantified value must be represented as a variable, existentially-quantified value may (often must) be a function of the universal one.
• “There exists x such that for all y” (EA): Universally-quantified value must still be a variable. Existentially-quantified value can be specified, but must not be a function of the universal one because the same value (not just the same function) has to work for all possible values of the variable.
• Disjunction: “A or B” is often proved as “not A -> B” or “not B -> A”, whichever is more straightforward.
• Cases: Sometimes your universally-quantified values fall into a few neat categories (odd/even, positive/negative/zero) and it is easier to use different proofs for each category.
• If it’s not coming together, two things to check: Can you work backwards? Are there any definitions you haven’t fully unpacked?

Proof warnings

• Existence of an item satisfying the given criteria may be shown by presenting an example (constructive proofs) but need not be (nonconstructive proofs). For example, the Intermediate Value Theorem says if f is continuous and f(a) ≠ f(b), for any r between f(a) and f(b) there is c between a and b such that f(c) = r. Its proof gives no clue as to where c might be found, not even in terms of a, b, and r.
• If you are trying to prove something holds of all items in a certain group you may assume only traits that hold of every item in the group. For example, if you are proving something about all rational numbers you may use the fact that they may each be written as p/q where p, q are integers, q is nonzero, and gcd(p,q)=1. Be careful not to assume rational numbers are nonintegers, integers are positive, and so forth.
• If you are asked to prove an implication, it is likely it is not actually an equivalence, and if you “prove” an equivalence it will be incorrect. This trap catches more students than you might expect.