Fact-checked by Grok 2 weeks ago

Transfinite induction

Transfinite induction is a proof technique in set theory that extends the principle of mathematical induction from the natural numbers to arbitrary well-ordered sets, particularly transfinite ordinals, enabling the establishment of properties for all elements in such a set by verifying a base case and an inductive step over predecessors.^[1]^[2] Developed in the late 19th and early 20th centuries as part of the foundations of set theory, transfinite induction originated with Georg Cantor's work on ordinal numbers in the 1880s, where he used iterative processes on well-ordered sets to analyze point-set topology and derived sets, laying the groundwork for handling infinite progressions without a final element.^[1] Ernst Zermelo further advanced the method in 1904 by formalizing its connection to the axiom of choice, which guarantees the well-ordering of any set, and applying it to prove results like the well-ordering theorem, thus integrating it into axiomatic set theory.^[1] Felix Hausdorff coined the term "transfinite induction" in 1906, solidifying its role in ordinal arithmetic and broader mathematical structures.^[1] The core principles of transfinite induction rely on the well-ordering property of ordinals, where every nonempty subset has a least element, allowing proofs by contradiction or direct verification.^[2] For a property P on a well-ordered set W, one shows P holds for the minimal element (often 0), and that if P holds for all predecessors of an element α (i.e., all β < α), then P(α) follows; this applies distinctly to successor ordinals (α = β + 1) and limit ordinals (α as the supremum of prior ordinals).^[3]^[4] No explicit base case beyond the least element is always required, as the well-ordering ensures the induction covers the entire structure.^[2] This method is fundamental in set theory for establishing results like the existence of ordinal exponentiation, the properties of transfinite arithmetic, and theorems in topology and analysis, such as the Cantor-Bendixson theorem on perfect sets.^[2]^[3] It underpins advanced constructions in modern mathematics, including the development of the Borel hierarchy and proofs involving the axiom of choice, though its reliance on well-ordering can introduce non-constructive elements.^[1]

Preliminaries

Ordinal numbers

Ordinal numbers, introduced by Georg Cantor in the late 19th century, are defined as the order types of well-ordered sets, where a well-ordered set is one in which every nonempty subset has a least element under the given ordering relation.^[5] This definition emphasizes the sequential structure imposed by the ordering, distinguishing ordinals from cardinal numbers, which quantify the size or cardinality of sets through bijections without regard to order.^[5] For finite sets, ordinal and cardinal numbers coincide, but the distinction becomes crucial for infinite sets, as different orderings of the same cardinality can yield distinct ordinals. Transfinite ordinals extend beyond the finite natural numbers, beginning with \omega, the order type of the natural numbers under the standard ordering, which is the smallest infinite ordinal.^[6] Successor ordinals follow any ordinal \alpha by adding one element after it, such as \omega + 1, which appends a single element beyond the infinite sequence of naturals. Limit ordinals, like \omega itself or \omega \cdot 2 = \omega + \omega, arise as the supremum of a sequence of smaller ordinals without an immediate predecessor. These structures allow for a hierarchy of infinities ordered by inclusion of their order types. Arithmetic operations on ordinals are defined recursively based on the order types, but they are not commutative, reflecting the sensitivity to ordering. Ordinal addition \alpha + \beta concatenates the order type of \beta after \alpha, so for example, \omega + 1 places a single element after the infinite sequence, while $1 + \omega absorbs the initial element into the infinite tail, yielding \omega.^[6] Multiplication \alpha \cdot \beta repeats the order type of \alpha \beta times, and exponentiation \alpha^\beta nests repetitions accordingly; notably, \omega \cdot 2 = \sup\{\omega + n \mid n < \omega\} = \omega + \omega, but $2 \cdot \omega = \omega. These operations preserve well-ordering but differ from cardinal arithmetic, where infinite sums and products often collapse to the maximum cardinality. Every nonzero ordinal \alpha admits a unique representation in Cantor normal form as a finite sum \alpha = \omega^{\beta_k} \cdot c_k + \cdots + \omega^{\beta_1} \cdot c_1, where \beta_k > \cdots > \beta_1 \geq 0 are ordinals, and c_i are positive finite integers (the coefficients).^[7] This form, introduced by Cantor, expresses ordinals as "polynomials" in \omega with ordinal exponents in strictly decreasing order, facilitating comparisons and computations; for instance, \omega^2 + \omega \cdot 3 + 5 is already in normal form. The uniqueness stems from the well-ordered nature of ordinals, ensuring no carrying over in the representation as in finite base expansions.

