How can we show that, for every infinite recursive language, it has a subset that is recursively enumerable but not recursive?

I think we need to show there's a list of natural numbers that can't be ordered but I don't know how to build such a subset.

Is there another way of arguing or another type of argument in order to prove such subset exists?

  • $\begingroup$ What have you tried? Where did you get stuck? We want to help you understand concepts, not do your exercise for you, but as you haven't given us much to work with, it's not clear how to help you. Do you know of any lanuage that is recursively enumerable but not recursive? Does that give you any ideas? Given that $L$ is recursive, what do you know about $L$? $\endgroup$
    – D.W.
    Commented Apr 8, 2016 at 17:05
  • $\begingroup$ @D.W. I know that L can be enumerated in canonical order, but i need to show there's a subset that can't be enumerated in this way. Or i can work around Turing machines. An example of a RE but not recursive language is the language of all strings than belong in the language of their corresponding Turing machine. $\endgroup$ Commented Apr 8, 2016 at 17:38
  • $\begingroup$ Alright. Let L be the recursive language and K be the subset you are looking for. Think about this: K has to be infinite because otherwise it would be recursive. Also, L\K has to be infinite; otherwise you could run a finite test whether the input is part of this complement and use the decision algorithm for L otherwise. Try to start with specific cases and generalize step by step. (0+1)*, the language of all words, is arguably the easiest case. If you have a subset for this language, look for one of the language of all words with even canonical index by extending the first case. $\endgroup$
    – Andreas T
    Commented Apr 8, 2016 at 22:25

2 Answers 2


Hint. Let $S$ be any infinite recursive language. By considering, e.g., the lexicographic order, we can talk of the first, second, third, etc. strings in $S$. Use this indexing to define what you need to define.

  • 3
    $\begingroup$ You need $S$ to be r.e. at least. If you want lexicographic order, you need it to be recursive. $\endgroup$ Commented Apr 9, 2016 at 10:36
  • $\begingroup$ @YuvalFilmus Oops. Good point. Fixed. $\endgroup$ Commented Apr 9, 2016 at 14:12

Another hint. Let A be the infinite recursive language. Prove that you may define a computable bijective function f:N->A. Then take any r.e. not recursive subset of N (e.g. the diagonal set K). f(K) is the set you are looking for.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.