A "negative" standard system

Question

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?

Answer 1

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.