[Solved]: If all infinite r.e. languages have an infinite recursive subset, then do co-r.e. languages not have such subsets?

Problem Detail: 

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?

Asked By : user2896468

Answered By : Yuval Filmus

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/32952