Well-ordered sets

A well-ordered set is a totally ordered set (X, \leq) such that every non-empty subset of X has a least element with respect to \leq.^[8] This property strengthens the notion of a total order, where comparability holds for every pair of distinct elements (trichotomy: for any x, y \in X, exactly one of x < y, x = y, or y < x is true), but does not require the existence of least elements in subsets.^[8] In contrast, a strict weak order is an irreflexive and transitive binary relation that may not be total, allowing incomparable elements, whereas well-orders demand totality alongside the least-element condition.^[9] The natural numbers \mathbb{N} under the usual ordering \leq form a prototypical well-ordered set, as any non-empty subset has a smallest element.^[8] The integers \mathbb{Z} under the usual ordering are not well-ordered, since the subset of negative integers \{\dots, -3, -2, -1\} lacks a least element.^[8] Similarly, \mathbb{Z} under the reverse ordering (where m \leq n if m \geq n in the usual sense) is not well-ordered, as the subset of positive integers now descends infinitely without a least element.^[8] Transfinite examples include ordinals such as \omega \cdot 2, which orders two copies of \mathbb{N} in succession: $0 < 1 < 2 < \dots < \omega < \omega + 1 < \omega + 2 < \dots.^[8] A key property of well-orders is the absence of infinite descending chains: there is no infinite sequence (x_n)_{n \in \mathbb{N}} in X such that x_{n+1} < x_n for all n.^[8] This is equivalent to the least-element condition, as any descending chain's set of elements would otherwise form a non-empty subset without a minimum.^[8] For any two well-ordered sets (A, \leq_A) and (B, \leq_B), they are comparable in the sense that either there exists an order-isomorphic embedding of A into an initial segment of B, or vice versa; this is the trichotomy theorem for well-orders.^[8] The order type of a well-ordered set, up to order-isomorphism, is labeled by an ordinal number.^[9]

Standard Induction

Finite mathematical induction

Mathematical induction is a fundamental proof technique used to establish that a given property holds for all natural numbers. Formally, let P(n) be a proposition defined for each natural number n \in \mathbb{N}, where \mathbb{N} = \{0, 1, 2, \dots\}. The principle states that if P(0) is true (the base case) and, for every n \geq 0, the truth of P(n) implies the truth of P(n+1) (the inductive step), then P(n) holds for all n \in \mathbb{N}.^[10] This principle can be proved using the well-ordering property of the natural numbers, which asserts that every nonempty subset of \mathbb{N} has a least element; \mathbb{N} is the simplest infinite well-ordered set under the usual ordering./01%3A_Introduction/1.02%3A_The_Well_Ordering_Principle_and_Mathematical_Induction) To see this, suppose the base case and inductive step hold, but P(n) fails for some n. Let S = \{ m \in \mathbb{N} \mid P(m) is false \}, which is nonempty. By well-ordering, S has a minimal element k \geq 1. Then P(k-1) holds (since k is minimal), so the inductive step implies P(k) holds, a contradiction. Thus, S is empty, and P(n) is true for all n.^[10] Alternatively, the principle follows from the least element principle, equivalent to well-ordering in the context of \mathbb{N}.^[11] A classic application is proving the formula for the sum of the first n natural numbers. Consider P(n): \sum_{i=0}^{n} i = \frac{n(n+1)}{2}. For the base case n=0, the sum is 0, matching the formula. Assume P(n) holds; then for n+1,

