1
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.