Transfinite induction

Transfinite induction is an extension of mathematical induction to ordinal numbers. Its correctness is a theorem of ZF, and relies on the fact that the ordinal numbers are well-ordered, and thus a statement that is not universally true for all ordinals must have a minimal counterexample. In fact, this principle is also true for arbitrary well-ordered sets, but since any well-ordered set can be indexed by ordinals in an order-preserving way, it suffices to establish the principle for ordinals.

Overview

The principle of transfinite induction is as follows:

This principle can be easily proved by considering the contrapositive form:

Such an ⁠

α

{\displaystyle \alpha }

⁠ is just a minimal counterexample, the existence of which is guaranteed by the fact the class of ordinal numbers is well-ordered.

Induction by cases

A proof by transfinite induction is often broken down into three cases:

Zero case: Prove that

P

(

0

)

{\displaystyle P(0)}

is true.

Successor case: Prove that for any successor ordinal

α

+

1

{\displaystyle \alpha +1}

,

P

(

α

+

1

)

{\displaystyle P(\alpha +1)}

follows from

P

(

α

)

{\displaystyle P(\alpha )}

(and, if necessary,

P

(

β

)

{\displaystyle P(\beta )}

for all

β

<

α

{\displaystyle \beta <\alpha }

).

Limit case: Prove that for any limit ordinal

λ

{\displaystyle \lambda }

, if

P

(

β

)

{\displaystyle P(\beta )}

holds for all

β

<

λ

{\displaystyle \beta <\lambda }

, then

P

(

λ

)

{\displaystyle P(\lambda )}

.

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.