\sum_{i=0}^{n+1} i = \sum_{i=0}^{n} i + (n+1) = \frac{n(n+1)}{2} + (n+1) = \frac{n(n+1) + 2(n+1)}{2} = \frac{(n+1)(n+2)}{2},

so P(n+1) holds. Thus, the formula is true for all n \in \mathbb{N}.^[10] Another example involves divisibility: prove that 3 divides $4^n - 1 for all n \geq 0. Let P(n): $3 \mid (4^n - 1). For n=0, $4^0 - 1 = 0, divisible by 3. Assume P(n) holds; then for n+1,

$4^{n+1} - 1 = 4 \cdot 4^n - 1 = 4(4^n - 1) + 4 - 1 = 4(4^n - 1) + 3,

where $4(4^n - 1) is divisible by 3 (by the hypothesis and since 4 ≡ 1 mod 3), and 3 is divisible by 3, so P(n+1) holds. Thus, 3 divides $4^n - 1 for all n \geq 0./02%3A_Enumeration/06%3A_Induction_and_Recursion/6.02%3A_Basic_Induction) A variant known as strong induction strengthens the inductive hypothesis. Here, if P(0) holds and, for every n \geq 0, the truth of P(k) for all k < n implies P(n), then P(n) holds for all n \in \mathbb{N}. This is equivalent to standard induction but useful when the proof for n requires multiple prior cases.^[12] While mathematical induction is effective for properties along the successor chain of natural numbers, its reliance on this finite-step progression limits direct application to more general well-ordered structures beyond \mathbb{N}.^[10]

Generalization to infinite sets

While finite mathematical induction successfully proves properties for all natural numbers by leveraging their well-ordered structure under the standard ordering, it fails to apply directly to many infinite sets that lack this property. For instance, the integers \mathbb{Z} under the usual order are not well-ordered, as the nonempty subset of negative integers has no least element, preventing the base case or inductive step from establishing a minimal starting point. Similarly, the rational numbers \mathbb{Q} (even the positive ones) are not well-ordered; the set \{1/n \mid n \in \mathbb{N}, n \geq 1\} has no least element, so induction cannot proceed by assuming a property holds up to some point and extending it.^[13]^[14] Well-ordering resolves this limitation by ensuring every nonempty subset of the set has a least element, which underpins an inductive proof structure analogous to that on the naturals. In a well-ordered set, to prove a property P holds for all elements, one can assume P fails somewhere and derive a contradiction via the least counterexample, mirroring the finite case but applicable to infinite structures without requiring a finite "first" element in the traditional sense. This least element principle thus generalizes the foundation of induction to arbitrary well-ordered infinite sets, allowing proofs that traverse the entire order type.^[15] Extending this to transfinite contexts involves distinguishing between successor ordinals and limit ordinals in the well-ordering. A successor ordinal \alpha + 1 immediately follows \alpha, enabling a step-by-step progression similar to finite induction, where the property at \alpha + 1 builds directly on \alpha. In contrast, a limit ordinal like \omega (the order type of the naturals) has no immediate predecessor and is the supremum of all smaller ordinals, requiring the property to hold uniformly across all prior elements before applying at the limit. This bifurcation accommodates the denser structure of transfinite well-orderings, where induction must handle both discrete advances and accumulations at "infinity points."^[16] The motivation for this generalization traces to Georg Cantor's foundational work on transfinite numbers in the 1890s, where he introduced ordinals to classify well-ordered infinite sets and extended arithmetic beyond finites, highlighting the need for inductive methods that respect transfinite succession and limits. In his 1895–1897 memoir, Cantor defined well-ordered aggregates with least elements and derived ordinal types, laying the groundwork for proofs over infinite orderings without gaps or descending chains.

Principle of Transfinite Induction

Formal statement

