Proof Techniques

Direct Proof

In a direct proof, we assume the hypothesis is true and use definitions, axioms, and previously proved theorems to show the conclusion is true.

To prove: p → q
1. Assume p is true
2. Derive q from p using logical steps
3. Therefore p → q

Proof by Contrapositive

Instead of proving p → q directly, we prove its contrapositive ¬q → ¬p, which is logically equivalent.

To prove: p → q
1. Assume ¬q is true (the conclusion is false)
2. Derive ¬p from ¬q
3. Therefore ¬q → ¬p, which means p → q

Proof by Contradiction

Assume the negation of what you want to prove, then show this assumption leads to a contradiction.

To prove: p
1. Assume ¬p is true
2. Derive a contradiction (e.g., r ∧ ¬r)
3. Therefore ¬p must be false, so p is true

Example: √2 is irrational — proved by contradiction by assuming it is rational and finding a contradiction.

Mathematical Induction

Induction proves statements about natural numbers by verifying a base case and an inductive step.

To prove: P(n) for all n ≥ n₀
1. Base Case: Prove P(n₀) is true
2. Inductive Step: Assume P(k) is true for some k ≥ n₀
   Prove P(k+1) is true using the assumption
3. By induction, P(n) is true for all n ≥ n₀