The well-ordering principle

Theorem

The well-ordering principle

T-002Home MU-101Threads logic · structure

Statement

Let \( \mathbb{N} = \{0, 1, 2, \dots\} \) carry its usual order \( \le \). Well-ordering principle (WOP). Every non-empty subset \( S \subseteq \mathbb{N} \) has a least element: there exists \( m \in S \) such that \( m \le s \) for all \( s \in S \). Moreover, over the remaining Peano axioms together with the basic order facts of \( \mathbb{N} \) (namely: \( 0 \le n \) for all \( n \); every \( n \neq 0 \) is a successor; and there is no natural number \( k \) with \( n \lt k \lt n+1 \)), the well-ordering principle is equivalent to the principle of mathematical induction: if \( P(0) \) holds and \( P(n) \Rightarrow P(n+1) \) for every \( n \in \mathbb{N} \), then \( P(n) \) holds for all \( n \in \mathbb{N} \).

Why it matters

The well-ordering principle is the engine behind the two most powerful elementary proof techniques in number theory and combinatorics: the minimal counterexample argument ("consider the least criminal") and infinite descent. Whenever a statement about natural numbers might fail, WOP hands you a smallest failure, and the structure of \( \mathbb{N} \) usually lets you build a still-smaller failure — a contradiction. Existence proofs in arithmetic (prime factorisation, the division algorithm, greatest common divisors via the Euclidean algorithm) all rest on it.

Conceptually, the equivalence with induction reveals that induction is not an arbitrary axiom but a statement about the order structure of \( \mathbb{N} \): the naturals are the prototype of a well-ordered set, and the entire theory of ordinals and transfinite induction generalises exactly this property.

Hypotheses

Hypothesis.\( S \) is non-empty. The empty set \( \emptyset \subseteq \mathbb{N} \) has no least element — a least element must in particular be an element. Every existence claim about \( \min S \) silently requires \( S \neq \emptyset \).

Hypothesis.\( S \) is a subset of \( \mathbb{N} \), not of a larger ordered set. The set \( \mathbb{Z} \) itself is non-empty but has no least element (\( \dots, -2, -1, 0, \dots \) descends forever). Likewise \( \{ q \in \mathbb{Q} : q \gt 0 \} \) is non-empty and bounded below by \( 0 \), yet has no least element: if \( q \) belonged to it, so would \( q/2 \lt q \).

Hypothesis.The order on \( \mathbb{N} \) is the standard one, and the ambient axioms include the other Peano axioms. "Well-ordered" is a property of a set with an order, not of a bare set. \( \mathbb{N} \) re-ordered by "all evens before all odds" (\( 0, 2, 4, \dots, 1, 3, 5, \dots \)) is still well-ordered but is a different well-order (order type \( \omega + \omega \)); \( \mathbb{N} \) ordered by \( \ge \) is not well-ordered at all, since \( \mathbb{N} \) itself then has no least element. The equivalence with induction also uses the successor facts named in the Statement; without them (over a very weak base theory) the two principles can come apart, which is why we state the base theory explicitly.

Proof

We prove the two implications separately. Throughout, \( \le \) is the usual order and we freely use the three order facts named in the Statement, flagging each use.

Part I: Induction \( \Rightarrow \) well-ordering.

Let \( S \subseteq \mathbb{N} \) be non-empty, and suppose for contradiction that \( S \) has no least element.

Proof by contradiction: we will derive \( S = \emptyset \). A

\[ T := \{ n \in \mathbb{N} : \forall m \in \mathbb{N},\ m \le n \Rightarrow m \notin S \}. \]

Key idea: instead of inducting on "\( n \notin S \)" (whose inductive step fails), we induct on the cumulative predicate "no number up to \( n \) lies in \( S \)". This is the standard trick converting ordinary induction into strong induction. B

