Transfinite induction
From Wikipedia, the free encyclopedia.
Printable version | Pages that link here
66.28.250.171
Log in | Help
[Main Page]
Main Page | Recent Changes | Edit this page | History | Random Page | Special Pages

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.

Main Page
Recent Changes
Watch page links
Edit this page
History
Upload files
Statistics
New pages
Orphans
Most wanted
Most popular
Random Page
Stub articles
Long articles
List users
Bug reports
July 10, 2002
Talk
This page has been accessed 452 times. Other namespaces : Talk
Last edited: Monday, February 25, 2002, 15:51 (diff)
    Validate this page