The principle of transfinite induction applies to well-ordered sets and provides a method to prove that a property holds for every element in the set by assuming it holds for all predecessors. Formally, let (W, <) be a well-ordered set and P a property such that for every x \in W, if P(y) holds for all y < x, then P(x) holds; it follows that P(x) holds for all x \in W.< ^[2] > This statement generalizes mathematical induction to arbitrary well-orderings, where the induction step relies on the absence of infinite descending chains. For ordinals, the principle is stated in terms of the class of ordinals up to a fixed ordinal \alpha. Specifically, let P be a property on ordinals such that for every ordinal \gamma \leq \alpha, if P(\beta) holds for all \beta < \gamma, then P(\gamma) holds; then P(\beta) holds for all ordinals \beta \leq \alpha.< ^[17] > This formulation accounts for the structure of ordinals, including successor and limit cases, though the single assumption suffices due to the transitive closure of ordinals. The principle is equivalent to the least element property in well-ordered sets: if a nonempty subset S \subseteq W has the property that for every x \in S, all y < x satisfy P(y), then S must be empty, as any counterexample would violate well-ordering by having a minimal element where the induction step fails.< ^[18] > A strong variant of transfinite induction strengthens the hypothesis by assuming P(\beta) for all \beta < \gamma implies P(\gamma) directly, without needing separate cases for successors or limits, and yields the same conclusion for all elements in the well-ordered set or up to the bounding ordinal.< ^[2] >

Proof outline

The principle of transfinite induction, as formally stated, asserts that if (W, \leq) is a well-ordered set and P is a property such that for every x \in W, the assumption that P(y) holds for all y < x implies P(x), then P(x) holds for all x \in W. To prove this, proceed by contradiction. Suppose there exists some x \in W such that \neg P(x). Let S = \{x \in W \mid \neg P(x)\}. Then S is a nonempty subset of W, so by the well-ordering property, S has a least element m. For this m, every y < m satisfies y \notin S, hence P(y) holds. Thus, the antecedent of the induction hypothesis is satisfied at m, which implies P(m). But this contradicts m \in S, so S must be empty and P(x) holds for all x \in W. When W is the class of ordinal numbers, ordered by the usual < relation (or membership \in), the proof follows analogously. The class of ordinals is well-ordered, so any nonempty subclass of counterexamples has a least element m, an ordinal such that all proper initial segments \{y \mid y < m\} satisfy P, forcing P(m) by hypothesis and yielding a contradiction. This proof is non-constructive, as it depends solely on the existence of a well-ordering (and thus a least element in any nonempty subset) without providing an explicit method to compute or enumerate the elements.

Basic examples

