Principle of transfinite induction
Statement
Let be a class of ordinals such that for every ordinal : if for all , then . Then contains every ordinal.
Why is it true?
This lets us prove a statement for every ordinal — finite, , and beyond — by only ever handling "assume it holds for everything smaller", with no separate base case and no separate limit case needed in the statement of the principle itself.
Proof sketch
Suppose, for contradiction, that does not contain every ordinal. Then the class of ordinals not in is nonempty. The ordinals themselves form a well-order (any nonempty class of ordinals has a least element — this is essentially the defining property of the ordinals), so has a least element; call it .
By minimality of , every ordinal is not in , i.e. every satisfies .
But this is exactly the hypothesis of the theorem applied to : " for all " implies . So .
This contradicts (i.e. ). The contradiction shows no such least counterexample can exist, so : contains every ordinal.
Topics that use this theorem
Step-by-step proofs
No step-by-step proof yet for this theorem.
References
- Wikipedia contributors (2024). Ordinal number
- Wikipedia contributors (2024). König's theorem (set theory)
- Wikipedia contributors (2024). Goodstein's theorem