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$

2 Answers 2

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .