Fact-checked by Grok 2 weeks ago

Well-ordering theorem

The well-ordering theorem, also known as Zermelo's well-ordering theorem, asserts that every set can be equipped with a total order such that every non-empty subset of the set has a least element with respect to that order.^[1] This property defines a well-ordering, a linear ordering where the relation "<" is total, irreflexive, transitive, and ensures no infinite descending chains exist.^[2] The theorem was first proved by Ernst Zermelo in 1904, marking a foundational result in set theory.^[1] Distinct from the well-ordering principle—which posits that the natural numbers under the standard ordering are well-ordered, serving as an axiom equivalent to mathematical induction—the well-ordering theorem extends this property to arbitrary sets, including uncountable ones like the real numbers.^[3] Zermelo's proof relies on the axiom of choice (AC), which allows selecting one element from each set in a collection of non-empty sets; the two statements are logically equivalent within Zermelo-Fraenkel set theory.^[4] This equivalence implies that the theorem's acceptance hinges on AC, a controversial yet indispensable axiom in modern mathematics.^[5] The theorem's significance lies in enabling the construction of ordinal numbers, which generalize natural numbers to transfinite ordinals and facilitate the systematic study of infinite sets' sizes and structures.^[6] It underpins key results in analysis, topology, and algebra, such as the existence of maximal ideals in rings via equivalents like Zorn's lemma, though its non-constructive nature—providing no explicit ordering for most sets—has sparked ongoing philosophical debate in foundations of mathematics.^[4]

Statement and context

Formal statement

The well-ordering theorem, also known as Zermelo's well-ordering theorem, asserts that every set admits a well-ordering.^[7] A total order \leq on a set X is a well-order if every non-empty subset of X has a least element with respect to \leq. Equivalently, using the associated strict total order <, every non-empty subset has a minimal element, and there are no infinite descending chains \dots < x_2 < x_1. In such a well-order, for any element x \in X, the successor of x can be defined as the least element y > x if it exists, reflecting the discrete structure of the ordering beyond limit points. This theorem is a non-constructive existence principle: it guarantees the availability of a well-ordering for any set but provides no method to explicitly construct it without additional assumptions like the axiom of choice. For instance, the natural numbers equipped with the standard less-than-or-equal-to relation form a well-order.

Relation to natural numbers

The well-ordering property of the natural numbers states that every non-empty subset S \subseteq \mathbb{N} has a least element under the standard ordering <, meaning there exists some m \in S such that m \leq n for all n \in S.^[8] This principle, often called the well-ordering principle for \mathbb{N}, serves as a foundational tool in proofs involving positive integers, such as the division algorithm and unique prime factorization.^[9] To prove this property using mathematical induction, assume for contradiction that S \subseteq \mathbb{N} is non-empty but has no least element. Define T = \mathbb{N} \setminus S, and show by induction that T = \mathbb{N}. The base case holds since $0 \notin S (or $1, depending on the convention for \mathbb{N}). For the inductive step, assume k \in T; then k+1 \notin S, as otherwise k+1 would be the least element of S. Thus, T = \mathbb{N}, implying S = \emptyset, a contradiction.^[10] This well-ordering principle is logically equivalent to the axiom of mathematical induction in first-order Peano arithmetic, where both capture the idea that properties true for the base case and preserved under the successor operation hold for all natural numbers.^[11] Unlike the general well-ordering theorem, which asserts that every set can be well-ordered and is equivalent to the axiom of choice, the version for \mathbb{N} is provable directly from the axioms of ZF set theory without requiring choice.^[12] The general theorem thus extends this provable special case to all sets but depends on the additional strength of the axiom of choice.^[13]

Well-orderings

Definition and properties

