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.
Referenced By
Induction (disambiguation) | List of mathematical logic topics | List of mathematical topics (S-U)
|
