Is $K_{n-1}$ a $\Sigma_{n-1}$-elementary substruture of $K_n$

Question

Is $K_{n-1}$ a $\Sigma_{n-1}$ elementary substruture of $K_n$?

Let $M$ be any non-standard model of PA.

$K_n$ is define to be the set of $\Sigma_n$-definable elements of $M$.

I have a feeling the statement is true, I try proving by induction, but I keep getting stuck in the induction step.

Any help or insight is appreicated.

Cheers.

Answer 1

The answer, perhaps surprisingly, is no.

We begin by calculating $K_n^M$ in the simplest case:

Suppose $M$ is a model of $PA$ such that $Th_n(M)=Th_n(\mathcal{N})$. Here "$\mathcal{N}$" denotes the standard model of arithmetic, and "$Th_n(\cdot)$" denotes the $\Sigma_n$ theory. Then we have $K_n^M=\mathcal{N}^M$, where "$\mathcal{N}^M$" is the standard part of $M$ (and I'm putting a superscript on $K_n$ for my own comfort).

Proof. Obviously $K_n^M\supseteq\mathcal{N}_M$. Suppose $p\in K_n^M$. Then for some $\Sigma_n$ formula $\varphi(x)$, we have

• $M\models\varphi(p)$, and

• For each $q\in M$, if $q\not=p$ then $M\models\neg\varphi(p)$.

Since $\varphi$ is $\Sigma_n$, the sentence $\psi\equiv\exists x\varphi(x)$ is $\Sigma_n$; since $Th_n(M)=Th_n(\mathcal{N})$, we have $\mathcal{N}\models\psi$. Letting $m\in\mathcal{N}$ witness $\psi$ we have $M\models\varphi(m^M)$ since $Th_n(M)=Th_n(\mathcal{N})$ and every standard natural number is $\Sigma_0$-definable (here "$m^M$" is the element of $\mathcal{N}^M$ corresponding to $m$). Putting this together gives $p=m\in \mathcal{N}^M$. $\quad\Box$

Now here's how we build counterexamples to your claim. Fix $n$, and let $M$ be a model of PA such that $Th_n(M)=Th_n(\mathcal{N})$ but $Th_{k}(M)\not=Th_{k}(\mathcal{N})$ for some $k>n$. We have $K_n^M=\mathcal{N}^M$, but $Th_{k}(\mathcal{N}^M)\not=Th_{k}(M)$. So such a model gives a counterexample to the claim.

How do we know such a model exists? There are several ways. My personal favorite is to note that for each $n$, $\Sigma_n$ truth in $\mathcal{N}$ is definable; now use Tarski's theorem to conclude that the deductive closure of $Th_n(\mathcal{N})$ isn't complete, for any $n$.

---

Incidentally, based off the idea above, the following is a good exercise:

Show that if $M$ is a nonstandard model of $PA$ which does not satisfy true arithmetic, then $M$ contains a definable nonstandard element.