The induction axiom in the theory of Peano Arithmetic (PA) is actually an axiom scheme such that for every formula $\phi(x,\bar{y})$ with free variables $x,\bar{y}$ ($\bar{y}$ being a string of variables) we include axiom $$ \forall \bar{y} (\phi(0,\bar{y}) \wedge \forall x (\phi(x,\bar{y})\rightarrow \phi(s(x),\bar{y}))\rightarrow \forall x \phi(x,\bar{y})). $$

We often refer to $\mathbb{N}$ as the standard model of PA, in the sense that any model that is not isomorphic to it is considered nonstandard. The fact that $\mathbb{N}$ is a model of PA can be used to proof by means of the compactness theorem that PA is not $\omega$-categorical.

I understand $\mathbb{N}$ to be a structure in the language of PA such that all PA axioms except possibly induction hold and where every element is image of $0$ after applying the successor function a finite number of times.

How do we know that in $\mathbb{N}$ the induction axiom scheme holds?

A way of rephrasing the question could be how do we know that there exists a model of PA where every element is image of $0$ after taking successor finitely many times.


1 Answer 1


It follows from that $\Bbb{N}$ is well-ordered. If $A\subset\Bbb{N}$ is a subset satisfying $0\in A$ and $n\in A \to n+1\in A$, then $A=\Bbb{N}$.

The proof goes as follow: on the contrary, $A\neq\Bbb{N}$. Take $m = \min (\Bbb{N}-A)$. By assumption, elements of $\Bbb{N}$ less than $m$ is in $A$. Moreover $m\neq 0$, so $m$ has a predecessor. However the predecessor of $m$ is in $A$ so $m$ is also in $A$, a contradiction.

Thus if $\phi(x)$ is a formula that satisfy inductive conditions, then $A = \{x\in \Bbb{N} : \Bbb{N} \models \phi(x)\}$ satisfies above two conditions so $A=\Bbb{N}$. That is, $\Bbb{N}\models \forall x \phi(x)$.

As you can see, the proof does not say about any first-order sentences. It just occurs in the last step. In fact you can prove the $\Bbb{N}$ satisfies the second-order induction by slight modification to my proof.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .