Recipe

Prove a claim using the well-ordering principle

Use when: you want to show a property holds for every natural number at or above n0, and assuming a counterexample would hand you a concrete smallest case to work with

Goal: a proof that no counterexample to the claim exists, built from well-ordering's guaranteed least element

Taught in The well-ordering principle

1. 1

   Suppose, for contradiction, that the set S of natural numbers failing the claim is nonempty.

   Why: this is the standard setup for a proof by contradiction; everything that follows works toward collapsing this one assumption.

2. 2

   Since S is a nonempty set of natural numbers, the well-ordering principle guarantees it has a least element. Call it m.

   Example

   Proving "every integer n\ge2 has a prime factorization": if some integers \ge2 had none, that set would have a least element m.

   Why: well-ordering turns "assume a counterexample" into "assume one specific, smallest counterexample," which is concrete enough to reason about directly.

3. 3

   Show that m's own properties force a smaller number that is also a counterexample, or force m itself to satisfy the claim after all.

   Example

   m is not prime, or it would trivially have a factorization, so m=ab with 2\le a,b<m. Since a and b are smaller than the least counterexample, both have factorizations, so m=ab does too.

   • the argument constructs an explicit smaller counterexample — that directly contradicts m being least.
   • the argument instead shows m itself must satisfy the claim — that directly contradicts m being a counterexample at all.

   Why: minimality is the only special fact available about m, so the whole proof has to spend it here to reach a contradiction.

4. 4

   Since assuming S nonempty leads to a contradiction, S must be empty, so the claim holds for every natural number in its stated range.

   Why: this closes the proof by contradiction, now powered by well-ordering's guaranteed least element instead of a direct argument.