A well-ordering on a set X is a binary relation < that is a strict total order—meaning it is irreflexive (x \not< x for all x \in X), transitive (if x < y and y < z, then x < z), and total (for any distinct x, y \in X, either x < y or y < x)—with the additional property that every non-empty subset of X has a least element, i.e., an element m such that m \leq y for all y in the subset, where \leq is the reflexive closure of <.^[14]^[15] Equivalently, it can be defined using the non-strict order \leq, which is antisymmetric, transitive, total, and satisfies the minimum condition that every non-empty subset has a minimal element.^[15] A fundamental property of a well-ordering is the absence of infinite descending chains: there do not exist elements a_1 > a_2 > a_3 > \cdots in the set, as any such chain would form a non-empty subset without a least element.^[14]^[15] This ensures that the order is "well-founded," preventing indefinite regression. Comparability follows from the total order: every pair of elements is comparable. Trichotomy holds precisely: for any two elements a, b \in X, exactly one of a < b, a = b, or a > b is true.^[14]^[15] Every well-ordered set has an order type that is an ordinal number, which uniquely classifies its structure up to order isomorphism.^[14]^[15] Moreover, initial segments of a well-ordered set—subsets of the form \{x \in X \mid x < a\} for some a \in X—inherit the well-ordering, meaning they are themselves well-ordered under the induced relation.^[15] The natural numbers under the standard ordering provide the simplest example of an infinite well-ordered set.^[14]

Examples

Finite totally ordered sets provide the simplest examples of well-orderings. For instance, the set \{1, 2, 3\} equipped with the standard less-than relation \langle is well-ordered, as every nonempty subset has a least element: the singleton \{3\} has least element 3, \{1, 3\} has least element 1, and the full set has least element 1. In general, any finite totally ordered set is well-ordered under its given order. Among infinite sets, the natural numbers \mathbb{N} = \{0, 1, 2, \dots \} under the standard ordering \langle form a well-ordering of order type \omega, the smallest infinite ordinal, where every nonempty subset has a least element, enabling mathematical induction.^[16] In contrast, the integers \mathbb{Z} under the standard ordering are not well-ordered, as the subset of negative integers has no least element.^[2] Similarly, the rational numbers \mathbb{Q} under the standard ordering lack a well-ordering, since dense subsets like the positive rationals less than 1 have no minimal element.^[2] Ordinal numbers themselves exemplify well-orderings in set theory, where each ordinal is the order type of a well-ordered set consisting of all smaller ordinals. For example, the finite ordinal 3 is the set \{0, 1, 2\} ordered by membership, with 0 as the least element, followed by 1 and then 2.^[17] The ordinal \omega + 1 extends \mathbb{N} by adding a single element greater than all naturals, such as \mathbb{N} \cup \{\omega\} with the order where n < m for n, m \in \mathbb{N}, all naturals less than \omega, yielding a well-ordering where the subset \mathbb{N} has least element 0, but the full set has least element 0 with no infinite descending chains.^[18]

Equivalences

To the axiom of choice

The axiom of choice (AC) states that, given any set X of nonempty sets, there exists a choice function f: X \to \bigcup X such that f(A) \in A for every A \in X.^[19] In Zermelo-Fraenkel set theory without choice (ZF), the well-ordering theorem is logically equivalent to AC.^[20] To see that the well-ordering theorem implies AC, consider a collection \{A_i \mid i \in I\} of nonempty sets; well-order their union S = \bigcup_{i \in I} A_i and define the choice function by selecting, for each A_i, the least element of A_i in this well-ordering of S.^[20] Conversely, AC implies the well-ordering theorem by using transfinite recursion along the cardinals of the power set hierarchy to construct a well-ordering on any given set, assigning ordinals to elements via choice functions on previous stages.^[20] This equivalence underscores the foundational strength of both principles in ZF, enabling key results such as the existence of a basis for every vector space over any field.^[21] The well-ordering theorem is also equivalent to Zorn's lemma.^[20] In 1904, Ernst Zermelo employed AC to establish the well-ordering theorem, demonstrating that every set, including the reals, admits a well-ordering.^[22]

To Zorn's lemma

