Transfinite induction, like regular induction, is used to show a property holds for all numbers . The essential difference is that regular induction is restricted to the natural numbers , which are precisely the finite ordinal numbers. The normal inductive step of deriving from can fail due to limit ordinals.
Let be a well ordered set and let be a proposition with domain . A proof by transfinite induction uses the following steps (Gleason 1991, Hajnal 1999):
1. Demonstrate is true.
2. Assume is true for all .
3. Prove , using the assumption in (2).
4. Then is true for all .
To prove various results in point-set topology, Cantor developed the first transfinite induction methods in the 1880s. Zermelo (1904) extended Cantor's method with a "proof that every set can be well-ordered," which became the axiom of choice or Zorn's Lemma (Johnstone 1987). Transfinite induction and Zorn's lemma are often used interchangeably (Reid 1995), or are strongly linked (Beachy 1999). Hausdorff (1906) was the first to explicitly name transfinite induction (Grattan-Guinness 2001).