\( 0 \in T \): if \( 0 \in S \), then since \( 0 \le s \) for every \( s \in S \), the number \( 0 \) would be a least element of \( S \), contradicting Step 1. Hence \( 0 \notin S \); and the only \( m \) with \( m \le 0 \) is \( m = 0 \).

Uses the order fact \( \forall n,\ 0 \le n \), and antisymmetry of \( \le \) to get \( m \le 0 \Rightarrow m = 0 \). A

Suppose \( n \in T \); we show \( n + 1 \in T \). If \( n + 1 \in S \), take any \( s \in S \). By \( n \in T \) we have \( s \not\le n \), so \( n \lt s \) by totality of the order. By discreteness — there is no \( k \) with \( n \lt k \lt n+1 \) — we get \( n + 1 \le s \). Thus \( n+1 \) would be a least element of \( S \), contradicting Step 1. Hence \( n+1 \notin S \). Combined with \( n \in T \), every \( m \le n+1 \) satisfies \( m \notin S \) (either \( m \le n \), or \( m = n+1 \), again by discreteness). So \( n + 1 \in T \).

The inductive step. Legality: totality of \( \le \) on \( \mathbb{N} \) (a consequence of the Peano axioms, proved itself by induction — we cite it as the trichotomy lemma), and the discreteness lemma (\( m \le n+1 \Rightarrow m \le n \) or \( m = n+1 \)), also proved by induction from the Peano axioms. This is the step where the specific structure of \( \mathbb{N} \) enters; it is exactly what fails in \( \mathbb{Q} \). C

By induction applied to the predicate \( n \in T \): from Steps 3 and 4, \( T = \mathbb{N} \). Now take any \( s \in S \) (possible since \( S \neq \emptyset \)). Then \( s \in T \) and \( s \le s \), so \( s \notin S \) — contradiction. Hence the assumption of Step 1 is untenable, and \( S \) has a least element. \( \blacksquare \) (Part I)

Direct application of the induction principle to \( P(n) :\equiv (n \in T) \); reflexivity of \( \le \); the contradiction discharges Step 1. A

Part II: Well-ordering \( \Rightarrow \) induction.

Assume WOP. Let \( P \) be a predicate with \( P(0) \) and \( \forall n \, \big( P(n) \Rightarrow P(n+1) \big) \). Define the "counterexample set" \[ S := \{ n \in \mathbb{N} : \neg P(n) \}. \] Suppose for contradiction \( S \neq \emptyset \).

Set-up: the induction conclusion \( \forall n \, P(n) \) is exactly \( S = \emptyset \). (For predicates given by formulas this is comprehension over \( \mathbb{N} \); in second-order Peano arithmetic \( S \) is a genuine set.) A

By WOP, \( S \) has a least element \( m \). Since \( P(0) \) holds, \( 0 \notin S \), so \( m \neq 0 \).

Direct application of WOP to the non-empty set \( S \); the base case rules out \( m = 0 \). A

Since \( m \neq 0 \), there exists \( k \in \mathbb{N} \) with \( m = k + 1 \). Then \( k \lt m \), so by minimality of \( m \) we have \( k \notin S \), i.e. \( P(k) \) holds.

Uses the predecessor lemma: every non-zero natural number is a successor. This is a consequence of the other Peano axioms (provable by an easy induction on the statement "\( n = 0 \) or \( \exists k,\ n = k+1 \)"; note this particular induction is over the base theory, which is why it appears among our stated background facts rather than being circular). The inequality \( k \lt k + 1 \) is a basic order fact. C

The inductive hypothesis \( P(k) \Rightarrow P(k+1) \) now yields \( P(m) \), i.e. \( m \notin S \) — contradicting \( m \in S \). Hence \( S = \emptyset \), i.e. \( \forall n \in \mathbb{N},\ P(n) \). \( \blacksquare \)

The key reversal: minimality of the counterexample feeds the inductive step, which destroys the counterexample. This completes both directions, so induction and WOP are equivalent over the stated base theory. B

Result

