Transfinite induction

Encyclopedia : T : TR : TRA : Transfinite induction

Transfinite induction is an extension of mathematical induction to (large) well-ordered sets, for instance to sets of ordinals or cardinals. It may be regarded as one of three forms of mathematical induction.

Contents

1 Transfinite induction
2 Transfinite recursion
3 Relationship to AC
4 See also

Transfinite induction

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 α < β).

Limit case: Prove that for any limit ordinal λ, P(λ) follows from [P(α) for all α < λ].

Notice that the second and third cases are identical except for the type of ordinal considered. They do not formally need to be proved separately, but in practice the proofs are commonly so different that it is standard to present them separately.

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 three things:

What A₀ is
How to determine A_α+1 from A_α (or possibly from the entire sequence up to A_α)
For a limit ordinal λ, how to determine A_λ from the sequence of A_α for α < λ

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 yRx must be a set.)

Relationship to AC

There is a popular misconception that transfinite induction, or transfinite recursion, or both, require the axiom of choice (AC). This is incorrect. However it is very often the case that proofs or constructions using the technique do use AC.

For example, consider the following construction of the Vitali set: First, well-order the reals, say into a sequence <r_{α_{| α, where c is the cardinality of the continuum. Let v₀ equal r₀. Then let v₁ equal r_α1, where α1 is least such that r_α1 − v₀ is not 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 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.

Transfinite induction

Transfinite induction

Transfinite recursion

Relationship to AC

See also