# A "negative" standard system

For $$\mathcal{M}$$ a (countable) nonstandard model of $$\mathsf{PA}$$, let $$\mathsf{SS}(\mathcal{M})$$ be the set of sets of natural numbers coded by elements of $$\mathcal{M}$$. There are various ways to define this, for example $$\{X\subseteq\mathbb{N}:\exists a\in\mathcal{M}\;\forall k\in\mathbb{N}\;(k\in X\iff p_k\vert a)\}$$ (where $$p_k$$ is the $$k$$th prime and we conflate $$\mathbb{N}$$ with its canonical image in $$\mathcal{M}$$).

I'm curious about how this could differ from the following analogue: let $$\mathsf{SS}^-(\mathcal{M})=\{X\subseteq\mathbb{N}:\exists a\in\mathcal{M}\;\forall k\in\mathbb{N}\;[k\in X\iff \exists n\in\mathbb{N}\;(p_k^n\not\vert a)]\}.$$

Intuitively, elements of $$\mathbb{N}$$ are prevented from entering $$X$$ by corresponding primes dividing $$a$$ "too much." (This version has come up in a separate problem I'm playing with, and I'd like to understand it better.)

It's easy to show that $$\mathsf{SS}(\mathcal{M})$$ is the set of elements of $$\mathsf{SS}^-(\mathcal{M})$$ whose complements are also in $$\mathsf{SS}^-(\mathcal{M})$$, and it's not hard to show that every $$\mathcal{M}$$ has an elementary extension $$\mathcal{N}$$ such that $$\mathsf{SS}^-(\mathcal{N})=\mathsf{SS}(\mathcal{N})$$. However, this still leaves a lot open. In particular:

Is there an $$\mathcal{M}$$ with $$\mathsf{SS}(\mathcal{M})\not=\mathsf{SS}^-(\mathcal{M})$$?

Equivalently per the above, is there an $$\mathcal{M}$$ whose $$\mathsf{SS}^-$$ is not closed under complementation?

• It appears to me that for any $X$ in $SS(\mathcal{M})$, $X'$ is in $SS^-(\mathcal{M})$ and hence they can only be equal if $SS(\mathcal{M})$ is closed under the Turing jump. Since $SS(\mathcal{M})$ is not always closed under jump, they are not always equal. May 29 at 18:06
• @PatrickLutz That's plausible, but I don't see the details. Joel suggested the same thing (in a now-deleted answer) but there was an issue. Can you elaborate? May 29 at 18:18
• Yes, I'll try to type up a complete answer. Perhaps I'll find that there's some problem with it. May 29 at 18:25
• I've posted a complete answer. Let me know if there are any problems with it. May 29 at 19:04

If $$\mathcal{M}$$ is a nonstandard model of PA then for any set $$X \in \mathsf{SS}(\mathcal{M})$$, $$X' \in \mathsf{SS}^-(\mathcal{M})$$. Thus if $$\mathsf{SS}(\mathcal{M}) = \mathsf{SS}^{-}(\mathcal{M})$$ then $$\mathsf{SS}(\mathcal{M})$$ is closed under the Turing jump. Since not every Scott set is closed under the jump, $$\mathsf{SS}(\mathcal{M})$$ is not always equal to $$\mathsf{SS}^-(\mathcal{M})$$.
Claim. If $$X \in \mathsf{SS}(\mathcal{M})$$ then $$X' \in \mathsf{SS}^-(\mathcal{M})$$.
Proof. Suppose $$X$$ is in $$\mathsf{SS}(\mathcal{M})$$. Thus there is some $$a$$ such that $$\forall k \in \mathbb{N}\, (k \in X \iff p_k \mid a).$$ Now let $$b$$ be a fixed nonstandard number in $$\mathcal{M}$$ and let $$c$$ be a nonstandard number such that $$\forall n, k < b\, (p_k^n \mid c \iff \varphi^a_k(k) \text{ does not converge in \leq n steps}).$$ Here, using $$a$$ as an oracle for $$\varphi_k(k)$$, means that when $$\varphi_k(k)$$ asks a question about $$m$$ to the oracle, we check if $$p_m \mid a$$ to determine the answer. Note that the existence of such a $$c$$ can be proved in PA.
Now let $$Y = \{k \in \mathbb{N} \mid \exists n \in \mathbb{N} \, (p_k^n \nmid c)\}$$. I claim that $$Y = X'$$. To show this it is enough to show that for all $$n, k \in \mathbb{N}$$, $$p_k^n \mid c$$ if and only if $$\varphi^X_k(k)$$ does not converge in $$\leq n$$ steps.
Note that for $$n$$ and $$k$$ standard natural numbers, the convergence or nonconvergence of $$\varphi^X_k(k)$$ within $$n$$ steps is witnessed by a standard natural number (encoding the transcript of the computation). And since running $$\varphi^X_k(k)$$ for $$n$$ steps never requires asking questions of the oracle at nonstandard numbers, there is no difference between using $$X$$ and $$a$$. Thus $$\mathcal{M}$$ can check that the witness to convergence or divergence of $$\varphi^X_k(k)$$ within $$n$$ steps is also a witness to the convergence or divergence of $$\varphi^a_k(k)$$ within $$n$$ steps and therefore by definition of $$c$$, $$p_k^n \mid c$$ if and only if $$\varphi^X_k(k)$$ does not converge in $$\leq n$$ steps.
• By the way, I'm pretty sure this exactly characterizes $\mathsf{SS}^-(\mathcal{M})$: it is the set of subsets of $\mathbb{N}$ which are $\Sigma^0_1$ in some element of $\mathsf{SS}(\mathcal{M})$. May 29 at 19:14