principle of finite induction proven from the well-ordering principle for natural numbers
We give a proof for the “strong” formulation.
Let be a set of natural numbers such that belongs to whenever all numbers less than belong to (i.e., assume , where the quantifiers range over all natural numbers
). For indirect proof, suppose that is not the set of natural numbers . That is, the complement
is nonempty. The well-ordering principle for natural numbers says that has a smallest element; call it . By assumption
, the statement holds. Equivalently, the contrapositive statement holds. This gives a contradition since the element is an element of and is, moreover, the smallest element of .