MATH2020 (Lec 02) - Proof Techniques

Proof Techniques

Proof definitions

All term definitions:

• proposition: a statement that is either true or false
• axioms: propositions simply accepted as true
• predicates: propositions whose truth depends on the value of one or more variables
• Implications: proposition of the form “if P then Q” → “P implies Q”, with P is premise, Q is conclusion

Truth Table

Basic Proof Techniques (P is premise, Q is conclusion)

Direct Proof

• To prove P implies Q
• Step 1: assume P, or “If P then…”
• Step 2: show that Q logically follows

Indirect Proof

• Method 1 (Prove by contrapositive): Assume Q false → deduct that P is also false
• Method 2 (Prove by contradiction): Assume P is true and Q is false, reach an illogic

Proof by cases

• split into several cases satisfying the range, and prove with examples
• good when the range is small, or the quantity having to prove is small, can examined each element in the whole range

Non constructive proof of existence

• does not explicitly construct the example asked, but prove such example exists
• use logical reasoning, without providing specific example
• eg. game of chomp; proving “there exists irrational x and y such that $x^y$ is rational”