Transfinite induction

Transfinite induction is an extension of mathematical induction to well-ordered sets, for instance to sets of ordinals or cardinals. Mathematical induction is a method of Mathematical proof typically used to establish that a given statement is true of all Natural numbers It is done by proving that In Mathematics, a well-order relation (or well-ordering) on a set S is a Total order on S with the property that every This article describes cardinal numbers in mathematics For cardinals in linguistics see Names of numbers in English.

1 Transfinite induction
2 Transfinite recursion
3 Relationship to the axiom of choice
4 See also

Transfinite induction

Let P(α) be a property defined for all ordinals α. In modern Philosophy, Mathematics, and Logic, a property is an Attribute of an object; thus a red object is said to have the property Suppose whenever for all β < α, P(β) is true, then P(α) is also true. 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 ordinal β+1, P(β+1) follows from P(β) (and, if necessary, P(α) for all α < β). When defining the ordinal numbers, an absolutely fundamental operation that we can perform on them is a successor operation S to get the next higher one

Limit case: Prove that for any limit ordinal λ, P(λ) follows from [P(α) for all α < λ]. A limit ordinal is an Ordinal number which is neither zero nor a Successor ordinal.

Notice that the second and third case are identical except for the type of ordinal considered. They do not formally need to be proved 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 $\upharpoonright$ α) for all ordinals α. In Set theory, an ordinal number, or just ordinal, is the Order type of a Well-ordered set.

As in the case of induction, we may treat different types of ordinals separately: another formulation of transfinite recursion is that given a set g₁, and class functions G₂, G₃, there exists a unique function F: Ord → V such that

F(0) = g₁,
F(α + 1) = G₂(F(α)), for all α ∈ Ord,
F(λ) = G₃(F $\upharpoonright$ λ), for all limit λ ≠ 0.

Note that we require the domains of G₂, G₃ 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. In Mathematics, a Binary relation, R, is well-founded (or wellfounded) on a class X if and only if every non- empty (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. In Set theory and its applications throughout Mathematics, a class is a collection of sets (or sometimes other mathematical objects that can be unambiguously In Mathematics, a binary relation (or a dyadic or 2-place relation) is an arbitrary association of elements within a set or with elements of )

Relationship to the axiom of choice

There is a popular misconception that transfinite induction, or transfinite recursion, or both, require the axiom of choice (AC). In Mathematics, the axiom of choice, or AC, is an Axiom of Set theory. This is incorrect. Transfinite induction can be applied to any well-ordered set. However, frequently proofs or constructions using transfinite induction also use the axiom of choice to well-order a set. In Mathematics, the axiom of choice, or AC, is an Axiom of Set theory.

For example, consider the following construction of the Vitali set: First, well-order the reals, say into a sequence $\langle r_{\alpha} | \alpha < c \rangle$ , where c is the cardinality of the continuum. In Mathematics, a Vitali set is an elementary example of a set of Real numbers that is not Lebesgue measurable. In Mathematics, a well-order relation (or well-ordering) on a set S is a Total order on S with the property that every In Mathematics, the real numbers may be described informally in several different ways In Mathematics, the cardinality of the continuum, sometimes also called the power of the continuum, is the size ( Cardinality) of the set of Let v₀ equal r₀. Then let v₁ equal r_α₁, where α₁ is least such that r_α₁ − v₀ is not a rational number. In Mathematics, a rational number is a number which can be expressed as a Ratio of two Integers Non-integer rational numbers (commonly called fractions 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 AC in a blatant way at the very beginning, by well-ordering the reals. Other uses are more subtle. For example, frequently a construction by transfinite recursion 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 it is possible to meet 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 AC to choose one such at each step. For inductions/recursions of countable length, the weaker axiom of dependent choice, DC, is sufficient. In Mathematics, the axiom of dependent choices, denoted DC, is a weak form of the Axiom of choice (AC which is still sufficient to develop most of

Contents