Transfinite induction, as formally stated in the principle, allows proofs over well-ordered sets like the ordinals by verifying a base case, successor step, and limit step.^[2] One fundamental application demonstrates the countability of all ordinals less than \varepsilon_0, the smallest fixed point of the function \alpha \mapsto \omega^\alpha. To prove this, proceed by transfinite induction on \alpha < \varepsilon_0. Every such \alpha admits a unique Cantor normal form \alpha = \omega^{\beta_k} \cdot n_k + \cdots + \omega^{\beta_0} \cdot n_0, where \beta_k < \cdots < \beta_0 < \varepsilon_0, each n_i < \omega, and there are finitely many terms. The base case holds for finite ordinals, which are countable. For the successor step, if \gamma < \alpha is countable, then \alpha = \gamma + 1 adds a single element, preserving countability. For the limit step, \alpha is the union of countably many smaller ordinals (due to the finite support in the normal form and induction hypothesis on the exponents \beta_i), so |\alpha| \leq \aleph_0. Thus, by induction, all \alpha < \varepsilon_0 are countable.^[7] Another illustrative example establishes the uncountability of \omega_1, the first uncountable ordinal. Assume for contradiction that \omega_1 is countable, so there is a bijection with \mathbb{N}, or equivalently, a sequence (\alpha_n)_{n \in \mathbb{N}} enumerating all ordinals less than \omega_1. Let \beta = \sup_{n \in \mathbb{N}} \alpha_n. The set underlying \beta is the union \bigcup_{n} [\alpha_n), a countable union of countable sets (each [\alpha_n) countable as \alpha_n < \omega_1), hence countable. Thus, \beta has countable cardinality, so \beta is a countable ordinal, implying \beta < \omega_1. However, since the sequence enumerates all ordinals below \omega_1, we must have \beta = \omega_1, a contradiction. This argument relies on the fact that countable unions of countable ordinals have countable order type, which follows from transfinite recursion defining bijections to \mathbb{N}.^[2] Transfinite induction also reveals that ordinal addition is not commutative. Consider proving \omega + 1 > 1 + \omega. First, note that $1 + \omega orders a singleton followed by a copy of \omega, yielding order type \omega (every element has finitely many predecessors). In contrast, \omega + 1 appends a singleton after \omega, so the final element has infinitely many predecessors. To formalize via induction, define a property P(\alpha) for \alpha \leq \omega: in the ordinal \alpha, every element has finitely many predecessors. The base case P(0) holds (empty). For successors, if P(\beta) holds, then \beta + 1 adds an element with finitely many (those of \beta) predecessors. At the limit \omega = \sup_{n < \omega} n, by the induction hypothesis, all finite n satisfy P(n), so \omega has elements with arbitrarily many but finite predecessors. Now, \omega + 1 adds an element after this limit, which has infinitely many predecessors, violating a similar property for the extended structure. Meanwhile, $1 + \omega = \sup_{n < \omega} (1 + n) = \omega, which lacks a greatest element. Thus, \omega + 1 \neq 1 + \omega, as the former has a greatest element while the latter does not.^[19] To trace transfinite induction explicitly on a limit ordinal like \omega, consider proving that every \alpha < \omega is a finite natural number (i.e., the ordinals below \omega are exactly the finite ones). Let P(\alpha) be "\alpha is finite." The base case: P(0) holds, as 0 is finite. Successor step: if P(\beta) holds for \beta < \alpha, then \alpha = \beta + 1 adds one to a finite set, so finite. Limit step at \omega: for any \gamma < \omega, \gamma is reached by successors from 0, so by the induction hypothesis on all proper initial segments (each a finite successor chain), P(\gamma) holds; thus, all below \omega are finite, confirming \omega as the first infinite ordinal. This limit step unions the properties over the countable cofinality of \omega.^[2]

Variants and Extensions

Transfinite recursion

Transfinite recursion provides a method for defining functions on well-ordered sets by specifying the value at each element in terms of the function's values on the preceding elements. Formally, given a well-ordered set W and a class function g that assigns to each pair consisting of an initial segment of W and an element x \in W a unique value in some universe V, there exists a unique function F: W \to V such that for every x \in W, F(x) = g(F \upharpoonright \{y \in W \mid y < x\}, x), where F \upharpoonright S denotes the restriction of F to the subset S.^[17] This construction extends the familiar finite recursion to transfinite structures, ensuring the function is determined uniquely by the recursive clause.^[20] The existence and uniqueness of such a function F are guaranteed by the transfinite recursion theorem, which holds in Zermelo-Fraenkel set theory (ZF). The theorem applies more generally to well-founded set-like relations, but for ordinals or well-ordered sets, it specializes to the above form; uniqueness follows from the well-foundedness of the order via a contradiction argument assuming two distinct functions differ at a minimal point, while existence is established by iteratively approximating the function over initial segments.^[17] The proof of uniqueness relies on transfinite induction along the well-ordering of W, confirming that no inconsistencies arise in the recursive definition.^[20] A prominent application of transfinite recursion is the definition of ordinal exponentiation, which builds the operation \alpha^\beta for ordinal numbers \alpha and \beta recursively on \beta. Specifically, \alpha^0 = 1, \alpha^{\beta+1} = \alpha^\beta \cdot \alpha for successor ordinals, and for limit ordinals \lambda, \alpha^\lambda = \sup\{\alpha^\gamma \mid \gamma < \lambda\}.^[21] For the base \alpha = \omega, this yields the sequence where \omega^0 = 1, \omega^1 = \omega, \omega^2 = \omega \cdot \omega, \omega^3 = \omega^2 \cdot \omega, and so on iteratively for finite n, with \omega^\omega = \sup\{\omega^n \mid n < \omega\}, and further terms like \omega^{\omega+1} = \omega^\omega \cdot \omega, illustrating how recursion generates the hierarchy of infinite ordinals.^[21] Unlike transfinite induction, which verifies that a property holds for all elements of a well-ordered set by assuming it for predecessors and checking the current element, transfinite recursion actively constructs new mathematical objects—such as functions or sequences—by the same predecessor-based rule, thereby extending the definitional power of recursion beyond finite cases.^[17]

