Induction axiom

The assertion of the validity for all $x$ of some predicate $P(x)$ defined on the set of all non-negative integers, if the following two conditions hold: 1) $P(0)$ is valid; and 2) for any $x$, the truth of $P(x)$ implies that of $P(x+1)$. The induction axiom is written in the form

$$P(0)\mathbin\&\forall x(P(x)\supset P(x+1))\supset\forall x\ P(x).$$

In applications of the induction axiom, $P(x)$ is called the induction predicate, or the induction proposition, and $x$ is called the induction variable, induction parameter or the variable with respect to which the induction is carried out (in those cases when $P(x)$ contains other parameters apart from $x$). Here the verification of condition 1) is called the basis of the induction, while the verification of condition 2) is called the induction step. The assumption in 2) of the validity of $P(x)$, from which $P(x+1)$ is then deduced, is called the induction hypothesis. The principle of (mathematical) induction in mathematics is the scheme of all induction axioms for all possible predicates $P(x)$. In the system $\text{FA}$ of formal arithmetic (cf. Arithmetic, formal), the induction scheme consists merely of those induction axioms that correspond to predicates expressible in $\text{FA}$ (these predicates form a countable set). It is this circumstance, namely the impossibility of expressing in $\text{FA}$ induction in its full extent, that is responsible for the incompleteness of $\text{FA}$ (see Gödel incompleteness theorem).

Sometimes one considers the following axiom instead of the induction axiom: Let $P(x)$ be some property of non-negative integers; if for any $x$ it follows from the assumption that $P(y)$ is true for all $y$ smaller than $x$ that $P(x)$ is true, then $P(x)$ is true for all $x$. In other words,

$$\forall x((\forall y<x)P(y)\supset P(x))\supset\forall x\ P(x).$$

This axiom is called the complete or recursive induction axiom. The principle of complete induction is equivalent to the principle of ordinary induction. See also Transfinite induction.

References

[1]	S.C. Kleene, "Mathematical logic" , Wiley (1967)