# When is first order induction valid?

Assume we know $\forall x(P(x))$ is true in a model of Peano arithmetic (PA). Does this mean we can prove $\forall x(P(x))$ using induction? If not, why not? If $P(x)$ is true for all $x$ then $P(0) \land \forall x(P(x) \rightarrow P(S(x)))$ is a true statement.

What if $\forall x(P(x))$ is false in some other model of PA?

I want to emphasize the "if not, why not" part. What more is needed to prove $\forall x(P(x))$ if satisfying the induction axiom schema is not enough.

I think I figured out my confusion. When we say "$\forall x P(x)$" is provable by induction what we mean is we can prove $P(0) \land \forall x(P(x) \rightarrow P(Sx))$ from the other axioms of PA and we can then use modus ponens and the induction axiom $(P(0) \land \forall x(P(x) \rightarrow P(Sx))) \rightarrow \forall x P(x)$ to deduce $\forall x P(x)$. Assume we can prove $\forall x P(x)$ from the other axioms of PA. This does not mean we can prove $\forall x P(x)$ "using induction". We would still have to prove $P(0) \land \forall x(P(x) \rightarrow P(Sx))$ before we could use modus ponens. Of course, we don't need induction to prove $\forall x P(x)$ if it can be derived from the other axioms.

The only way the induction axiom can be false is when $P(0) \land \forall x(P(x) \rightarrow P(Sx))$ is true and $\forall x P(x)$ is false. The easiest way for this to happen is when a proper subset of a model is closed under successor.

Let $P(x)$ = "x does not encode a proof of 0=1". If PA is consistent then there is a model of PA + $\exists x \neg P(x)$. Such a model is $\omega$ - inconsistent. The standard natural numbers are a proper subset of this model and are closed under successor. Even though $P(0) \land \forall x(P(x) \rightarrow P(Sx))$ is true for the standard natural numbers, $\forall x P(x)$ is false. It would seem a model of PA + $\exists x \neg P(x)$ must fail to satisfy induction. We get around this by talking about "definable" subsets of natural numbers. If PA is consistent then the standard natural numbers can't be definable in the language of PA.

• If the inductive premises are true in some model but false in some other, then completeness tells us that you can't prove them from PA. What's provable is what's true in every model. Of course, given PA+$P(0)\wedge\forall x(P(x)\to P(Sx))$ you can show in a purely question begging way that the induction works. – Malice Vidrine Nov 12 '13 at 4:32
• @Russell: I think the question is a little ambiguous in saying what it means to prove something "by induction". Do you mean provability in $\mathrm{PA}$? Anyway, if $M\models\mathrm{PA}+\forall x\ P(x)$, then it does not follow that $\mathbb N\models\forall x\ P(x)$ because $M$ and $\mathbb N$ may disagree on $P$. – Lawrence Wong Nov 16 '13 at 17:23
• @Lawrence Wong: I agree saying something is provable by induction is ambiguous. This is why I asked the question. I mean provable in PA. It seems any proof requiring induction is suspect because someone may dream up a model of PA where it is false. – Russell Easterly Nov 17 '13 at 4:18
• @Russell: If $\mathrm{PA}$ (and hence induction according to your definition) proves a sentence $\sigma$, then no model of $\mathrm{PA}$ can fail to satisfy $\sigma$. – Lawrence Wong Nov 17 '13 at 15:21

There are sentences of the form you describe that are neither provable nor refutable in first-order PA. If $\varphi$ is such a sentence, it will be true in some model of PA, but unprovable from the axioms of PA. One can arrange for $\phi(0)$ to be a theorem. So the induction step will not be a theorem.

• I don't understand the last part. Does this mean we can't use induction to prove $\forall x(P(x))$ even if it is true in the standard model? – Russell Easterly Nov 12 '13 at 3:23
• That's right, we cannot (sometimes). – André Nicolas Nov 12 '13 at 3:26

To give an explicit example for André Nicolas's answer, if $\phi (n)$ means "the Goodstein sequence starting with $n+2$ is eventually constantly $0$" then by Goodstein's theorem we know that $(\forall x)\phi(x)$ holds in the standard model, but a result of Kirby and Paris says that this is not a theorem of $\mathsf{PA}$.

Consider $P(x)$ as the statement "$x$ does not encode a proof from the axioms of $\sf PA$ that $0=1$". Clearly $\sf PA$ cannot prove $\forall xP(x)$, because that would amount for proving its consistency, moreover $\Bbb N\models\forall xP(x)$, because no standard integer can encode a proof of $\lnot\rm Con(\sf PA)$.

However if $\sf PA$ is consistent then so is $\sf PA+\lnot\mathrm{Con}(PA)$ is consistent, and if $M$ is a model of the latter, then $M\models\lnot\forall xP(x)$, because $M$ knows a [non-standard] number which does encode a proof of contradiction. Do note that in such $M$, the non-standard numbers encode "new axioms" of $\sf PA$, and "new proofs". The contradiction appears in those non-standard additions.

In the general case, I think that the answer should be "Suppose that $\forall xP(x)$ is provable from $\sf PA$, is it provable by induction?", and then the answer is yes; but in almost a trivial way. It will be the case that $\sf PA$ proves $P(0)$, and in fact $P(n)$ and $P(S(n))$ and so $\sf PA$ proves $P(0)\land\forall n(P(n)\rightarrow P(S(n)))$. By the induction schema, $\sf PA$ proves $\forall xP(x)$.

On the other hand, if $\forall xP(x)$ is not provable from $\sf PA$ then it cannot be proved. And if it is false in some models, then it is not provable (unless you assume that $\sf PA$ is inconsistent to begin with, or that first-order logic is not sound. In either way, though, you are essentially begging the question).