Editing Mathematical induction (section)

== Formalization {{anchor|Axiom of induction}} ==
In '''[[second-order logic]]''', one can write down the "[[axiom]] of induction" as follows:
<math display="block">\forall P\,\Bigl( P(0) \land \forall k \bigl( P(k) \to P(k+1)\bigr ) \to \forall n \,\bigl(P(n)\bigr)\Bigr),</math>
where {{math|''P''(&middot;)}} is a variable for [[Predicate (mathematical logic)|predicates]] involving one natural number and {{mvar|k}} and {{mvar|n}} are variables for [[natural number]]s.

In words, the base case {{math|''P''(0)}} and the induction step (namely, that the induction hypothesis {{math|''P''(''k'')}} implies {{math|''P''(''k'' +&thinsp;1)}}) together imply that {{math|''P''(''n'')}} for any natural number {{mvar|n}}. The axiom of induction asserts the validity of inferring that {{math|''P''(''n'')}} holds for any natural number {{mvar|n}} from the base case and the induction step.

The first quantifier in the axiom ranges over ''predicates'' rather than over individual numbers. This is a second-order quantifier, which means that this 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.

The axiom of structural induction for the natural numbers was first formulated by Peano, who used it to specify the natural numbers together with the following four other axioms:

# 0 is a natural number.
# The successor function {{mvar|s}} of every natural number yields a natural number {{math|1=(''s''(''x'') = ''x'' + 1)}}.
# The successor function is [[injective]].
# 0 is not in the [[Range of a function|range]] of {{mvar|s}}.

In '''[[First-order logic|first-order]] [[ZFC set theory]]''', quantification over predicates is not allowed, but one can still express induction by quantification over sets:
<math display="block">\forall A \Bigl( 0 \in A \land \forall k \in \N \bigl( k \in A \to (k+1) \in A \bigr) \to \N\subseteq A\Bigr)</math>
{{mvar|A}} may be read as a set representing a proposition, and containing natural numbers, for which the proposition holds. This is not an axiom, but a theorem, given that natural numbers are defined in the language of ZFC set theory by axioms, analogous to Peano's. See [[Axiom of infinity#Alternative method|construction of the natural numbers]] using the [[axiom of infinity]] and [[axiom schema of specification]].