Proof by Contradiction Tutorial

Overview

• Goal: Learn to prove statements by contradiction using four simple steps.
• Prerequisites:
  • Basic operations with numbers.
  • Manipulating and simplifying algebraic expressions.
  • Understanding different types of numbers (e.g., prime, composite, integers).

What is Proof by Contradiction?

• A technique to prove statements that are hard to prove directly.
• Example of a hard statement: "All numbers are positive."
  • Negation: "There exists a number that is negative."
  • Finding one negative number disproves the original statement.

Negation Statements

• A negation statement opposes the original statement.
• Example:
  • Original: "5 times 5 is equal to 25."
  • Negation: "5 times 5 is not equal to 25."
  • Since the negation is false, the original statement is proven true.

The Knack Method

1. N: Write the negation statement.
2. A: Assume the negation statement is true.
3. C: Perform calculations based on the assumption.
4. K: Find a contradiction based on calculations.

Forming Negation Statements

• The negation can often be more than the direct opposite.
• Use keywords to guide forming negations:
  • "All" → "There exists"
  • Example:
    • Original: "n is odd."
    • Negation: "n is not odd" (or "n is even").
• More examples:
  • Original: "The square root of 20 equals 5."
  • Negation: "The square root of 20 does not equal 5."
  • Original: "All tall guys get girls."
  • Negation: "There exists one tall guy that does not get girls."

Examples of Proof by Contradiction

Example 1: Proving if n^2 is even, then n is even.

1. Negation: "If n^2 is even, then there exists an n that is odd."
2. Assumption: Assume the negation is true.
3. Calculations:
   • If n is odd, then n = 2k + 1 (where k is an integer).
   • n^2 = (2k + 1)(2k + 1) = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1 (an odd number).
4. Contradiction: n^2 cannot be both odd and even.
   • Therefore, if n^2 is even, then n must be even.

Example 2: Proving the square root of 2 is irrational.

1. Negation: "The square root of 2 is rational."
2. Assumption: Assume the square root of 2 is a fraction a/b (in simplest form).
3. Calculations:
   • From the equation: (sqrt(2) = a/b) => 2 = a^2/b^2 => a^2 = 2b^2.
   • If a^2 is even, then a must be even (a = 2n).
   • Substitute back: 2b^2 = 4n^2 => b^2 = 2n^2 (means b is also even).
4. Contradiction: If both a and b are even, a/b is not in simplest form, contradicting the assumption.
   • Thus, the square root of 2 is irrational.

Conclusion

• Mastering negation statements is crucial for proof by contradiction.
• Practice forming negations with textbook examples.
• For further help, like this video, comment below, and subscribe for more tutorials.