If all infinite r.e. languages have an infinite recursive subset, then can we logically take co-r.e. languages to not have such subsets by complemence?


In one word: no. It doesn't follow logically. It is also definitely not the case that no infinite co-r.e. language can have infinite recursive subsets: every infinite recursive set, say $0^*$, is also r.e. and co-r.e.

It is easy to show that any infinite r.e. set contains an infinite recursive subset: run the enumerator and accept a word if it is longer than any previously accepted word. This approach doesn't work for co-r.e. sets, and leads to the conjecture that there exists an infinite co-r.e. set that doesn't contain an infinite recursive subset. When trying to prove this using diagonalization, we see that since there is no way of distinguishing infinite recursive sets from infinite r.e. sets, the property we are after is an infinite co-r.e. set that doesn't have any infinite r.e. subset.

It is not too difficult to prove that such sets, called co-simple, exist, following the footsteps of Post (1944). Instead of constructing an infinite co-r.e. set which doesn't have an infinite r.e. subset, we will construct a co-infinite r.e. set $S$ which intersects every infinite r.e. set. Simulate all Turing machines, and for Turing machine $e$, put in $S$ the first $x > 2e$ such that $e$ halts on $x$ (if any); here we think of $e,x$ as integers. This is clearly an r.e. set, which clearly intersects every infinite r.e. set. It is co-infinite since for every $n$, we put in $S$ at most $n/2$ integers, at most one from each of the programs $1,\ldots,n/2$.

| cite | improve this answer | |

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.