\[ \emptyset \neq S \subseteq \mathbb{N} \;\Longrightarrow\; \exists\, m \in S \ \forall s \in S: \ m \le s, \qquad \text{and} \qquad \text{WOP} \iff \text{Induction}. \]

Reading. You can never descend forever in the natural numbers: any collection of naturals you can point to, however wild, contains a definite smallest member. And this fact carries exactly the same logical weight as proof by induction — each can be manufactured from the other.

Scope. Applies to every non-empty subset of \( \mathbb{N} \) with its standard order (and, by translation \( n \mapsto n - a \), to subsets of \( \mathbb{Z} \) bounded below). It fails for \( \mathbb{Z} \), \( \mathbb{Q}^{+} \), \( \mathbb{R}^{+} \), and for \( \mathbb{N} \) under non-standard orders. The equivalence with induction is relative to the remaining Peano axioms plus the elementary order facts of \( \mathbb{N} \).

Corollaries & converses

Strong induction. If \( \big( \forall m \lt n,\ P(m) \big) \Rightarrow P(n) \) for every \( n \), then \( \forall n\, P(n) \). Proof: the least element of \( \{ n : \neg P(n) \} \) would violate the hypothesis. Strong induction, ordinary induction, and WOP are pairwise equivalent over the base theory.
No infinite descent. There is no infinite strictly decreasing sequence \( n_0 \gt n_1 \gt n_2 \gt \cdots \) in \( \mathbb{N} \): the set \( \{ n_0, n_1, \dots \} \) would have a least element \( n_k \), yet \( n_{k+1} \lt n_k \). This is Fermat's method of infinite descent.
Greatest elements. Every non-empty subset of \( \mathbb{N} \) that is bounded above has a greatest element (apply WOP to the non-empty set of upper bounds; see Problem 5).
Converse direction within \( \mathbb{N} \): holds — that is the Part II implication above; the two principles are genuinely equivalent, not merely one-way.
Converse as a characterisation: "every non-empty subset has a least element" is precisely the definition of a well-order; \( (\mathbb{N}, \le) \) is the least infinite well-order (order type \( \omega \)). The naive converse "every ordered set is well-ordered" is false: \( (\mathbb{Z}, \le) \) and \( (\mathbb{R}_{\ge 0}, \le) \) are total orders that are not well-orders — e.g. \( (0,1) \subseteq \mathbb{R}_{\ge 0} \) is non-empty with no least element. (Zermelo's theorem says every set admits some well-order, but that requires the axiom of choice and the order it produces is unrelated to any given order.)

Fails without

Drop non-emptiness: \( S = \emptyset \) has no least element; any argument that "takes the least element of \( S \)" without first exhibiting one element of \( S \) is broken. (Classic trap: in a minimal-counterexample proof you must not conclude anything before checking the counterexample set could be non-empty in the first place — the contradiction is what proves it empty.)
Replace \( \mathbb{N} \) by \( \mathbb{Z} \): \( S = \mathbb{Z} \) (or \( S = \{ -n : n \in \mathbb{N} \} \)) is non-empty with no least element. Correspondingly, "induction" on \( \mathbb{Z} \) with base case \( P(0) \) and step \( P(n) \Rightarrow P(n+1) \) proves nothing about negative integers.
Replace \( \mathbb{N} \) by \( \mathbb{Q}^{+} \) or \( \mathbb{R}^{+} \): \( S = \{ x \in \mathbb{R} : x \gt 0 \} \) is non-empty and bounded below, yet has no least element (\( x/2 \lt x \) for every candidate \( x \)). Density destroys the discreteness used in Step 4; the infimum \( 0 \) exists but is not a member — least element and infimum are different concepts.
Change the order: \( \mathbb{N} \) with the reversed order \( \ge \) is not well-ordered: \( \mathbb{N} \) itself has no \( \ge \)-least (i.e. no largest) element. Well-ordering is a property of the pair (set, order).

Common errors

Confusing least element with infimum. \( \inf \{ 1/n : n \ge 1 \} = 0 \) in \( \mathbb{R} \), but the set has no least element. WOP asserts membership of the minimum, not mere existence of a lower bound.
Forgetting the non-emptiness check. Writing "let \( m \) be the least element of \( S \)" when \( S \) might be empty. In a minimal-counterexample proof this is fine inside the contradiction hypothesis, but students often invoke \( \min S \) in direct proofs without justifying \( S \neq \emptyset \).
Applying WOP to sets of rationals or reals. E.g. "let \( \varepsilon \) be the smallest positive real number" — no such number exists.
Circular equivalence proofs. Proving "induction \( \Rightarrow \) WOP" while silently using WOP (e.g. "take the least \( n \) not in \( T \)"), or using unrestricted induction inside the proof of "WOP \( \Rightarrow \) induction". The predecessor lemma in Step 8 must come from the base theory, not from the induction principle being derived.
Minimal counterexample with no descent. Announcing a least criminal \( m \) but then deriving a contradiction that never uses minimality — usually a disguised (and often incomplete) direct proof.
Off-by-one at the bottom. Taking the least element \( m \) and immediately writing \( m = k+1 \) without first ruling out \( m = 0 \) (or \( m = 1 \) if your \( \mathbb{N} \) starts at \( 1 \)).

Discussion

Historically the principle was used long before it was isolated as an axiom-level statement. Fermat's method of infinite descent (17th century) — deriving from any solution a strictly smaller one, hence a contradiction — is WOP in action; he used it to prove that \( x^4 + y^4 = z^4 \) has no positive integer solutions. Euclid's proof that every number greater than \( 1 \) has a prime divisor (Elements, Book VII) implicitly takes a least divisor. The modern axiomatic picture emerged with Dedekind (1888) and Peano (1889), who made induction a defining axiom of \( \mathbb{N} \); the equivalence with well-ordering then became a theorem rather than folklore.

The right general frame is order theory: a well-order is a total order in which every non-empty subset has a least element, and the theorem says \( (\mathbb{N}, \le) \) is one. Well-orders are exactly the orders that support transfinite induction and transfinite recursion, and their isomorphism types are the ordinals. From this viewpoint \( \mathbb{N} \) is the ordinal \( \omega \), and structural induction on trees, terms, and formulas — ubiquitous in logic and computer science — is induction over other well-founded orders. The useful weakening is well-foundedness (no infinite descending chains, equivalently every non-empty subset has a minimal, not necessarily least, element), which supports induction without requiring totality; program-termination proofs are exactly arguments that a certain relation on program states is well-founded.

Two neighbouring results deserve contrast. Zermelo's well-ordering theorem ("every set can be well-ordered") is equivalent to the axiom of choice and is non-constructive: nobody can exhibit a well-order of \( \mathbb{R} \). The WOP for \( \mathbb{N} \) needs no choice whatsoever — the least element is definable. Second, in \( \mathbb{R} \) the analogous role is played by the completeness axiom (every non-empty set bounded below has an infimum); density forces the weaker conclusion, and much of real analysis is the art of working with infima where number theory would take minima.

A finer logical point: the equivalence proved above is relative to a base theory, and the choice of base matters. In second-order arithmetic, induction and WOP (as statements about all subsets of \( \mathbb{N} \)) are straightforwardly interderivable as above. In first-order Peano arithmetic both become axiom schemes, one instance per formula \( \varphi \), and the translation costs something: deriving the least-number principle for \( \varphi \) uses induction on a formula of slightly higher logical complexity (the cumulative predicate of Step 2 has an extra bounded quantifier). Over weak fragments the hierarchies \( \mathrm{I}\Sigma_n \) (induction for \( \Sigma_n \) formulas) and \( \mathrm{L}\Sigma_n \) (least number principle for \( \Sigma_n \) formulas) interleave rather than coincide levelwise — for instance \( \mathrm{I}\Sigma_n \) is equivalent to \( \mathrm{L}\Sigma_n \), but \( \mathrm{I}\Sigma_n \) and induction for \( \Delta_n \) formulas separate. The slogan "induction \( = \) well-ordering" is exactly true at degree level and in second-order arithmetic, and true-with-bookkeeping in fragments.

Common misconceptions. (i) "WOP holds for any set with a lower bound" — false; \( (0,1) \) is bounded below with no least element. (ii) "The least element is unique because WOP says so" — uniqueness is a separate (easy) fact from antisymmetry: two least elements \( m, m' \) satisfy \( m \le m' \) and \( m' \le m \), hence \( m = m' \). (iii) "Induction proves \( P \) for infinite \( n \)" — induction yields \( P(n) \) for each natural \( n \); it says nothing about a limit or an "infinite stage", which is precisely where transfinite induction differs by adding limit cases.

Worked examples

Example 1. Every natural number \( n \ge 2 \) has a prime divisor.

Fix \( n \ge 2 \) and let \( S = \{ d \in \mathbb{N} : d \ge 2 \text{ and } d \mid n \} \).

We hunt for a prime among the divisors; WOP will produce the candidate. A

\( S \neq \emptyset \), since \( n \in S \) (indeed \( n \ge 2 \) and \( n \mid n \)).

Non-emptiness check — mandatory before invoking WOP. A

By the well-ordering principle, \( S \) has a least element \( p \).

Direct application of the theorem to \( S \subseteq \mathbb{N} \), \( S \neq \emptyset \). A

Claim: \( p \) is prime. Suppose not; since \( p \ge 2 \), there is a factorisation \( p = ab \) with \( 1 \lt a \lt p \) (definition of composite). Then \( a \mid p \) and \( p \mid n \), so \( a \mid n \) by transitivity of divisibility; and \( a \ge 2 \). Hence \( a \in S \) with \( a \lt p \), contradicting minimality of \( p \).

Key move: minimality converts "smaller divisor exists" into a contradiction. Uses the definition of prime/composite and transitivity of \( \mid \) (if \( a \mid b \) and \( b \mid c \) then \( a \mid c \): write \( b = ak,\ c = bl \), so \( c = a(kl) \)). B

\[ \forall n \ge 2\ \ \exists\, p \text{ prime}: \ p \mid n. \]

Reading. The smallest non-trivial divisor of any number is automatically prime — a one-line consequence of well-ordering, and the first step of the fundamental theorem of arithmetic.

Scope. All integers \( n \ge 2 \); extends to \( n \le -2 \) by applying it to \( |n| \).

Example 2. The division algorithm: for all \( a \in \mathbb{N} \) and \( b \ge 1 \) there exist \( q, r \in \mathbb{N} \) with \( a = qb + r \) and \( 0 \le r \lt b \).

Let \( S = \{ s \in \mathbb{N} : \exists q \in \mathbb{N},\ a = qb + s \} \).

\( S \) is the set of all candidate remainders; we avoid subtraction in \( \mathbb{N} \) by phrasing membership additively. A

\( S \neq \emptyset \): taking \( q = 0 \) gives \( a = 0 \cdot b + a \), so \( a \in S \).

Non-emptiness witness. A

By WOP, \( S \) has a least element \( r \), with witness \( q \): \( a = qb + r \).

Application of the theorem. A

Claim: \( r \lt b \). Suppose instead \( r \ge b \). Then \( r - b \in \mathbb{N} \), and \[ a = qb + r = qb + b + (r - b) = (q+1)b + (r-b), \] so \( r - b \in S \). But \( b \ge 1 \) gives \( r - b \lt r \), contradicting minimality of \( r \). Hence \( r \lt b \), and \( (q, r) \) is the required pair.

Descent step: a too-large remainder can be shrunk by one more subtraction of \( b \); minimality forbids this. Subtraction is legal since \( r \ge b \); the strict inequality \( r - b \lt r \) uses \( b \ge 1 \) (this is where the hypothesis \( b \neq 0 \) is consumed — for \( b = 0 \) the statement is false unless \( b \mid a \)). B

Uniqueness (for completeness): if \( qb + r = q'b + r' \) with \( 0 \le r, r' \lt b \) and, say, \( q \lt q' \), then \( r - r' = (q' - q) b \ge b \), impossible since \( r - r' \le r \lt b \). So \( q = q' \), hence \( r = r' \).

Standard uniqueness argument by comparing the two representations; not needed for the WOP illustration but stated so the result is the full division algorithm. C

\[ \forall a \in \mathbb{N},\ \forall b \ge 1\ \ \exists!\,(q,r): \ a = qb + r,\ \ 0 \le r \lt b. \]

Reading. Keep subtracting \( b \) while you still can; well-ordering guarantees the process bottoms out, and the floor it hits is the remainder.

Scope. \( a \in \mathbb{N} \), \( b \ge 1 \); the extension to \( a \in \mathbb{Z} \) follows by translating \( a \) by a large multiple of \( b \). Fails for \( b = 0 \).

Problems

Prove that there is no natural number \( n \) with \( 0 \lt n \lt 1 \).
Solution

Let \( S = \{ n \in \mathbb{N} : 0 \lt n \lt 1 \} \) and suppose \( S \neq \emptyset \). By WOP, \( S \) has a least element \( m \), so \( 0 \lt m \lt 1 \). Multiplying the inequality \( 0 \lt m \lt 1 \) through by \( m \gt 0 \) (multiplication by a positive number preserves strict inequalities) gives \( 0 \lt m^2 \lt m \lt 1 \). Hence \( m^2 \in \mathbb{N} \) (closure under multiplication) with \( 0 \lt m^2 \lt 1 \), so \( m^2 \in S \); but \( m^2 \lt m \) contradicts the minimality of \( m \). Therefore \( S = \emptyset \). \( \blacksquare \)
Prove that every non-empty subset \( A \subseteq \mathbb{Z} \) that is bounded below has a least element.
Solution

Let \( b \in \mathbb{Z} \) be a lower bound: \( b \le a \) for all \( a \in A \). Define the translate \( A' = \{ a - b : a \in A \} \). Each \( a - b \ge 0 \), so \( A' \subseteq \mathbb{N} \), and \( A' \neq \emptyset \) since \( A \neq \emptyset \). By WOP, \( A' \) has a least element \( m' = a_0 - b \) for some \( a_0 \in A \). Then for any \( a \in A \): \( a - b \in A' \), so \( a_0 - b = m' \le a - b \), hence \( a_0 \le a \) (adding \( b \) preserves the order). Thus \( a_0 \) is a least element of \( A \). \( \blacksquare \) (Remark: both hypotheses are needed — \( \emptyset \) has no least element, and \( \mathbb{Z} \) itself is non-empty but unbounded below with no least element.)
Use the well-ordering principle to prove that \( \sqrt{2} \) is irrational.
Solution

Suppose \( \sqrt{2} = p/q \) with \( p, q \) positive integers. Then the set \( S = \{ q \in \mathbb{N} : q \ge 1 \text{ and } q\sqrt{2} \in \mathbb{N} \} \) is non-empty. By WOP let \( q_0 \) be its least element, and put \( p_0 = q_0 \sqrt{2} \in \mathbb{N} \). From \( 1 \lt \sqrt{2} \lt 2 \) (since \( 1 \lt 2 \lt 4 \) and squaring is order-preserving on positives) we get \( q_0 \lt p_0 \lt 2q_0 \), hence \( 0 \lt p_0 - q_0 \lt q_0 \). Set \( q_1 = p_0 - q_0 \). Then \[ q_1 \sqrt{2} = (p_0 - q_0)\sqrt{2} = p_0 \sqrt{2} - q_0 \sqrt{2} = q_0 \cdot 2 - p_0 = 2q_0 - p_0, \] using \( p_0 \sqrt{2} = q_0 (\sqrt{2})^2 = 2 q_0 \). Since \( p_0 \lt 2 q_0 \), the number \( 2q_0 - p_0 \) is a positive integer, so \( q_1 \sqrt{2} \in \mathbb{N} \) and \( q_1 \ge 1 \), i.e. \( q_1 \in S \). But \( q_1 \lt q_0 \), contradicting minimality. Hence \( S = \emptyset \) and \( \sqrt{2} \notin \mathbb{Q} \). \( \blacksquare \)
Derive the principle of strong induction from the well-ordering principle: if for every \( n \in \mathbb{N} \) the implication \( \big( \forall m \lt n,\ P(m) \big) \Rightarrow P(n) \) holds, then \( P(n) \) holds for all \( n \).
Solution

Assume the hypothesis and let \( S = \{ n \in \mathbb{N} : \neg P(n) \} \). Suppose \( S \neq \emptyset \); by WOP it has a least element \( n_0 \). By minimality, every \( m \lt n_0 \) satisfies \( m \notin S \), i.e. \( P(m) \) holds for all \( m \lt n_0 \). The hypothesis applied at \( n = n_0 \) then yields \( P(n_0) \), contradicting \( n_0 \in S \). Hence \( S = \emptyset \), i.e. \( \forall n\, P(n) \). \( \blacksquare \) (Note there is no separate base case: at \( n_0 = 0 \) the antecedent "\( \forall m \lt 0,\ P(m) \)" is vacuously true, so the hypothesis already demands \( P(0) \) outright. Forgetting that the \( n = 0 \) instance must be verified unconditionally is a classic error.)
Let \( \mathbb{N} \times \mathbb{N} \) carry the lexicographic order: \( (a, b) \prec (c, d) \) iff \( a \lt c \), or \( a = c \) and \( b \lt d \). Prove that \( \prec \) is a well-order, i.e. every non-empty \( S \subseteq \mathbb{N} \times \mathbb{N} \) has a \( \prec \)-least element. Explain which ordinal this order realises.
Solution

Let \( S \subseteq \mathbb{N} \times \mathbb{N} \) be non-empty. Consider the set of first coordinates \( A = \{ a \in \mathbb{N} : \exists b,\ (a,b) \in S \} \). \( A \) is non-empty (project any element of \( S \)), so by WOP it has a least element \( a_0 \). Next consider \( B = \{ b \in \mathbb{N} : (a_0, b) \in S \} \); by choice of \( a_0 \) this is non-empty, so by WOP again it has a least element \( b_0 \). We claim \( (a_0, b_0) \) is \( \prec \)-least in \( S \). Take any \( (c, d) \in S \). Then \( c \in A \), so \( a_0 \le c \). If \( a_0 \lt c \), then \( (a_0, b_0) \prec (c, d) \) by the first clause. If \( a_0 = c \), then \( d \in B \), so \( b_0 \le d \); if \( b_0 \lt d \) the second clause gives \( (a_0, b_0) \prec (c,d) \), and if \( b_0 = d \) the pairs are equal. In all cases \( (a_0,b_0) \preceq (c,d) \). Totality of \( \prec \) follows from totality of \( \le \) on \( \mathbb{N} \) coordinatewise, so \( \prec \) is a well-order. \( \blacksquare \)

This order has order type \( \omega \cdot \omega = \omega^2 \): it consists of infinitely many consecutive copies of \( \omega \) (one copy \( \{a\} \times \mathbb{N} \) for each \( a \)), laid end to end. It is a well-order in which some elements — e.g. \( (1, 0) \) — have infinitely many predecessors, showing that well-ordering does not require each element to be reached in finitely many steps; this is precisely the gateway from ordinary to transfinite induction.