principle of finite induction proven from the well-ordering principle for natural numbers


We give a proof for the “strong” formulation.

Let S be a set of natural numbers such that n belongs to S whenever all numbers less than n belong to S (i.e., assume n(m<nmS)nS, where the quantifiersMathworldPlanetmath range over all natural numbersMathworldPlanetmath). For indirect proof, suppose that S is not the set of natural numbers . That is, the complementPlanetmathPlanetmath S is nonempty. The well-ordering principle for natural numbers says that S has a smallest element; call it a. By assumptionPlanetmathPlanetmath, the statement (m<amS)aS holds. Equivalently, the contrapositive statement aSm<amS holds. This gives a contradition since the element a is an element of S and is, moreover, the smallest element of S.

Title principle of finite induction proven from the well-ordering principle for natural numbers
Canonical name PrincipleOfFiniteInductionProvenFromTheWellorderingPrincipleForNaturalNumbers
Date of creation 2013-03-22 11:48:04
Last modified on 2013-03-22 11:48:04
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 16
Author CWoo (3771)
Entry type Proof
Classification msc 03E25
Classification msc 37H10