Lecture Notes: Proof by Contradiction

Overview

Proof by Contrapositive:
- Prove the contrapositive to establish the implication.
- Example: To prove ( P \rightarrow Q ), prove ( \neg Q \rightarrow \neg P ).
Proof by Contradiction:
- Prove a statement ( P ) by showing that ( \neg P ) leads to a contradiction.
- If ( \neg P ) implies false, then ( P ) must be true.

Statement: There are infinitely many prime numbers.
Assumption: Assume there are finitely many primes.
Process:
- List primes as ( P_1, P_2, \ldots, P_r ).
- Consider the number ( n = P_1 \times P_2 \times \ldots \times P_r + 1 ).
- ( n ) is not divisible by any of the listed primes ( P_i ), leading to a contradiction.
Conclusion: Assumption is false; there are infinitely many primes.

Statement: ( \sqrt{2} ) is irrational.
Assumption: Assume ( \sqrt{2} = \frac{a}{b} ) for integers ( a ) and ( b ) with no common factors.
Process:
- Square both sides: ( 2 = \frac{a^2}{b^2} ) implies ( 2b^2 = a^2 ).
- ( a^2 ) is even, so ( a ) is even; express as ( a = 2c ).
- Substitute back: ( 2b^2 = 4c^2 ) implies ( b^2 = 2c^2 ), so ( b ) is even.
- Contradiction: Both ( a ) and ( b ) are even, contradicting no common factors.
Conclusion: Assumption is false; ( \sqrt{2} ) is irrational.

Statement: ( \log_2 3 ) is irrational.
Assumption: Assume ( \log_2 3 = \frac{a}{b} ) for integers ( a ) and ( b ).
Process:
- ( 2^{a/b} = 3 ) implies ( a/b ) is positive and greater than 1.
- Raise to power ( b ): ( 2^a = 3^b ).
- Contradiction: Left side is even, right side is odd.
Conclusion: Assumption is false; ( \log_2 3 ) is irrational.

Contradictions arise when assumed negations of statements lead to logically impossible scenarios.
Further practice opportunities are available in tutorials.