Ordinals and axioms · Definition

Transfinite induction

set theoryordinals and axioms

When indices stop being natural numbers, ordinary induction no longer covers the whole process. This method proves properties and supports definitions along any well-ordering, especially on the ordinals.

Definition

Principle that proves a property holds for all ordinal numbers \(\mathrm{On}\) by showing that if it holds for all ordinals below a given \(\alpha\), it also holds for \(\alpha\).

\[\forall\alpha[\forall\beta<\alpha P(\beta)\to P(\alpha)]\to\forall\alpha P(\alpha)\]

The general version does not separate cases: it is enough to show that \(P(\alpha)\) follows from \(P(\beta)\) for every \(\beta<\alpha\). Its validity comes from the well-ordering of the ordinals, since a counterexample would have a least element, and that least element would yield a contradiction.

To prove that \(0+\alpha=\alpha\) for every ordinal, the proof can be organized into three cases: \(0+0=0\); at a successor, \(0+(\beta+1)=(0+\beta)+1=\beta+1\) by hypothesis; and at a limit, \(0+\lambda=\sup_{\beta<\lambda}(0+\beta)=\sup_{\beta<\lambda}\beta=\lambda\).

The most common mistake is treating a limit as a successor, looking for an immediate predecessor \(\lambda-1\) that does not exist. It is also not enough to check only the immediately preceding ordinal, because the general step needs every \(\beta<\alpha\).

Think about it

Why does \(P(0)\) follow without a separate proof?

Because there is no \(\beta<0\), so the condition is vacuous.

Exercises 10

  1. What does the general step of transfinite induction require?
  2. If \(P(\alpha)\) follows whenever \(P(\beta)\) holds for all \(\beta<\alpha\), what do we conclude?
  3. How is the successor case \(\alpha=\beta+1\) handled in the general version?
  4. Which of these ordinals is a limit ordinal?
  5. On which kind of ordered sets can transfinite induction be applied?
  6. Let \(P(\alpha): \alpha\notin\alpha\). The general step assumes \(\alpha\in\alpha\). What follows?
  7. If \(0+\alpha=\alpha\) for every ordinal \(\alpha\), what is \(0+(\omega+1)\)?
  8. If \(0+\beta=\beta\) for all \(\beta<\lambda\) and \(\lambda\) is a limit ordinal, what is \(0+\lambda\)?
  9. Is it valid to conclude that \(P\) holds for every ordinal if \(P(0)\) holds and \(P(\beta)\) implies \(P(\beta+1)\) for every \(\beta\)? Give a counterexample if not.
  10. Let \(P(\alpha): 1+\alpha=\alpha\). Evaluate \(P(0)\), \(P(1)\) and \(P(\omega)\). What can be concluded?

References

  • Herbert B. Enderton, Elements of Set Theory, 1st edition, Academic Press, 1977.
  • Thomas Jech, Set Theory (The Third Millennium Edition), 3rd millennium edition, Springer, 2003.