Course contentsShow
← Mathematics
Lesson 2518 of 3,12150. Discrete Math — Logic and ProofFree lesson

Proofs Using Well-Ordering

Apply the well-ordering principle to prove statements about integers.

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

  1. Assume negation: Suppose the statement you want to prove is false
  2. Construct a set: Define S as the set of positive integers for which the statement fails
  3. Apply well-ordering: Since S is nonempty (by assumption), it has a smallest element, call it m
  4. 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.