[Home]Transfinite induction

HomePage | Recent Changes | Preferences

Showing revision 7
Difference (from revision 7 to revision 7) (minor diff, author diff)
(The revisions are identical or unavailable.)
Transfinite 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.

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.


HomePage | Recent Changes | Preferences
This page is read-only | View other revisions | View current revision
Edited November 5, 2001 3:04 am by The Anome (diff)
Search: