Transfinite Induction - Transfinite Induction

Transfinite Induction

Let P(α) be a property defined for all ordinals α. Suppose that whenever P(β) is true for all β < α, then P(α) is also true (including the case that P(0) is true given the vacuously true statement that P(α) is true for all ). Then transfinite induction tells us that P is true for all ordinals.

That is, if P(α) is true whenever P(β) is true for all β < α, then P(α) is true for all α. Or, more practically: in order to prove a property P for all ordinals α, one can assume that it is already known for all smaller β < α.

Usually the proof is broken down into three cases:

• Zero case: Prove that is true.

• Successor case: Prove that for any successor ordinal α+1, P(α+1) follows from P(α) (and, if necessary, P(β) for all β < α).

• Limit case: Prove that for any limit ordinal λ, P(λ) follows from .

Notice that all three cases are identical except for the type of ordinal considered. They do not formally need to be considered separately, but in practice the proofs are typically so different as to require separate presentations. Zero is sometimes considered a limit ordinal and then may sometimes be treated in proofs in the same case as limit ordinals.