Well-Orders and Least Elements

Well-ordering is the quiet engine behind ordinary mathematical induction, so it appears anywhere induction does: correctness proofs for recursive algorithms in computer science, termination arguments for loops and rewriting systems, and inductive definitions of syntax in logic (formulas, proofs, terms). In set theory and logic, well-orders generalize to ordinal numbers, which classify order types of well-orders and underpin transfinite induction and transfinite recursion — techniques essential for constructing objects (like a well-ordering of $\mathbb{R}$, or a non-measurable set) that cannot be built in finitely many or even countably many steps. In computer science, well-founded orders (a close relative, dropping totality) justify termination proofs for recursive functions and are the basis of well-founded recursion in proof assistants such as Coq and Lean. In combinatorics and the foundations of counting, well-ordering of $\mathbb{N}$ is exactly the fact that licenses "there is a smallest counterexample" style proofs, which is the standard route into rigorously establishing facts about Finite Sets and Counting. Even in algebra, well-ordered index sets appear in transfinite constructions of vector space bases and in the study of ordinal-indexed sequences in analysis and topology.

:::quiz[What goes wrong when trying to well-order $\mathbb{Q} \cap (0,1]$ with the usual order?]

• The order is not total.
• The order is not transitive.
• No nonempty subset ever has a least element.
• The subset itself has no least element, since dividing any candidate by 2 gives something smaller still in the set ✓

Ask the tutor: Can you show me step by step why the negative integers, as a subset of $\mathbb{Z}$, have no least element under the usual order?

Picture the natural numbers laid out on a ray starting at $0$. Any nonempty collection of dots on this ray — no matter how sparse, how large, even if infinite — has a leftmost dot. You can see this: sweep a marker from $0$ to the right, and it must hit the collection somewhere for the first time, because there are only finitely many candidates to check before reaching any given point. This "leftmost dot always exists" phenomenon is exactly the well-ordering property, and it is what makes proofs like "suppose for contradiction there is a counterexample; take the smallest one" logically airtight on $\mathbb{N}$. Contrast this with the integers. Take $S = \mathbb{Z}$ itself: sweeping from the left, there is no leftmost point, because the ray extends infinitely in both directions. The order $(\mathbb{Z}, \le)$ fails the well-ordering property — not because it lacks a total order, but because some nonempty subsets (like $\mathbb{Z}$ itself, or the negative integers) have no least element. The rational numbers fail even more dramatically: even a bounded nonempty set like $\{q \in \mathbb{Q} : q > 0\}$ has no least element, since between $0$ and any positive rational there's a smaller one.

Example 1: A well-order on a non-numeric-looking set. Let $A = \{a_1, a_2, a_3, \dots\} \cup \{\omega\}$ be a set with elements $a_1, a_2, a_3, \ldots$ (one for each positive integer) together with one extra element $\omega$. Define $\le$ by:

So the order looks like $a_1 < a_2 < a_3 < \cdots < \omega$, with $\omega$ placed above every $a_i$. Claim: $(A, \le)$ is a well-order. Verification. First, $\le$ is a total order: reflexivity and antisymmetry are immediate from the definitions (distinct elements compare via their indices, or via the special top rule for $\omega$), and transitivity is checked by cases (if $a_i \le a_j \le a_k$ then $i \le j \le k$ so $i \le k$; anything $\le \omega$ stays $\le \omega$). Totality holds since any two $a_i, a_j$ compare via integer order, and $\omega$ compares above everything. Now let $S \subseteq A$ be nonempty. Two cases: Case 1: $S \subseteq \{a_1, a_2, \dots\}$. Let $I = \{i \in \mathbb{Z}^+ : a_i \in S\}$, a nonempty subset of the positive integers. By the well-ordering property of $(\mathbb{N},\le)$ (positive integers form a subset of $\mathbb{N}$, and any nonempty subset of $\mathbb{N}$ has a least element by (WO)), $I$ has a least element $i_0$. Then $a_{i_0} \in S$ and $a_{i_0} \le a_j$ for every $a_j \in S$ since $i_0 \le j$ for all $j \in I$. So $a_{i_0} = \min(S)$. Case 2: $\omega \in S$. If $S = \{\omega\}$, then $\min(S) = \omega$ trivially. Otherwise $S$ contains some $a_i$'s too; let $S' = S \setminus \{\omega\}$, nonempty, handled by Case 1 to get $\min(S') = a_{i_0}$. Since $a_{i_0} \le \omega$, we get $a_{i_0} \le s$ for all $s \in S$ (including $\omega$), so $a_{i_0} = \min(S)$. In both cases $S$ has a least element, so $(A, \le)$ is a well-order. $\checkmark$ Note this well-order is not order-isomorphic to $(\mathbb{N}, \le)$: in $\mathbb{N}$, every element has finitely many predecessors, but $\omega$ has infinitely many predecessors (all the $a_i$). This shows well-orders come in genuinely different "shapes" (order types) even at the same cardinality — a phenomenon fully developed in the theory of ordinal numbers.

Example 2: A total order that fails to be a well-order, checked carefully. Let $B = \mathbb{Q} \cap [0,1]$, the rational numbers between $0$ and $1$ inclusive, with the usual order $\le$. Claim: $(B, \le)$ is a total order but not a well-order. Verification of total order: $\le$ restricted from $\mathbb{Q}$ is reflexive, antisymmetric, transitive, and total — these are inherited automatically since $B \subseteq \mathbb{Q}$ and $\le$ on $\mathbb{Q}$ already has these properties (a sub-relation of a total order restricted to a subset remains a total order on that subset, since the defining universally-quantified properties persist when the domain shrinks). Failure of the least-element property: Consider $S = \{q \in B : q > 0\} = \mathbb{Q} \cap (0,1]$. This is nonempty (e.g. $1 \in S$). Suppose for contradiction $S$ has a least element $m$. Since $m \in S$, $m > 0$. Consider $m' = m/2$. Then $m'$ is rational (quotient of rationals with nonzero denominator $2$), $0 < m' < m \le 1$, so $m' \in B$ and $m' > 0$, hence $m' \in S$. But $m' < m$ contradicts minimality of $m$ in $S$. Hence no least element exists for $S$, so $(B,\le)$ fails the well-ordering property despite being a perfectly good total order. This confirms concretely that totality alone never suffices for well-ordering — density of the rationals is precisely the obstruction, since between any two distinct rationals lies a third.