Induction by cases

Induction by cases is a variant of transfinite induction tailored to the recursive structure of ordinals, where proofs are divided into three distinct cases corresponding to the zero ordinal, successor ordinals, and limit ordinals.^[19] In this approach, to establish a property P(\alpha) for all ordinals \alpha, one first verifies the base case P(0). For the successor case, assuming P(\alpha) holds, one proves P(\alpha + 1). For the limit case, assuming P(\beta) holds for all \beta < \lambda where \lambda is a limit ordinal, one proves P(\lambda).^[2]^[4] This case-based method is equivalent to the standard principle of transfinite induction, which states that if P(\beta) holds for all \beta < \alpha implies P(\alpha), then P(\alpha) holds for all ordinals \alpha. The equivalence arises because every nonzero ordinal is either a successor \alpha = \beta + 1 for some \beta, in which case the successor assumption suffices using the inductive hypothesis on \beta, or a limit ordinal \lambda = \sup\{\beta \mid \beta < \lambda\}, where the limit assumption covers all predecessors.^[19]^[17] A representative example illustrates the utility of this variant in distinguishing ordinal types. Consider proving that no successor ordinal greater than 1 is additively closed, where an ordinal \alpha is additively closed if \beta + \gamma < \alpha for all \beta, \gamma < \alpha.^[22] Proceed by transfinite induction by cases on the property Q(\alpha): "if \alpha is a successor ordinal and \alpha > 1, then \alpha is not additively closed." For the base case, $0 is a limit ordinal, so Q(0) holds vacuously. For the successor case, suppose Q(\alpha) holds and consider \alpha + 1, which is a successor ordinal greater than 1. Then \alpha < \alpha + 1 and $1 < \alpha + 1 (since \alpha \geq 0 implies \alpha + 1 \geq 1, but for the implication, when \alpha \geq 1, $1 < \alpha + 1; for \alpha = 0, Q(1) holds vacuously as $1 \not> 1), but \alpha + 1 \not< \alpha + 1, so \alpha + 1 is not additively closed, establishing Q(\alpha + 1). For the limit case, let \lambda be a limit ordinal; then \lambda is not a successor, so Q(\lambda) holds vacuously. Thus, Q(\alpha) holds for all \alpha, proving the claim.^[19]^[22] This approach offers advantages in proofs involving structural properties of ordinals, as it explicitly addresses transfinite "gaps" at limit ordinals by isolating the cases, making the reasoning more intuitive than the monolithic assumption over all predecessors in the standard form.^[4] It relates briefly to transfinite recursion, which formalizes function definitions across these same ordinal cases.^[2]

Set-Theoretic Connections

Relation to the axiom of choice

