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.


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


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.


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.