Exercise 1158Logic, sets and proofs › Quantifiers and negationL1Added 3 Nov 2026

Quantifiers in induction proofs

#induction#quantifiers#base case

Statement

Express the principle of induction using quantifiers.

Hint

$\forall P:\ (\text{Base}\land\text{Step})\Rightarrow\forall n\ge n_0,\ P(n)$ .

Show solutionHide solution

Principle. For any predicate $P$ on integers,
$[P(n_0)\land\forall n\ge n_0,\ (P(n)\Rightarrow P(n+1))]\Rightarrow\forall n\ge n_0,\ P(n).$

Conclusion. Induction is a second-order axiom: quantified over predicates $P$ .

Remark. In first-order arithmetic, induction is an axiom scheme: one instance per definable predicate.