Zorn's lemma states that if every chain in a partially ordered set (poset) has an upper bound, then the poset contains at least one maximal element. This principle, introduced by Max Zorn in 1935 as a "maximum principle" in the context of transfinite algebra, provides a tool for establishing the existence of maximal elements without constructing them explicitly. The well-ordering theorem is equivalent to Zorn's lemma within Zermelo–Fraenkel set theory (ZF). To see that the well-ordering theorem implies Zorn's lemma, one well-orders the poset and uses transfinite ascent along this ordering to extend any chain to a maximal element.^[23] Conversely, Zorn's lemma implies the axiom of choice (and hence the well-ordering theorem) by applying it to the poset of partial choice functions on a family of nonempty sets, ordered by extension, to obtain a maximal choice function that selects one element from each set.^[24] These equivalences highlight how both principles rely on non-constructive methods to guarantee existence in infinite structures.^[25] Zorn's lemma finds extensive applications in algebra and topology, often where the axiom of choice is invoked indirectly through poset maximality. In algebra, it proves the existence of bases for modules over rings, such as showing that every vector space has a basis by considering the poset of linearly independent subsets ordered by inclusion.^[25] It also establishes the existence of maximal ideals in commutative rings with identity, which is crucial for quotient ring constructions and algebraic geometry.^[26] In topology, Zorn's lemma underpins Tychonoff's theorem, which states that the product of compact topological spaces is compact, by applying it to the poset of compactifications.^[25] While equivalent to the axiom of choice, Zorn's lemma is often more intuitive for proofs involving partial orders, as it directly addresses chain conditions and maximality in posets, whereas the axiom of choice focuses on selecting elements from disjoint nonempty sets.^[23] This makes Zorn's formulation particularly useful in contexts where the structure is naturally ordered, such as lattices or filter systems.^[24]

Proofs

Proof from the axiom of choice

The well-ordering theorem can be proved from the axiom of choice (AC) via a constructive process that builds a well-ordering on any given set X using transfinite recursion and a choice function. Assume AC holds, which implies the existence of a choice function f on the family of all nonempty subsets of X, that is, f: \mathcal{P}(X) \setminus \{\emptyset\} \to X such that f(A) \in A for every nonempty A \subseteq X.^[27]^[21] To construct the well-ordering, define a function h: \mathrm{Ord} \to X by transfinite recursion as follows. Set h(0) = f(X), so the initial element is chosen from the entire set X. For a successor ordinal \alpha = \beta + 1, define h(\alpha) = f\left(X \setminus \bigcup_{\gamma \leq \beta} \{h(\gamma)\}\right), selecting an element from the subset of X excluding all previously chosen elements. For a limit ordinal \lambda, define h(\lambda) = f\left(X \setminus \bigcup_{\beta < \lambda} \{h(\beta)\}\right), again choosing from the remaining unused elements up to that stage. This recursion ensures that each h(\alpha) is distinct from all prior values, as the argument to f is nonempty (by the recursion hypothesis) and excludes previous images.^[27]^[21] The function h is injective because if h(\alpha) = h(\delta) for \alpha < \delta, then at stage \delta, the remaining set would exclude h(\alpha), contradicting the choice. The process terminates in the sense that there exists some ordinal \tau such that the image h[\tau] = \{h(\alpha) \mid \alpha < \tau\} = X, with h bijective onto X. This follows because the recursion cannot continue indefinitely without repeating or exhausting X; specifically, the length \tau is at most the Hartogs number of X, the smallest ordinal not injectable into X, ensuring surjectivity before exceeding the cardinal |X|. Thus, \tau is the order type of the well-ordering, isomorphic to the initial segment of ordinals up to \tau.^[27] Finally, define a binary relation \prec on X by x \prec y if and only if the unique ordinal \alpha with h(\alpha) = x is less than the unique ordinal \beta with h(\beta) = y. This relation is a strict total order on X, and every nonempty subset Y \subseteq X has a least element, namely h(\min \{ \alpha < \tau \mid h(\alpha) \in Y \}), because the ordinals are well-ordered. Therefore, (X, \prec) is a well-ordering of X.^[27]^[21]

Proof of the axiom of choice

