For all humankind
Academicsubsite
ZixuanZhang
ZixuanZhang
Ponder...

Strong induction implies well-ordering

Assuming the strong principle of induction, every non-empty subset of has a least element: .

Theorem 3.7
.

Proof

Assume holds for with , and suppose, for contradiction, that there is no least such that holds. Consider .

Certainly is false, because otherwise would be our minimal element; so holds. Now, given , suppose is true for all . Then must be false for all , and so must also be false — otherwise would be our minimal element. Hence holds.

Hence by SPI, holds for all , and is false for all , contradicting the assumption that holds for some .

The converse fails

The converse fails: , and the well-ordering principle fails for certain ordinals. However, in any proof using SPI, one can in fact use WOP instead.

Related

Stated in