7
$\begingroup$

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$?

$\endgroup$
8
$\begingroup$

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

$\endgroup$
5
$\begingroup$

Emil Jeřábek has already provided a nice answer. Here is another answer to complement his.

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.

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