Transfinite induction
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.
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.