Transfinite induction

HomePage | Recent changes | View source | Discuss this page | Page history | Log in |

Printable version | Disclaimers | Privacy policy

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.

If you are trying to prove that a property P holds for all ordinals then you can apply transfinite induction: you need only prove that P(0) holds true and that for any ordinal b > 0, if P(a) is true for all ordinals a < b then P(b) is true as well. This latter part is often broken down into two cases: the case for non-limit ordinals (ordinals which have an immediate predecessor), where normal induction can be applied (you only need to 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.