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?

  • $\begingroup$ 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. $\endgroup$ May 29 at 18:06
  • 1
    $\begingroup$ @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? $\endgroup$ May 29 at 18:18
  • $\begingroup$ Yes, I'll try to type up a complete answer. Perhaps I'll find that there's some problem with it. $\endgroup$ May 29 at 18:25
  • $\begingroup$ I've posted a complete answer. Let me know if there are any problems with it. $\endgroup$ May 29 at 19:04

1 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.

  • 1
    $\begingroup$ Nice, I think this works! I almost got this (so did Joel), but I wasn't actually doing enough detailed coding. $\endgroup$ May 29 at 19:11
  • $\begingroup$ 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})$. $\endgroup$ May 29 at 19:14

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.