Summary of "Discrete Math - 1.7.3 Proof by Contradiction"

Summary of “Discrete Math - 1.7.3 Proof by Contradiction”

This video explains the method of proof by contradiction, a fundamental technique in discrete mathematics used to prove propositions by assuming the opposite and deriving a contradiction.

Main Ideas and Concepts

Proof by Contradiction Overview:
- Unlike direct proof (which assumes the proposition ( P ) is true), proof by contradiction assumes the negation of the proposition ((\neg P)) is true.
- The goal is to show this assumption leads to a logical contradiction.
- The contradiction implies that (\neg P) is false, so ( P ) must be true.
Two Types of Propositions:
1. Single Proposition ( P ):
  - Assume (\neg P) and derive a contradiction.
  - Example: Proving (\sqrt{2}) is irrational.
2. Implication ( P \implies Q ):
  - Assume ( P ) and (\neg Q) (i.e., (P) is true and (Q) is false).
  - Derive a contradiction to prove the implication.
  - This is related to the contrapositive proof: (\neg Q \implies \neg P).

Detailed Methodologies and Examples

1. Proof by Contradiction for a Single Proposition

Example: Prove (\sqrt{2}) is irrational.

Step 1: Assume the negation: (\sqrt{2}) is rational.
Step 2: By definition of rational numbers, (\sqrt{2} = \frac{a}{b}), where (a, b) are integers with no common factors and (b \neq 0).
Step 3: Square both sides: [ 2 = \frac{a^2}{b^2} \implies 2b^2 = a^2 ]
Step 4: From (a^2 = 2b^2), conclude (a^2) is even, so (a) must be even.
Step 5: Write (a = 2c) for some integer (c).
Step 6: Substitute back: [ 2b^2 = (2c)^2 = 4c^2 \implies b^2 = 2c^2 ]
Step 7: Similarly, (b^2) is even, so (b) is even.
Step 8: Since both (a) and (b) are even, they share a common factor of 2, contradicting the assumption that (a/b) was in simplest form.
Conclusion: The assumption that (\sqrt{2}) is rational leads to contradiction, so (\sqrt{2}) is irrational.

2. Proof by Contradiction for an Implication (P \implies Q)

Example: Prove that if (3n + 2) is even, then (n) is even, where (n) is an integer.

Step 1: Assume (P): (3n + 2) is even.
Step 2: Assume (\neg Q): (n) is odd.
Step 3: Since (3n + 2) is even, subtract 2 (even) from it: [ 3n = (3n + 2) - 2 ] So (3n) is even.
Step 4: Consider (3n - n = 2n).
Step 5: Since (n) is odd, (3n - n = 2n) should be odd (difference of even and odd), but (2n) is always even.
Step 6: This contradiction shows the assumption that (n) is odd is false.
Conclusion: If (3n + 2) is even, then (n) must be even.

Additional Notes

The video briefly mentions that the next topic will be proof by cases (proof by exhaustion).
The explanation emphasizes understanding definitions (e.g., rational numbers, even/odd integers) as critical tools in proofs by contradiction.

Speakers/Sources Featured

Main Speaker: The instructor/presenter of the video (unnamed).
No other speakers or external sources explicitly mentioned.

Summary of Key Points

Proof by contradiction assumes the negation of what you want to prove.
For a proposition (P), assume (\neg P) and find a contradiction.
For an implication (P \implies Q), assume (P) and (\neg Q) and find a contradiction.
Use definitions and algebraic manipulation to derive contradictions.
Example proofs:
- (\sqrt{2}) is irrational.
- If (3n + 2) is even, then (n) is even.
Upcoming topic: proof by cases.