Understanding Proof by Contradiction

Dec 1, 2024

Lecture: Proof by Contradiction

Overview

  • The lecture covers the concept of Proof by Contradiction.
  • Offers a comparison with Proof by Contrapositive.
  • Includes three examples to illustrate Proof by Contradiction.

Proof by Contrapositive vs. Proof by Contradiction

  • Proof by Contrapositive:
    • Involves proving an implication by proving its contrapositive: if not Q then not P.
    • Equivalence: Proving "if P then Q" is equivalent to proving "if not Q then not P".
  • Proof by Contradiction:
    • More general than contrapositive.
    • To prove a statement P, prove that "not P implies false".
    • If not P leads to a contradiction, then P must be true.

Examples

Example 1: Infinitely Many Prime Numbers

  • Theorem: There are infinitely many prime numbers.
  • Assumption: Assume finitely many primes exist.
  • List primes as P1, P2, ..., Pr.
  • Consider a number N = (P1 * P2 * ... * Pr) + 1.
  • Contradiction:
    • N is not divisible by any listed primes, but must be divisible by a prime.
    • Contradiction: N is both not divisible by any prime and divisible by a prime.
    • Conclusion: Assumption is false, so there are infinitely many primes.

Example 2: Square Root of 2 is Irrational

  • Theorem: The square root of 2 is irrational.
  • Assumption: Assume √2 is rational (√2 = A/B for integers A, B with no common factors).
  • Process:
    • Square both sides: 2 = A^2 / B^2, implies 2B^2 = A^2.
    • A must be even (since A^2 is even), let A = 2C.
    • Substitute back: 2B^2 = 4C^2, simplifies to B^2 = 2C^2.
    • B must also be even.
  • Contradiction:
    • Both A and B are even, contradicting the assumption of no common factors.
    • Conclusion: √2 is irrational.

Example 3: Log Base 2 of 3 is Irrational

  • Theorem: Log base 2 of 3 is irrational.
  • Assumption: Assume log₂3 is rational (log₂3 = A/B for integers A, B).
  • Process:
    • 2^(A/B) = 3.
    • A/B > 1 (since 3 > 2).
    • Raise both sides to power B: 2^A = 3^B.
  • Contradiction:
    • 2^A must be even, 3^B must be odd.
    • Conclusion: log base 2 of 3 is irrational.

Closing

  • The lecture ends with an encouragement to practice more in the tutorial sessions.

Key Takeaways

  • Proof by contradiction involves assuming the negation of what you want to prove and then showing this leads to a logical inconsistency.
  • Useful for proving non-existence or irrationality.