Transfinite induction
Encyclopedia
Transfinite induction is an extension of mathematical induction
to well-ordered sets
, for instance to sets of ordinal number
s or cardinal number
s.
defined for all ordinals α. Suppose that whenever P(β) is true for all β < α, then P(α) is also true (including the case that P(0) is true given the vacuously true statement that P(α) is true for all
). Then transfinite induction tells us that P is true for all ordinals.
That is, if P(α) is true whenever P(β) is true for all β < α, then P(α) is true for all α. Or, more practically: in order to prove a property P for all ordinals α, one can assume that it is already known for all smaller β < α.
Usually the proof is broken down into three cases:
Notice that the second and third case are identical except for the type of ordinal considered. They do not formally need to be proven separately, but in practice the proofs are typically so different as to require separate presentations.
More formally, we can state the Transfinite Recursion Theorem as follows. Given a class function G: V → V, there exists a unique transfinite sequence F: Ord → V (where Ord is the class of all ordinals) such that
As in the case of induction, we may treat different types of ordinals separately: another formulation of transfinite recursion is that 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 proven 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; that is, for any x, the collection of all y such that y R x must be a set.)
The following construction of the Vitali set
shows one way that the axiom of choice can be used in a proof by transfinite induction:
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.
Mathematical induction
Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers...
to well-ordered sets
Well-order
In mathematics, a well-order relation on a set S is a strict total order on S with the property that every non-empty subset of S has a least element in this ordering. Equivalently, a well-ordering is a well-founded strict total order...
, for instance to sets of ordinal number
Ordinal number
In set theory, an ordinal number, or just ordinal, is the order type of a well-ordered set. They are usually identified with hereditarily transitive sets. Ordinals are an extension of the natural numbers different from integers and from cardinals...
s or cardinal number
Cardinal number
In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality of sets. The cardinality of a finite set is a natural number – the number of elements in the set. The transfinite cardinal numbers describe the sizes of infinite...
s.
Transfinite induction
Let P(α) be a propertyProperty (philosophy)
In modern philosophy, logic, and mathematics a property is an attribute of an object; a red object is said to have the property of redness. The property may be considered a form of object in its own right, able to possess other properties. A property however differs from individual objects in that...
defined for all ordinals α. Suppose that whenever P(β) is true for all β < α, then P(α) is also true (including the case that P(0) is true given the vacuously true statement that P(α) is true for all
). Then transfinite induction tells us that P is true for all ordinals.That is, if P(α) is true whenever P(β) is true for all β < α, then P(α) is true for all α. Or, more practically: in order to prove a property P for all ordinals α, one can assume that it is already known for all smaller β < α.
Usually the proof is broken down into three cases:
- Zero case: Prove that P(0) is true.
- Successor case: Prove that for any successor ordinalSuccessor ordinalIn 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...
α+1, P(α+1) follows from P(α) (and, if necessary, P(β) for all β < α).
- Limit case: Prove that for any limit ordinal λ, P(λ) follows from [P(β) for all β < λ].
Notice that the second and third case are identical except for the type of ordinal considered. They do not formally need to be proven separately, but in practice the proofs are typically so different as to require separate presentations.
Transfinite recursion
Transfinite recursion is a method of constructing or defining something and is closely related to the concept of transfinite induction. As an example, a sequence of sets Aα is defined for every ordinal α, by specifying how to determine Aα from the sequence of Aβ for β < α.More formally, we can state the Transfinite Recursion Theorem as follows. Given a class function G: V → V, there exists a unique transfinite sequence F: Ord → V (where Ord is the class of all ordinals) such that
- F(α) = G(F
α) for all ordinals α.
As in the case of induction, we may treat different types of ordinals separately: another formulation of transfinite recursion is that given a set g1, and class functions G2, G3, there exists a unique function F: Ord → V such that
- F(0) = g1,
- F(α + 1) = G2(F(α)), for all α ∈ Ord,
- F(λ) = G3(F
λ), for all limit λ ≠ 0.
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 proven using transfinite induction.
More generally, one can define objects by transfinite recursion on any well-founded relation
Well-founded relation
In mathematics, a binary relation, R, is well-founded on a class X if and only if every non-empty subset of X has a minimal element with respect to R; that is, for every non-empty subset S of X, there is an element m of S such that for every element s of S, the pair is not in R:\forall S...
R. (R need not even be a set; it can be a proper class, provided it is a set-like relation; that is, for any x, the collection of all y such that y R x must be 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. 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
Vitali set
In mathematics, a Vitali set is an elementary example of a set of real numbers that is not Lebesgue measurable, found by . The Vitali theorem is the existence theorem that there are such sets. There are uncountably many Vitali sets, and their existence is proven on the assumption of the axiom of...
shows one way that the axiom of choice can be used in a proof by transfinite induction:
- First, well-orderWell-orderIn mathematics, a well-order relation on a set S is a strict total order on S with the property that every non-empty subset of S has a least element in this ordering. Equivalently, a well-ordering is a well-founded strict total order...
the real numberReal numberIn mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
s, giving a sequence
, where c is the cardinality of the continuumCardinality of the continuumIn set theory, the cardinality of the continuum is the cardinality or “size” of the set of real numbers \mathbb R, sometimes called the continuum. It is an infinite cardinal number and is denoted by |\mathbb R| or \mathfrak c ....
. Let v0 equal r0. Then let v1 equal rα1, where α1 is least such that rα1 − v0 is not a rational numberRational numberIn mathematics, a rational number is any number that can be expressed as the quotient or fraction a/b of two integers, with the denominator b not equal to zero. Since b may be equal to 1, every integer is a rational number...
. Continue; at each step choose 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
Countable set
In mathematics, a countable set is a set with the same cardinality as some subset of the set of natural numbers. A set that is not countable is called uncountable. The term was originated by Georg Cantor...
length, the weaker axiom of dependent choice
Axiom of dependent choice
In mathematics, the axiom of dependent choices, denoted DC, is a weak form of the axiom of choice which is still sufficient to develop most of real analysis...
is sufficient. Because there are models of Zermelo–Fraenkel set theory
Zermelo–Fraenkel set theory
In mathematics, Zermelo–Fraenkel set theory with the axiom of choice, named after mathematicians Ernst Zermelo and Abraham Fraenkel and commonly abbreviated ZFC, is one of several axiomatic systems that were proposed in the early twentieth century to formulate a theory of sets without the paradoxes...
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.