STEP-BY-STEP LESSON · §4.8
Indirect Argument: Two Famous Theorems
Understand the structure of two classical contradiction proofs.
Before you begin
Direct Proof and Counterexample III: Rational Numbers
r is rational if r=a/b for integers a,b with b≠0. A finite or infinite decimal representation alone does not replace this condition.
r=a/b; a,b∈ℤ; b≠0
Direct Proof and Counterexample IV: Divisibility
For integers d,n with d≠0, d|n means n=dk for some integer k. The vertical bar is not a fraction.
d|n ↔ ∃k∈ℤ: n=dk
Indirect Argument: Contradiction and Contraposition
To prove S, temporarily assume ¬S and derive incompatible statements. The assumption ¬S is then rejected.
¬S ⇒ contradiction
To prove P→Q, prove equivalent ¬Q→¬P. Start from the negated conclusion and reach the negated hypothesis.
P→Q ≡ ¬Q→¬P
Symbols
- √2
- square root of two
- p
- prime number
Definitions and notation for this topic
Prime
An integer greater than 1 with exactly two positive divisors: 1 and itself.
The number 1 is not prime; 2 is the only even prime.
Separate glossary example
2 is prime.
Step by step
Step 1 / 6
Parity is the bridge in the irrationality proof
For integer a, if a were odd then a=2k+1 and a²=2(2k²+2k)+1 would be odd. Hence an even a² forces even a. This inference must be justified; it is not obtained by simply taking a square root of “even”.
a² even ⇒ a even
Contraposition supplies the parity lemma used twice in the proof of √2.
Worked example
Explain why the proposed complete prime list 2,3,5 cannot be complete.
- Form N=2·3·5+1=31. It is greater than 1 and therefore has a prime divisor.
- Dividing N by each listed prime leaves remainder 1, since the product 30 is divisible by each. None of 2,3,5 divides N.
- Consequently any prime divisor of N is outside the list. This is the contradiction to completeness; it does not rely on assuming N itself is prime.
Optional self-check
What do even a and b violate in the first proof?
Show answer
The assumption that a/b was already in lowest terms.