Coconote
AI notes
AI voice & video notes
Export note
Try for free
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.
📄
Full transcript