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 .
|Title||principle of finite induction proven from the well-ordering principle for natural numbers|
|Date of creation||2013-03-22 11:48:04|
|Last modified on||2013-03-22 11:48:04|
|Last modified by||CWoo (3771)|