Transfinite inductionTransfinite induction
is the proof technique of mathematical induction
when applied to (large) well-ordered sets
, for instance to sets of ordinals
, or even to the class
of all ordinals. It may be regarded as one of three forms of mathematical induction
If you are trying to prove that a property P holds for all ordinals then you can apply transfinite induction:
- Prove that P(0) holds true; and
- 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 non-limit ordinals (ordinals which have an immediate predecessor), where the usual inductive approach can be applied (show that P(b) implies
P(b+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 union 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(b) holds for all b < 0.