Transfinite induction is a valid principle in Zermelo-Fraenkel set theory (ZF) for any well-ordered set, as its proof relies solely on the properties of well-orderings and the axioms of ZF, without requiring the axiom of choice (AC).^[23] However, AC is essential to establish the well-ordering theorem, which asserts that every set can be well-ordered; this theorem is equivalent to AC and cannot be proved in ZF alone.^[23] In the absence of AC, transfinite induction applies only to sets that admit an explicit well-ordering constructible within ZF, such as the ordinal numbers or other hereditarily well-orderable structures. This limitation restricts the method's scope, as many sets—such as the real numbers under their natural order—may not be well-orderable without invoking AC.^[23] Historically, Ernst Zermelo's 1904 proof of the well-ordering theorem introduced AC explicitly and employed transfinite recursion on the well-ordered power set of a given set M to construct a choice function that yields a well-ordering of M.^[24] In this construction, Zermelo defined a sequence of "γ-sets" recursively, selecting elements via a choice function on the complements of initial segments, thereby building up to a total well-ordering; transfinite induction ensures the process covers M exhaustively.^[24] The principle of transfinite induction does not imply AC, since it is provable in ZF for well-ordered sets, and models of ZF exist where AC fails (such as those with amorphous sets or Dedekind-finite infinite sets).^[23] Conversely, AC implies the well-ordering theorem, enabling transfinite induction to be applied to arbitrary sets by first well-ordering them.^[23]

Implications for well-ordering

The well-ordering theorem states that every set can be well-ordered, and this result is equivalent to the axiom of choice.^[25] This equivalence implies that, under the axiom of choice, any set admits a well-ordering, thereby enabling the application of transfinite induction to arbitrary sets by treating them as well-ordered structures isomorphic to ordinals.^[25] A sketch of the proof proceeds by assuming the axiom of choice and employing transfinite recursion over the cardinals to construct, for a given set X, an ordinal \alpha and a bijection between X and \alpha, which induces the desired well-ordering on X.^[26] Specifically, the recursion builds an increasing sequence of initial segments of X until exhausting the set, relying on choice to select elements at each successor step and limits. One key consequence is Hartogs' theorem, which establishes in ZF set theory alone (without the axiom of choice) that for any set S, there exists an ordinal \alpha such that no injection from \alpha into S is possible; this \alpha, known as the Hartogs number of S, guarantees the existence of aleph fixed points and larger cardinals beyond |S|.^[27] However, while Hartogs' theorem provides alephs via well-orderings of the power set without choice, achieving a well-ordering of arbitrary sets themselves requires the axiom of choice. In the framework of ZFC (ZF plus the axiom of choice), the well-ordering theorem ensures the universal applicability of transfinite induction, as every set can be well-ordered and thus subjected to inductive arguments along its ordinal-type order.^[25]

References