The well-ordering theorem implies the axiom of choice by providing a method to construct a choice function for any family of nonempty sets. Consider an arbitrary family of nonempty sets \{A_i \mid i \in I\}, where I is the index set. To ensure disjointness, form the tagged union S = \bigcup_{i \in I} (\{i\} \times A_i), a set whose elements distinguish the copies of each A_i. By the well-ordering theorem, the set S can be well-ordered by some relation \prec. For each i \in I, the subset \{i\} \times A_i \subseteq S is nonempty and hence possesses a \prec-least element, say (i, a_i). Define the function f: I \to \bigcup_{i \in I} A_i by f(i) = a_i; this f selects one element from each A_i, serving as a choice function for the family. The well-ordering guarantees the existence of such a least element in every slice \{i\} \times A_i, ensuring the construction succeeds without further assumptions.

History

Early ideas

In the late 19th century, Georg Cantor laid the groundwork for the well-ordering theorem through his pioneering work on transfinite numbers and infinite sets. To extend the classification of infinities beyond mere cardinality, Cantor introduced the concept of transfinite ordinals in the 1880s, which describe the order types of well-ordered sets—linear orders where every non-empty subset has a least element. These ordinals allowed for a hierarchical structuring of infinite collections, distinguishing, for instance, the countable order type ω of the natural numbers from denser infinite arrangements. Cantor's development of well-orderings was essential for assigning ordinal numbers to sets, enabling a more nuanced understanding of their sequential properties rather than just their sizes.^[28] Cantor's motivations were deeply rooted in the challenges of set theory, particularly the need to order infinite sets to address the continuum hypothesis, which posits that there is no cardinality between that of the natural numbers and the real numbers. He firmly believed that every set, including the continuum of real numbers, could be well-ordered, viewing this as a necessary step to resolve whether the reals have order type ω₁, the smallest uncountable ordinal. This conviction drove much of his research in the 1880s, as well-orderings provided a tool to compare and enumerate infinities systematically. Philosophically, Cantor regarded the well-ordering principle as a "fundamental and certainly remarkable law of thought," an intuitive axiom applicable to all well-defined sets, reflecting his Platonist outlook on the objective reality of infinite structures.^[29]^[28] Entering the early 20th century, these ideas culminated in Ernst Zermelo's 1904 proof that every set can be well-ordered, achieved by invoking what became known as the axiom of choice to select elements iteratively and construct a total order. This result, published in Mathematische Annalen, extended Cantor's hypothesis to the continuum and aimed to settle foundational debates in set theory. However, it ignited significant controversy, with critics like Émile Borel and Giuseppe Peano questioning the axiom of choice's non-constructive nature and its implications for explicit definitions of orderings, prompting broader discussions on the foundations of mathematics.^[30]

Formalization

In 1908, Ernst Zermelo published a foundational axiomatization of set theory consisting of seven axioms, which explicitly incorporated the axiom of choice as its final axiom to ensure the existence of choice functions for infinite collections of sets.^[30] This system derived the well-ordering theorem as a theorem, demonstrating that every set admits a well-ordering under the given axioms, thereby rigorizing the principle within a formal framework. The equivalence between the axiom of choice and the well-ordering theorem was established in this axiomatization.^[30] In the early 1900s, Julius Kőnig advanced ordinal theory by exploring transfinite arithmetic and the structure of well-ordered sets, laying groundwork for understanding equivalences involving well-orderings and choice principles through his work on infinite cardinals and paradoxes.^[31] Concurrently, Felix Hausdorff contributed significantly by developing a systematic theory of order types in his 1914 monograph Grundzüge der Mengenlehre, where he formalized ordinal numbers as isomorphism classes of well-ordered sets and proved key results linking well-orderings to cardinal comparisons, implicitly relying on choice-like assumptions.^[32] These efforts by Kőnig and Hausdorff established foundational equivalences between the well-ordering principle, the axiom of choice, and related infinitary principles, influencing subsequent axiomatic developments. During the 1920s and 1930s, Kurt Gödel's construction of the inner model known as the constructible universe L demonstrated the relative consistency of the axiom of choice—and thus the well-ordering theorem—with Zermelo-Fraenkel set theory (ZF), showing that if ZF is consistent, then so is ZF plus choice.^[33] This work, published in 1938 and 1940, addressed ongoing debates about the necessity and consistency of choice by exhibiting a model where well-orderings exist for all sets without contradicting ZF axioms.^[34] In 1935, Max Zorn formulated Zorn's lemma, which was promptly recognized as equivalent to the axiom of choice within ZF set theory.^[33] Following World War II, the Zermelo-Fraenkel axioms (ZF) emerged as the standard foundation for set theory, with the axiom of choice—and by extension the well-ordering theorem—adopted optionally as ZFC, reflecting broad acceptance despite its non-constructive nature, as it permits proofs without explicit constructions of well-orderings.^[33] This recognition underscored the theorem's reliance on impredicative methods, distinguishing it from more intuitive set-theoretic principles.^[33]

