home | alphabetical index | |||||

## Transfinite inductionTransfinite 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.
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. | |||||

copyright © 2004 FactsAbout.com |