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

  • 1
    $\begingroup$ Maybe you could provide a bit more background for your question? $\endgroup$
    – Stefan Kohl
    Dec 21, 2013 at 15:15

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


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.