Proofs Using Well-Ordering
What you'll learn: You'll learn how to harness the well-ordering principle to prove statements about integers, particularly existence results and statements involving minimality.
The Core Idea
The well-ordering principle states that every nonempty set of positive integers has a smallest element. This seemingly simple fact is surprisingly powerful for proofs.
While mathematical induction lets you climb a ladder of statements (if true for n, then true for n+1), well-ordering works differently: you often assume your statement is false, then use that assumption to construct a nonempty set of counterexamples. Well-ordering guarantees this set has a smallest counterexample—and you then show this leads to a contradiction, often by finding an even smaller counterexample.
The Well-Ordering Proof Strategy
- Assume negation: Suppose the statement you want to prove is false
- Construct a set: Define S as the set of positive integers for which the statement fails
- Apply well-ordering: Since S is nonempty (by assumption), it has a smallest element, call it m
- Derive a contradiction: Use properties of m being minimal to construct a smaller element in S, contradicting minimality
Example Pattern
To prove "Every integer n ≥ 2 can be factored into primes":
- Assume not; let S = {integers ≥ 2 that cannot be factored into primes}
- S has a smallest element m
- m is not prime (else it's its own prime factorization)
- So m = ab where 2 ≤ a, b < m
- Both a and b are smaller than m, so both have prime factorizations
- Therefore m = (primes from a)(primes from b) is a prime factorization
- Contradiction! S must be empty.
Key Takeaway: Well-ordering proofs find the smallest counterexample and show it can't actually be smallest, collapsing the assumption that counterexamples exist.