References

[1]
Beweis, daß jede Menge wohlgeordnet werden kann
Beweis, daß jede Menge wohlgeordnet werden kann. Aus einem an Herrn Hilbert gerichteten Briefe. Download PDF.
[2]
[PDF] The Well-Ordering Theorem
A set is well-ordered if any nonempty subset has a least element. The natural numbers are well-ordered, but integers are not with the usual order.
[3]
[PDF] Well Ordering Principle: Chapter 2.1 – 2.3 - MIT OpenCourseWare
Every nonempty set of nonnegative integers has a smallest element. This statement is known as The Well Ordering Principle. Do you believe it? Seems sort of ...
[4]
[PDF] 11. The Axiom of Choice
The following are equivalent: 1. The Axiom of Choice. 2. The Well-Ordering Theorem. 3. Zorn's Lemma. We will not prove this theorem ...
[5]
[PDF] The Axiom of Choice and Related Topics
May 12, 2020 · Since every set has a well-order by the Well-Ordering Theorem, each element of an infinite set can be assigned a unique ordinal number, then ...
[6]
[PDF] Mathematics 4530 Ordinal numbers and the well-ordering theorem
The main result of this handout is the well-ordering theorem: Theorem. Every set X admits a well-ordering. The idea behind the construction of a well-ordering ...
[7]
https://doi.org/10.1007/BF01445300
[8]
[PDF] The Well-Ordering Principle
The well-ordering principle states that every non-empty subset of natural numbers has a least element, and is equivalent to mathematical induction.
[9]
[PDF] The Division Algorithm
Jul 11, 2000 · The Well Ordering Principle for Natural Numbers. Any non-empty set of positive (or non-negative) integers contains a smallest number. Taking ...
[10]
[PDF] proofs by induction and contradiction, and well-ordering of n
Proofs by induction require showing a base case and an inductive step. Proofs by contradiction assume a conclusion is false and try to prove a contradiction. ...
[11]
[PDF] 3. Mathematical Induction 3.1. First Principle of ... - FSU Math
The set N of natural numbers forms a well-ordered set. Discussion. As we prove below, the principle of induction is equivalent to the well-ordering principle.<|control11|><|separator|>
[12]
Set Theory | Internet Encyclopedia of Philosophy
Well-Ordering Theorem: Every set can be well-ordered. In his clever proof of the well-ordering theorem, Zermelo formulated and applied the following ...<|control11|><|separator|>
[13]
[PDF] Section 0.7. The Axiom of Choice, Order, and Zorn's Lemma
Jan 24, 2021 · Notice that the natural numbers are well ordered under the usual less than or equal to. Note. Another statement equivalent to the Axiom of ...
[14]
Well Ordered Set -- from Wolfram MathWorld
A totally ordered set (A,<=) is said to be well ordered (or have a well-founded order) iff every nonempty subset of A has a least element.
[15]
Well-ordered set - Encyclopedia of Mathematics
Jan 8, 2017 · A well-ordered set is a totally ordered set satisfying the minimum condition. The concept of a well-ordered set was introduced by G. Cantor.
[16]
Puzzle 6: Solution - Harvard Mathematics Department
Every finite set is well-ordered. The classic example of an infinite well-ordered set is {1,2,3,...}, which is infinite but of course only countable.) A No.
[17]
[PDF] Chapter 8 Ordered Sets
Theorem 5.20 Every set of ordinals is well-ordered. In particular, every ... This “informal” statement is a reasonably accurate paraphrase of a precise theorem in ...
[18]
[PDF] 1 Well-ordered sets 2 Ordinals
Examples of ordinals: 0 = {}. 1 = {0}. 2 = {0,1}. 3 = {0,1,2} ... For example, if κ is finite, then a κ-filtered ordinal is just an infinite limit ordinal.
[19]
[PDF] The Ordinal Numbers and Transfinite Induction - Purdue Math
Sep 14, 2015 · An ordinal number can be thought of as the position of an element in a well-ordered set. Example. Let N ∪ {ω} have the same ordering as before.
[20]
The Axiom of Choice - Stanford Encyclopedia of Philosophy
Jan 8, 2008 · The Well-Ordering Theorem (Zermelo 1904, 1908). Every set can be well-ordered. After Zermelo published his 1904 proof of the well-ordering ...
[21]
[PDF] introduction to set theory
3rd ed ... The Axiom of Choice and its Equivalents. 137. 2. The Use of the Axiom of Choice ...
[22]
[PDF] the axiom of choice and its implications - UChicago Math
Aug 29, 2013 · By the Well-Ordering Principle, S can be well- ordered, so for some ordinal ↵, there exists an enumeration of S = 1p0,...,p⇠,...l.
[23]
[PDF] The Axiom of Choice
In 1904, Zermelo published his first proof that every set can be well-ordered. The proof is based on the so-called Axiom of Choice, denoted AC, which, ...
[24]
245B, Notes 7: Well-ordered sets, ordinals, and Zorn's lemma ...
Jan 28, 2009 · (Schroder-Bernstein theorem for well-ordered sets) Show that two well-ordered sets X, Y are isomorphic if and only if there is a morphism from X ...<|control11|><|separator|>
[25]
[PDF] The Axiom of Choice, the Well Ordering Principle and Zorn's Lemma
Jan 9, 2012 · We will discuss which axioms from Zermelo-Fraenkel Set Theory, ZF, we need for the proofs we give. Readers only interested in the equivalence ...
[26]
[PDF] Zorn's lemma and some applications - Keith Conrad
Zorn, A remark on method in transfinite algebra, Bull. Amer. Math. Soc. 41 (1935), 667–670. URL https:// www.ams.org/journals/bull/1935-41-10/S0002-9904 ...
[27]
[PDF] Zorn's lemma and examples of its application - OSU Math
Zorn's lemma is an extremely handy tool for dealing with constructions that require infinitely many steps to be done. Consider, for example, the following ...Missing: topology | Show results with:topology
[28]
[PDF] The Axiom of Choice and Some Equivalences: - Kenyon College
Nov 29, 2012 · It is proved from the well-ordering of the natural numbers and works on natural numbers. Here is a formal statement of induction: Theorem 2.10 ( ...<|control11|><|separator|>
[29]
The Early Development of Set Theory
Apr 10, 2007 · Cantor presented an argument that relied on the “Burali-Forti” paradox of the ordinals, and aimed to prove that every set can be well-ordered.
[30]
The Continuum Hypothesis - Stanford Encyclopedia of Philosophy
May 22, 2013 · ... reals. 2.1.2 Well-ordering Version. The second formulation of CH asserts that every well-ordering of the reals has order type less than ℵ2.
[31]
Zermelo's Axiomatization of Set Theory
Jul 2, 2013 · 2 Zermelo's 1904 Proof of the Well-Ordering Theorem. Zermelo's approach to the well-ordering problem took place in three stages. He published a ...
[32]
In the footsteps of Julius König's paradox - ScienceDirect
König stressed in a footnote at the end of the paper that his difference between classes and sets solved the problem of those paradoxes of the theory of ordinal ...
[33]
Felix Hausdorff (1868 - 1942) - Biography - MacTutor
He introduced the concept of a partially ordered set and from 1901 to 1909 he proved a series of results on ordered sets. In 1907 he introduced special types of ...
[34]
The Axiom of Choice - Stanford Encyclopedia of Philosophy
Jan 8, 2008 · The principle of set theory known as the Axiom of Choice has been ... proof of the well-ordering theorem. These assumptions constituted ...
[35]
Gödel's First Proof of the Consistency of the Axiom of Choice
1. Kurt Gödel famously established the relative consistency of the Axiom of Choice and of the Continuum Hypothesis in the latter 1930s.