If a set S is infinite and recognizable, is there an infinite subset of S that is decidable?

Problem Detail: 

If a set S is infinite and recognizable, how can I prove that, if any, some subsets K is infinite and decidable? how about infinite and recognizable?

Asked By : user3277633

Answered By : Luke Mathieson

The second question is the easier one, we can just pick any string $\varsigma$ in the infinite Turing recognizable language $S$, and let $S' = S\setminus\{\varsigma\}$. Then you should be able to construct a TM that recognizes $S'$ from the recognizer $R$ for $S$.

The normal proof for the first question is trickier, relying on two facts:

1. Every Turing recognizable language has an enumerator (a TM that prints out the strings in the language one by one).
2. If a language has a lexicographic enumerator (a TM that enumerates the strings in the language in lexicographic order), then it is decidable.

So you start with $S$, which must have an enumerator $E$ that prints out, one by one, the strings in $S$ in some order, which may include repeats. What you have to do is construct a lexicographic enumerator using $E$ as a subroutine. It doesn't have to print out everything in $S$, just a subset of course, the trick is to ensure that the ones it prints are in lexicographic order. As noted Jeremy West in the comments, we must also ensure that the subset is infinite, this is easy enough, just not to be forgotten.

Best Answer from StackOverflow

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