Decidable language contained between (co)-recursively enumerable languages

Question

Let languages $A, B$ be co-recursively enumerable and disjoint. Prove the existence of a decidable language $L$ such that $A \subset L$ and $B \cap L = \emptyset$. That is, such that $A \subset L \subset B^c$.

The question should not be too hard (was on a rather easy exam, but I did not know how to do this one. Exam is over but still would be cool to know how to do this one!). I have the feeling it has something to do with the fact that the intersection of recursively and co-recursively enumerable languages is the set of decidable languages. Then starting with $A$, a co-recursively enumerable language, we add more and more words, and finally end up with $B^c$, a recursively enumerable language. I have some intuition that somewhere along the way we must have necessarily passed through some decidable languages, and cannot flip from co-recursively enumerable to recursively enumerable in an "instant" when adding words in such a way. But I am not sure how to put this intuition into a valid proof.

Answer 1

TLDR: Dovetail recursive enumerations of $A^c$ and $B^c.$ Every number appears in at least one of those two enumerations. Say that a number $x$ is in $L$ iff the first appearance of $x$ is in the $B^c$ enumeration, rather than the $A^c$ enumeration.

Here are the details:

If $A=\omega$ or $B=\omega,$ this is trivial, so we'll assume that $A\ne\omega$ and $B\ne\omega.$

Since the complement of $A$ and the complement of $B$ are non-empty and recursively enumerable, there exist total recursive functions $f$ and $g$ whose ranges are $A^c$ and $B^c,$ respectively.

For any $x\in\omega,$ let $k(x)$ be the least $n$ such that $f(n)=x$ or $g(n)=x.$ (For each $x,$ there must exist such an $n,$ since $A^c\cup B^c=\omega.)$

The function $k$ is a total recursive function (to compute $k(x),$ simply compute $f(0), g(0), f(1), g(1), f(2), g(2), \dots$ until you hit the first $f(n)$ or $g(n)$ which equals $x,$ which we know will eventually happen, and then output $n.)$

We have that for every $x,$ $f(k(x))=x$ or $g(k(x))=x.$

Set $L=\{x\mid g(k(x))=x\}.$

$L$ is clearly recursive.

$A\subseteq L,$ since if $x\in A,$ then $x$ is not in the range of $f.$ As a result, $f(k(x))$ cannot equal $x,$ so we must have $g(k(x))=x;$ that is, $x\in L.$

$L\subseteq B^c,$ since any $x\in L$ is equal to $g(k(x)),$ so is in the range of $g,$ which is $B^c.$

Answer 2

If $A$ is co-RE, there is a deterministic Turing machine $T_A$ that decides non-membership for $A$. Likewise, there is a deterministic Turing machine $T_B$ that decides membership for $B^c$.

Run $T_A$ and $T_B$ in interleaved fashion. If a word $w$ is in $A$, $T_A$ may loop, but $T_B$ will halt. If both TMs halt, they both report that $w$ passes the membership test. If $w \in B$, then $T_B$ may loop, but $T_A$ will halt. If both TMs halt, they both report that $w$ failed the membership test.

For $w \in B^c - A$, both $T_A$ and $T_B$ will halt, but $T_A$ will reject and $T_B$ will accept. In sum, at least one TM will halt on any word.

Let $L$ be defined as follows: $w \in L$ if and only if the first TM to halt accepts.