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
- Theorem 3.7§3.2 Induction and Ordering
