Mathematical Induction - Axiom of Induction

The basic assumption or axiom of induction is, in logical symbols,

where P is any proposition and k and n are both natural numbers.

In other words, the basis P(0) being true along with the inductive case ("P(k) is true implies P(k + 1) is true" for all natural k) being true together imply that P(n) is true for any natural number n. A proof by induction is then a proof that these two conditions hold, thus implying the required conclusion.

This works because k is used to represent an arbitrary natural number. Then, using the inductive hypothesis, i.e. that P(k) is true, show P(k + 1) is also true. This allows us to "carry" the fact that P(0) is true to the fact that P(1) is also true, and carry P(1) to P(2), etc., thus proving P(n) holds for every natural number n.

Note that the first quantifier in the axiom ranges over predicates rather than over individual numbers. This is called a second-order quantifier, which means that the axiom is stated in second-order logic. Axiomatizing arithmetic induction in first-order logic requires an axiom schema containing a separate axiom for each possible predicate. The article Peano axioms contains further discussion of this issue.