Transfinite induction
From Exampleproblems
Transfinite induction is the proof technique of mathematical induction when applied to (large) well-ordered sets, for instance to sets of ordinals or cardinals, or even to the class of all ordinals. It may be regarded as one of three forms of mathematical induction.
To prove that a property P holds of all ordinals, one applies transfinite induction as follows:
- Prove that P(0) holds true; and
- prove that for any ordinal b, if P(a) is true for all ordinals a < b then P(b) is true as well.
The latter step is often broken down into two cases: the case for successor ordinals (ordinals which have an immediate predecessor), where the usual inductive approach can be applied (show that P(a) implies P(a + 1)), and the case for limit ordinals, which have no predecessor, and thus cannot be handled by such an argument.
Typically, the case for limit ordinals is approached by noting that a limit ordinal b is (by definition) the supremum of all ordinals a < b and using this fact to prove P(b) assuming that P(a) holds true for all a < b.
The first step above is actually redundant. If P(b) follows from the truth of P(a) for all a < b, then it is simply a special case to say that P(0) is true, since it is vacuously true that P(a) holds for all a < 0.
Transfinite recursion
Transfinite recursion is a notion closely related to transfinite induction, but whereas the latter is a method of proof, the former is a method of definition or construction. In the simple form, indexed by ordinals, one defines a sequence of sets--say, Aα for every ordinal α, or perhaps every α less than some bound γ--by specifying three things:
- What A0 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 α < λ
(Note that there's not much formal difference between the second and third clauses, but in practice they are so often different that it is useful to present them separately.)
More generally, one can define objects by transfinite recursion on any wellfounded 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. 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, wellorder the reals, say into a sequence <rα | α<c >, where c is 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 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 wellordering 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.
