Productive sets and indices of constant functions

Question

Let $\phi_0,\phi_1,\phi_2,\ldots$ be an acceptable programming system. Recall that a set $S$ is productive if there exists a recursive function $p$ such that $(\forall x)(W_x\subseteq S\Rightarrow p(x)\in S\setminus W_x)$, where $W_x$ is the domain of the function $\phi_x$, for every $x$. Let $A=\{x:(\forall y)(\phi_x(y)=0)\}$ and $B=\{x:(\forall y)(\phi_x(y)=1)\}$. Is there a set $S$ such that $A\subseteq S$, $B\subseteq\mathbb{N}\setminus S$ and neither $S$ nor $\mathbb{N}\setminus S$ is productive? Note that, if $S$ is recursively enumerable, then $\mathbb{N}\setminus S$ is productive (see the paper "ON CREATIVE SETS AND INDICES OF PARTIAL RECURSIVE FUNCTIONS" by LOUISE HAY, Theorem 5.)

Answer 1

Yes. Let $U = \{ x : (\exists n, s)[\phi_{x,s}(n) = 0 \wedge (\neg \exists m) [\phi_{x,s}(m) = 1]]\}$. Note that the $\neg \exists m$ quantifier can be bounded by $s$, so this is c.e.. Let $V$ be the same, but with the role of $0$ and $1$ reversed. So $U$ and $V$ are disjoint c.e. sets with $A \subset U$ and $B \subset V$.

We'll construct $S$ as a superset of $U$ and disjoint from $V$. This alone determines $S$ on infinitely many elements, but leaves infinitely many undetermined. Fix $u$ and $v$ with $U = W_u$ and $V = W_v$. We construct $S$ in stages.

At stage $2t$, consider $\phi_t$. We wish to ensure that $\phi_t$ is not a productive function for $S$. Consider $\phi_t(u)$. If this diverges, there is nothing to do. Otherwise, let $n_0 = \phi_t(u)$. If $n_0 \in U$, there's nothing to do. If we have already declared that $n_0 \not \in S$, there's nothing to do. If we have not yet decided whether or not $n_0$ is an element of $S$, declare $n_0 \not \in S$. This defeats $\phi_t$.

The only remaining case is when $n_0 \not \in U$, but we have already decided that $n_0 \in S$. In this case, fix $u_0$ with $W_{u_0} = U \cup \{n_0\}$. Consider $\phi_t(u_0)$. Repeat the process we just went through. In this fashion, we might generate a sequence $u_0, u_1, u_2, \dots$, but this will end at $u_t$, since we've only declared at most $t$ many elements of $\omega \backslash U$ to be in $S$ by stage $2t$. Hence we ensure that $p_t$ is not a productive function for $S$.

At stage $2t+1$, consider again $\phi_t$, but this time make sure it isn't a productive function for $\omega\backslash S$ by considering $\phi_t(v)$. The argument then proceeds symmetrically.

The construction just outlined can be carried out by $0'$, so $S$ is $\Delta^0_2$.