TOPICS
Search

Transfinite Induction

Transfinite induction, like regular induction, is used to show a property P(n) holds for all numbers n. The essential difference is that regular induction is restricted to the natural numbers Z^*, which are precisely the finite ordinal numbers. The normal inductive step of deriving P(n+1) from P(n) can fail due to limit ordinals.

Let A be a well ordered set and let P(x) be a proposition with domain A. A proof by transfinite induction uses the following steps (Gleason 1991, Hajnal 1999):

1. Demonstrate P(0) is true.

2. Assume P(b) is true for all b<a.

3. Prove P(a), using the assumption in (2).

4. Then P(a) is true for all a in A.

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).

See also

Gödel's First Incompleteness Theorem, Gödel's Second Incompleteness Theorem, Induction, Principle of Mathematical Induction, Principle of Strong Induction, Principle of Weak Induction, Z-*

Portions of this entry contributed by Jonathan Emerson

Portions of this entry contributed by Mark Lezama

Explore with Wolfram|Alpha

References

Beachy, J. and Bruce, J. W. (Eds.). Introductory Lectures on Rings and Modules Cambridge, England: Cambridge University Press, p. 212, 1999.Gleason, A. M. Fundamentals of Abstract Analysis Natick, MA: A K Peters, p. 82, 1991.Grattan-Guinness, I. The Search for Mathematical Roots, 1870-1940. Princeton, NJ: Princeton University Press, p. 137, 2001.Hajnal, A.; Hamburger, P.; Bruce, J. W. (Eds.). Set Theory. Cambridge, England: Cambridge University Press, p. 66, 1999.Johnstone, P. T. Notes on Logic and Set Theory. Cambridge, England: Cambridge University Press, p. 78, 1987.Reid, M. and Bruce, J. W. (Eds.). Undergraduate Commutative Algebra. Cambridge, England: Cambridge University Press, p. 25, 1995.Séroul, R. "Reasoning by Induction." §2.14 in Programming for Mathematicians. Berlin: Springer-Verlag, pp. 22-25, 2000.

Referenced on Wolfram|Alpha

Transfinite Induction

Cite this as:

Emerson, Jonathan; Lezama, Mark; and Weisstein, Eric W. "Transfinite Induction." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/TransfiniteInduction.html

Subject classifications