Remark

There are various criteria which are frequently used under the name of "principle of induction". They can all be easily deduced from C61, and we indicate here the most important of them :

(1) Let $S\{n\}$ be the relation

and suppose that $S\{n\}$ implies $R\{n\}$. Then the relation

is true. For the relation $S\{0\}$ is true, and by hypothesis $S\{n\}$ implies $R\{n\}$; since the relation $m < n + 1$ is equivalent to $m \leqslant n$ (no. 2, Proposition 2), the relation $S\{n + 1\}$ is equivalent to "$S\{n\}$ and $R\{n\}$", consequently, $S\{n\}$ implies $S\{n + 1\}$. The criterion C61 therefore proves that the relation

is true, and since $S\{n\}$ implies $R\{n\}$, the relation

is true.

(2) Let $k$ be an integer and let $R\{n\}$ be a relation such that the relation

is true. Then the relation

is true ("*induction starting at k*"). For let $S\{n\}$ be the relation

Then by the method of disjunction of cases we see that $S\{0\}$ is true. On the other hand, it is easily verified that the relation

is true. It follows from C61 that the relation

is true, which proves our assertion.

(3) Let $a$ and $b$ be two integers such that $a \leqslant b$, and let $R\{n\}$ be a relation such that

Then the relation

is true. The proof is similar to that of the preceding case; we take $S\{n\}$ to be the relation "$(a \leqslant n < b) \Rightarrow R\{n\}$" ("*induction restricted to an interval*").

(4) Let $a$, $b$ be two integers such that $a \leqslant b$, and let $\mathrm{R}\{n\}$ be a relation such that

$\mathrm{R}\{b\}$ and $(\forall n)((n$ is an integer and $a \leqslant n < b$ and $\mathrm{R}\{n+1\}) \Rightarrow \mathrm{R}\{n\})$.

Then the relation

is true. For we have the relation

$(n$ is an integer and $a \leqslant n < b$ and (not $\mathrm{R}\{n\}$)) $\Rightarrow$ not $\mathrm{R}\{n+1\}$.

If for some $n$ such that $a \leqslant n \leqslant b$ we had (not $\mathrm{R}\{n\}$), it would follow from (3) that (not $\mathrm{R}\{b\}$), contrary to the hypothesis, whence the result ("descending induction").