Transfinite induction

Last updated
Representation of the ordinal numbers up to
{\displaystyle \omega ^{\omega }}
. Each turn of the spiral represents one power of
{\displaystyle \omega }
. Transfinite induction requires proving a base case (used for 0), a successor case (used for those ordinals which have a predecessor), and a limit case (used for ordinals which don't have a predecessor). Omega-exp-omega-labeled.svg
Representation of the ordinal numbers up to . Each turn of the spiral represents one power of . Transfinite induction requires proving a base case (used for 0), a successor case (used for those ordinals which have a predecessor), and a limit case (used for ordinals which don't have a predecessor).

Transfinite induction is an extension of mathematical induction to well-ordered sets, for example to sets of ordinal numbers or cardinal numbers. Its correctness is a theorem of ZFC. [1]


Induction by cases

Let be a property defined for all ordinals . Suppose that whenever is true for all , then is also true. [2] Then transfinite induction tells us that is true for all ordinals.

Usually the proof is broken down into three cases:

All three cases are identical except for the type of ordinal considered. They do not formally need to be considered separately, but in practice the proofs are typically so different as to require separate presentations. Zero is sometimes considered a limit ordinal and then may sometimes be treated in proofs in the same case as limit ordinals.

Transfinite recursion

Transfinite recursion is similar to transfinite induction; however, instead of proving that something holds for all ordinal numbers, we construct a sequence of objects, one for each ordinal.

As an example, a basis for a (possibly infinite-dimensional) vector space can be created by starting with the empty set and for each ordinal α > 0 choosing a vector that is not in the span of the vectors . This process stops when no vector can be chosen.

More formally, we can state the Transfinite Recursion Theorem as follows:

Transfinite Recursion Theorem (version 1). Given a class function [3] G: VV (where V is the class of all sets), there exists a unique transfinite sequence F: Ord → V (where Ord is the class of all ordinals) such that

for all ordinals α, where denotes the restriction of F's domain to ordinals <α.

As in the case of induction, we may treat different types of ordinals separately: another formulation of transfinite recursion is the following:

Transfinite Recursion Theorem (version 2). Given a set g1, and class functions G2, G3, there exists a unique function F: Ord → V such that

Note that we require the domains of G2, G3 to be broad enough to make the above properties meaningful. The uniqueness of the sequence satisfying these properties can be proved using transfinite induction.

More generally, one can define objects by transfinite recursion on any well-founded relation R. (R need not even be a set; it can be a proper class, provided it is a set-like relation; i.e. for any x, the collection of all y such that yRx is a set.)

Relationship to the axiom of choice

Proofs or constructions using induction and recursion often use the axiom of choice to produce a well-ordered relation that can be treated by transfinite induction. However, if the relation in question is already well-ordered, one can often use transfinite induction without invoking the axiom of choice. [4] For example, many results about Borel sets are proved by transfinite induction on the ordinal rank of the set; these ranks are already well-ordered, so the axiom of choice is not needed to well-order them.

The following construction of the Vitali set shows one way that the axiom of choice can be used in a proof by transfinite induction:

First, well-order the real numbers (this is where the axiom of choice enters via the well-ordering theorem), giving a sequence , where β is an ordinal with the cardinality of the continuum. Let v0 equal r0. Then let v1 equal rα1, where α1 is least such that rα1  v0 is not a rational number. Continue; at each step use the least real from the r sequence that does not have a rational difference with any element thus far constructed in the v sequence. Continue until all the reals in the r sequence are exhausted. The final v sequence will enumerate the Vitali set.

The above argument uses the axiom of choice in an essential way at the very beginning, in order to well-order the reals. After that step, the axiom of choice is not used again.

Other uses of the axiom of choice are more subtle. For example, a construction by transfinite recursion frequently will not specify a unique value for Aα+1, given the sequence up to α, but will specify only a condition that Aα+1 must satisfy, and argue that there is at least one set satisfying this condition. If it is not possible to define a unique example of such a set at each stage, then it may be necessary to invoke (some form of) the axiom of choice to select one such at each step. For inductions and recursions of countable length, the weaker axiom of dependent choice is sufficient. Because there are models of Zermelo–Fraenkel set theory of interest to set theorists that satisfy the axiom of dependent choice but not the full axiom of choice, the knowledge that a particular proof only requires dependent choice can be useful.

See also


  1. J. Schlöder, Ordinal Arithmetic. Accessed 2022-03-24.
  2. It is not necessary here to assume separately that is true. As there is no less than 0, it is vacuously true that for all , is true.
  3. A class function is a rule (specifically, a logical formula) assigning each element in the lefthand class to an element in the righthand class. It is not a function because its domain and codomain are not sets.
  4. In fact, the domain of the relation does not even need to be a set. It can be a proper class, provided that the relation R is set-like: for any x, the collection of all y such that y R x must be a set.

Related Research Articles

In mathematics, specifically set theory, the continuum hypothesis is a hypothesis about the possible sizes of infinite sets. It states that

there is no set whose cardinality is strictly between that of the integers and the real numbers,

In mathematics, a Mahlo cardinal is a certain kind of large cardinal number. Mahlo cardinals were first described by Paul Mahlo. As with all large cardinals, none of these varieties of Mahlo cardinals can be proven to exist by ZFC.

In programming language theory and proof theory, the Curry–Howard correspondence is the direct relationship between computer programs and mathematical proofs.

<span class="mw-page-title-main">Aleph number</span> Infinite cardinal number

In mathematics, particularly in set theory, the aleph numbers are a sequence of numbers used to represent the cardinality of infinite sets that can be well-ordered. They were introduced by the mathematician Georg Cantor and are named after the symbol he used to denote them, the Hebrew letter aleph.

In mathematics, in set theory, the constructible universe, denoted by , is a particular class of sets that can be described entirely in terms of simpler sets. is the union of the constructible hierarchy. It was introduced by Kurt Gödel in his 1938 paper "The Consistency of the Axiom of Choice and of the Generalized Continuum-Hypothesis". In this paper, he proved that the constructible universe is an inner model of ZF set theory, and also that the axiom of choice and the generalized continuum hypothesis are true in the constructible universe. This shows that both propositions are consistent with the basic axioms of set theory, if ZF itself is consistent. Since many other theorems only hold in systems in which one or both of the propositions is true, their consistency is an important result.

In set theory, one can define a successor operation on cardinal numbers in a similar way to the successor operation on the ordinal numbers. The cardinal successor coincides with the ordinal successor for finite cardinals, but in the infinite case they diverge because every infinite ordinal and its successor have the same cardinality. Using the von Neumann cardinal assignment and the axiom of choice (AC), this successor operation is easy to define: for a cardinal number κ we have

In set theory, the successor of an ordinal number α is the smallest ordinal number greater than α. An ordinal number that is a successor is called a successor ordinal. The ordinals 1, 2, and 3 are the first three successor ordinals and the ordinals ω+1, ω+2 and ω+3 are the first three infinite successor ordinals.

In mathematics, particularly in set theory, the beth numbers are a certain sequence of infinite cardinal numbers, conventionally written , where is the second Hebrew letter (beth). The beth numbers are related to the aleph numbers, but unless the generalized continuum hypothesis is true, there are numbers indexed by that are not indexed by .

The fixed-point lemma for normal functions is a basic result in axiomatic set theory stating that any normal function has arbitrarily large fixed points. It was first proved by Oswald Veblen in 1908.

In set theory and related branches of mathematics, the von Neumann universe, or von Neumann hierarchy of sets, denoted by V, is the class of hereditary well-founded sets. This collection, which is formalized by Zermelo–Fraenkel set theory (ZFC), is often used to provide an interpretation or motivation of the axioms of ZFC. The concept is named after John von Neumann, although it was first published by Ernst Zermelo in 1930.

In mathematical logic, New Foundations (NF) is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica. Quine first proposed NF in a 1937 article titled "New Foundations for Mathematical Logic"; hence the name. Much of this entry discusses NF with urelements (NFU), an important variant of NF due to Jensen and clarified by Holmes. In 1940 and in a revision in 1951, Quine introduced an extension of NF sometimes called "Mathematical Logic" or "ML", that included proper classes as well as sets.

In the mathematical field of set theory, ordinal arithmetic describes the three usual operations on ordinal numbers: addition, multiplication, and exponentiation. Each can be defined in essentially two different ways: either by constructing an explicit well-ordered set that represents the result of the operation or by using transfinite recursion. Cantor normal form provides a standardized way of writing ordinals. In addition to these usual ordinal operations, there are also the "natural" arithmetic of ordinals and the nimber operations.

In set theory, a subset of a Polish space is ∞-Borel if it can be obtained by starting with the open subsets of , and transfinitely iterating the operations of complementation and wellordered union. This concept is usually considered without the assumption of the axiom of choice, which means that the ∞-Borel sets may fail to be closed under wellordered union; see below.

In mathematics, specifically in axiomatic set theory, a Hartogs number is an ordinal number associated with a set. In particular, if X is any set, then the Hartogs number of X is the least ordinal α such that there is no injection from α into X. If X can be well-ordered then the cardinal number of α is a minimal cardinal greater than that of X. If X cannot be well-ordered then there cannot be an injection from X to α. However, the cardinal number of α is still a minimal cardinal not less than or equal to the cardinality of X. The map taking X to α is sometimes called Hartogs's function. This mapping is used to construct the aleph numbers, which are all the cardinal numbers of infinite well-orderable sets.

In mathematics, the epsilon numbers are a collection of transfinite numbers whose defining property is that they are fixed points of an exponential map. Consequently, they are not reachable from 0 via a finite series of applications of the chosen exponential map and of "weaker" operations like addition and multiplication. The original epsilon numbers were introduced by Georg Cantor in the context of ordinal arithmetic; they are the ordinal numbers ε that satisfy the equation

In the mathematical discipline of set theory, there are many ways of describing specific countable ordinals. The smallest ones can be usefully and non-circularly expressed in terms of their Cantor normal forms. Beyond that, many ordinals of relevance to proof theory still have computable ordinal notations. However, it is not possible to decide effectively whether a given putative ordinal notation is a notation or not ; various more-concrete ways of defining ordinals that definitely have notations are available.

<span class="mw-page-title-main">Axiom of limitation of size</span>

In set theory, the axiom of limitation of size was proposed by John von Neumann in his 1925 axiom system for sets and classes. It formalizes the limitation of size principle, which avoids the paradoxes encountered in earlier formulations of set theory by recognizing that some classes are too big to be sets. Von Neumann realized that the paradoxes are caused by permitting these big classes to be members of a class. A class that is a member of a class is a set; a class that is not a set is a proper class. Every class is a subclass of V, the class of all sets. The axiom of limitation of size says that a class is a set if and only if it is smaller than V—that is, there is no function mapping it onto V. Usually, this axiom is stated in the equivalent form: A class is a proper class if and only if there is a function that maps it onto V.

In proof theory, ordinal analysis assigns ordinals to mathematical theories as a measure of their strength. If theories have the same proof-theoretic ordinal they are often equiconsistent, and if one theory has a larger proof-theoretic ordinal than another it can often prove the consistency of the second theory.

<span class="mw-page-title-main">Ordinal number</span> Generalization of "n-th" to infinite cases

In set theory, an ordinal number, or ordinal, is a generalization of ordinal numerals aimed to extend enumeration to infinite sets.

This is a glossary of set theory.