Transfinite induction

English

Noun

1. Template:Lb An extension of mathematical induction to well-ordered sets of transfinite cardinality, such as sets of ordinal numbers or cardinal numbers.
   • Template:Quote-book
   • 1970 [Addison-Wesley], Howard DeLong, A Profile of Mathematical Logic, Dover, 2004, page 218,

     Just what kinds of transfinite inductions are to be considered finitary is debatable. Transfinite induction up to an arbitrary ordinal is certainly not finitary. However, it can be shown that certain transfinite inductions are reducible to ordinary mathematical inductions. For example, induction up to ${\omega }^{\omega }$ is reducible to ordinary induction. Gentzen in his proof used transfinite induction up to ${\epsilon }_0$.

   • Template:Quote-book

Usage notes

• Suppose $P(\alpha )$ is a property defined for any ordinal number $\alpha$, and that whenever $P(\beta )$ is true for all $\beta <\alpha$, then $P(\alpha )$ is also true. Then transfinite induction tells us that $P$ is true for all ordinals.
• A transfinite induction proof is typically broken down into three cases:
  • Zero case: $P(0)$.
  • Successor case: For any ordinal number $\alpha +1$ that is the successor of some ordinal $\alpha$, $P(\alpha )⟹P(\alpha +1)$. (Alternatively, if necessary, $[\mathrm{\forall }\beta <\alpha ,P(\beta )]⟹P(\alpha )$.)
  • Limit case: For any limit ordinal (non-successor ordinal) $\lambda$, $[\mathrm{\forall }\beta <\lambda ,P(\beta )]⟹P(\lambda )$.
• Some proofs involve first using the (historically controversial) axiom of choice to construct a well-ordered relation (enabling transfinite induction over its equivalence classes). If a well-ordered relation already exists, this step is unnecessary.
• For many purposes, transfinite induction is used only up to the smallest epsilon number, ${\epsilon }_0$.

Synonyms

• Template:Sense Template:L, Template:L, Template:L

Hyponyms

• Template:Sense Template:L, Template:L

Related terms

• Template:L
• Template:L

Translations

• German: Template:T
• Hungarian: Template:T
• Italian: Template:T
• Portuguese: Template:T

See also

• Template:L

Further reading

• Template:Pedia
• Template:Pedia
• Template:Pedia
• Template:Pedia