Proof by Contradiction

Return to List of Lectures

Previous Lecture

• Questions?
• Proof by Contradiction
  • Section 3.3
  • Complete the proof in preview activity 2 (for all real numbers x and y, if x ≠ y, x > 0, y > 0 then x/y + y/x > 2)
    • Assume false, i.e., x ≠ y, x > 0, y > 0, and x/y + y/x ≤ 2
    • x/y + y/x ≤ 2
    • x²/xy + y²/xy ≤ 2
    • x² + y² ≤ 2xy
    • x² + y² - 2xy ≤ 0
    • (x-y)² ≤ 0
    • (x-y)² < 0 { x ≠ y means x-y ≠ 0}
    • Contradiction!
  • Progress check 3.16 (for all integers n, if n ≡ 2 (mod 4) then n ≢ 3 (mod 6))
    • Assume some integer n where n ≡ 2 (mod 4) and n ≡ 3 (mod 6)
    • So 4 | (n-2) and 6 | (n-3)
    • n - 2 = 4q for some integer q
    • n - 3 = 6r for some integer r
    • n = 4q + 2 = 6r + 3
    • 4q = 6r + 1
    • 2q = 3r + 1/2
    • Integer = integer + 1/2
    • Contradiction!
    • Or…
      • 2(2q + 1) = 3(2r + 1)
      • Even × odd = odd × odd
      • Even = odd
      • Contradiction!
  • Proof that √2 is irrational
    • Think about it — this is probably the first time you can be certain irrational numbers exist at all
• Next
  • Proof in cases
  • Section 3.4

Next Lecture