# On models of $Th_{\Pi_2}(PA)$

Let $$M$$ be a nonstandard model of $$PA$$.

Q1. Is there any way to get a submodel $$N\subset M$$ such that $$N\models Th_{\Pi_2}(PA)$$, but $$N\not\models PA$$?

Q2. Especially, what combinatorial principle can be used to construct a model $$N\models Th_{\Pi_2}(PA)$$ such that $$N\not\models PA$$? Or $$Th_{\Pi_2}(PA)\vdash PA$$?

$$\def\pa{\mathit{PA}}\def\rfn{\mathrm{RFN}}\def\pr{\mathrm{Pr}}\def\num#1{\ulcorner#1\urcorner}\def\Th{\mathrm{Th}}$$ $$\Th_{\Pi_2}(\pa)$$ certainly does not prove $$\pa$$:

Theorem: For any constant $$k$$, there is no consistent $$\Pi_k$$-axiomatized theory $$T$$ such that $$T\vdash\pa$$.

More generally, if $$S$$ is a sequential theory that proves full induction, then $$S$$ is not derivable from any consistent theory $$T$$ axiomatized by formulas of restricted quantifier complexity.

(So, for example, $$\mathit{ZF}$$ is not derivable from any consistent theory axiomatized by $$\Pi_k$$-sentences in the Levy hierarchy.)

The reason is that $$\pa$$ proves the uniform reflection principles $$\rfn_Q(\Pi_k)=\forall x\,(\pr_Q(x)\land x\in\Pi_k\to\mathrm{Tr}_k(x)),$$ where $$\mathrm{Tr}_k$$ is the truth predicate for $$\Pi_k$$-sentences, $$\mathrm{Pr}_Q$$ is the provability predicate for $$Q$$, and $$Q$$ could really stand for any fixed finitely axiomatized subtheory of $$\pa$$ (the choice does not matter much).

So, if $$T$$ is a $$\Pi_k$$-axiomatized theory that proves $$\pa$$, then there is a finitely axiomatized subtheory $$T_0\subseteq T$$ that proves $$\rfn_Q(\Pi_{k+1})$$, and (say) $$I\Sigma_1$$. Let $$\psi=\bigwedge T_0$$. Then $$\pr_Q(\num{\neg\psi})\to\neg\psi$$ is an instance of $$\rfn_Q(\Pi_{k+1})$$, which implies that $$T_0$$ proves its own consistency. By Gödel’s theorem, $$T_0$$ is inconsistent, hence so is $$T$$.

As for constructing submodels of $$M\models\pa$$ satisfying $$\Th_{\Pi_2}(\pa)$$ but not $$\pa$$, there is the following general result due to McAloon [1]:

Theorem (McAloon): Let $$T$$ be a recursively axiomatizable $$\Sigma_1$$-sound extension of $$I\Sigma_1$$. Then for any countable nonstandard model $$M\models I\Delta_0$$, there is a nonstandard cut $$N\subseteq M$$ such that $$N\models T$$.

This was generalized to $$M\models IE_1$$ by Wilmers [2].

McAloon’s argument relies on the indicator theory, hence one may consider it a combinatorial construction.

In order to get $$N\models\Th_{\Pi_2}(\pa)$$, $$N\not\models\pa$$, we can apply this theorem to $$T=I\Sigma_1+\Th_{\Pi_2}(\pa)+\neg\rfn_Q(\Pi_4).$$ We only need to check that $$T$$ is $$\Sigma_1$$-sound. In fact, $$T$$ is $$\Pi_4$$-conservative over the (sound) theory $$I\Sigma_1+\Th_{\Pi_2}(\pa)$$.

To see this, let $$\phi$$ be a $$\Pi_4$$-sentence provable in $$T$$. Notice that $$I\Sigma_1+\Th_{\Pi_2(\pa)}$$ is $$\Pi_3$$-axiomatizable, hence there exists a $$\Pi_3$$-sentence $$\psi$$ derivable in $$I\Sigma_1+\Th_{\Pi_2(\pa)}$$ such that $$\psi\land\neg\phi\vdash\rfn_Q(\Pi_4).$$ As before, an instance of $$\rfn$$ for the $$\Pi_4$$-sentence $$\neg(\psi\land\neg\phi)$$ shows $$\psi\land\neg\phi\vdash\mathrm{Con}_{\psi\land\neg\phi},$$ hence $$\psi\land\neg\phi$$ is inconsistent by Gödel’s theorem, i.e., $$I\Sigma_1+\Th_{\Pi_2}(\pa)\vdash\psi\vdash\phi.$$

[1] Kenneth McAloon, On the complexity of models of arithmetic, Journal of Symbolic Logic 47 (1982), no. 2, pp. 403–415.

[2] George Wilmers, Bounded existential induction, Journal of Symbolic Logic 50 (1985), no. 1, pp. 72–90.

Answer to Q1: Yes, indeed $2$ can be replaced with any natural number $n>0$.

Explanation: Let $M$ be a nonstandard model of $PA$ and let $a$ be a nonstandard element of $M$, and $n$ be a fixed natural number, and let $K^{n}(M,a)$ be the submodel of $M$ consisting of elements that are definable in $(M,a)$ using a $\Sigma_n$ unary formula with parameter $a$. Then we have:

Theorem (Kirby & Paris). For all natural numbers $n\geq 1$:

(1) $K^{n}(M,a)$ is a $\Sigma_n$-elementary submodel of $(M,a)$.

(2) The collection scheme $B\Sigma_n$ fails in $K^{n}(M,a)$.

Note that the first condition of the theorem assures us that $K^{n}(M,a)$ satisfies all $\Pi_n$-consequences of $PA$, and the second condition tells us that $K^{n}(M,a)$ is not a model of $PA$.

[You can find an exposition of the theorem above in Chapter 10 of Kaye's textbook Models of Peano Arithmetic, or in chapter IV of the Hajek-Pudlak textbook Metamathematics of First Order Arithmetic].

Answer to Q2: The usual method is to arrange a model that supports a definable map whose domain is the predecessors of a "number", and whose range is unbounded in the model. This is equivalent to the failure of the scheme $B\Sigma_n$ mentioned above.