[1]
Transfinite Induction -- from Wolfram MathWorld
To prove various results in point-set topology, Cantor developed the first transfinite induction methods in the 1880s. Zermelo (1904) extended Cantor's method ...
[2]
[PDF] Transfinite Induction - Penn Math
This was one of the very first transfinite constructions in the history of mathematics, and was part of a failed attempt to prove the continuum hypothesis.
[3]
[PDF] Mathematical Induction, Transfinite Induction ... - Journal of Eduped
Jun 1, 2023 · Article History This article examines three types of induction methods in mathematics: mathematical induction, transfinite induction, and ...
[4]
Transfinite induction - Tricki
Transfinite induction is similar to induction but the well-ordered set \mathbb{N} is replaced by larger ordinals. This article tells you what you need to ...Missing: history | Show results with:history
[5]
[PDF] CARDINAL AND ORDINAL NUMBERS Contents 1. The Natural ...
Abstract. This paper will present a brief set-theoretic construction of the natural numbers before discussing in detail the ordinal and cardinal numbers.
[6]
English translation of Cantor's Grundlagen - Logic
An online English translation of Cantor's Grundlagen (Foundations of a theory of sets): Part 5 of Über unendliche lineare Punktmannig-faltigkeiten.
[7]
[PDF] On Cantor's normal form theorem and algebraic number theory
Jun 2, 2018 · Cantor introduced his normal form theorem as an ordinal polyno- mial for the countable ordinals of the second class up to the first epsilon.
[8]
[PDF] Elements of Set Theory
Enderton, Herbert, B. Elements of Set Theory. Bibliography: p. Includes index ... numbers are exactly the transitive sets that are well ordered by epsilon:.
[9]
245B, Notes 7: Well-ordered sets, ordinals, and Zorn's lemma ...
Jan 28, 2009 · . But a deep theorem of Solovay gives a model of set theory (without the axiom of choice) in which every set of reals is measurable.Missing: textbook | Show results with:textbook
[10]
https://math.libretexts.org/Bookshelves/Analysis/Introduction_to_Mathematical_Analysis_I_(Lafferriere_Lafferriere_and_Nguyen)/01%3A_Tools_for_Analysis/1.03%3A_The_Natural_Numbers_and_Mathematical_Induction
[11]
[PDF] Induction and the Well Ordering Principle - People | MIT CSAIL
Use a proof by contradiction and assume that C is nonempty. • By the Well Ordering Principle, there will be a smallest element, n, in C. • Reach a contradiction ...
[12]
2.6: Strong Mathematical Induction
### Definition and Explanation of Strong Mathematical Induction
[13]
[PDF] 6.042J Chapter 3: Induction - MIT OpenCourseWare
And it requires a set of nonnegative integers—it's false for the set of negative integers and also false for some sets of nonnegative rationals—for example, ...
[14]
[PDF] Notes 3 - People @EECS
For example, neither the integers nor even the positive rationals have a smallest element. The well-ordering principle not only underlies the induction ...<|separator|>
[15]
3.7: The Well-Ordering Principle
### Summary of Well-Ordering Principle and Relation to Induction
[16]
[PDF] ordinals.1 Successor and Limit Ordinals - Open Logic Project Builds
For any ordinal α, its successor is α+ = α ∪ {α}. We say that α is a successor ordinal if β+ = α for some ordinal β. We say that α is a limit ordinal ...
[17]
[PDF] Set Theory (MATH 6730) Ordinals. Transfinite Induction and Recursion
Transfinite Induction Theorem 3.3. Let A be an ordinal or On. For every subclass B of A, if • 0 ∈ B, • for all successor ordinals α +0 1 ∈ A such that α ∈ B we ...
[18]
[PDF] Supplementary Lecture A The Knaster–Tarski Theorem
The transfinite induction principle is a method of establishing that a partic- ular property is true of all ordinals (or of all elements of a class of objects.
[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]
transfinite recursion - PlanetMath
Mar 22, 2013 · Transfinite recursion, roughly speaking, is a statement about the ability to define a function recursively using transfinite induction . In its ...
[21]
[PDF] ord-arithmetic.1 Ordinal Exponentiation - Open Logic Project Builds
So instead, we'll offer the definition of ordinal exponen- tiation just by transfinite recursion, i.e.: Definition ord-arithmetic.1. sth:ord-arithmetic:expo ...
[22]
[PDF] arXiv:1911.07576v1 [math.LO] 18 Nov 2019
Nov 18, 2019 · Let α be an ordinal. We say that α is additively closed if the sum of two ordinals less then α is less than α. Similarly, α is multiplicatively ...
[23]
The Axiom of Choice - Stanford Encyclopedia of Philosophy
Jan 8, 2008 · The principle of set theory known as the Axiom of Choice has been hailed as “probably the most interesting and, in spite of its late appearance, the most ...
[24]
Zermelo's Axiomatization of Set Theory
Jul 2, 2013 · Zermelo's approach to the well-ordering problem took place in three stages. He published a proof of WOT in 1904 (Zermelo 1904, an extract from a ...
[25]
Zermelo's well-ordering theorem - Planetmath
Mar 22, 2013 · Zermelo's well-ordering theorem. If X X is any set whatsoever, then there exists a well-ordering of X X . The well-ordering theorem is ...
[26]
proof of Zermelo's well-ordering theorem - PlanetMath.org
Mar 22, 2013 · , it is a bijection between α and X , and therefore establishes a well-ordering of X by x<Xy↔i−1(x)<i−1(y) x < X y ↔ i - 1 ⁢ ( x ) < i - 1 ⁢ . ...
[27]
Hartogs number - PlanetMath
Mar 22, 2013 · ... deduce? In 1915, Hartogs proved the following: Theorem 1. Given any set A A , there is an ordinal α α not embeddable in A A . Proof.