When is first order induction valid?

Question

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.

Answer 1

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.

Answer 2

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}$.

Answer 3

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).