I'm trying to figure out how to prove or disprove the following statement:

Infinite union of recursive languages is recursively enumerable.

I know how to prove that infinite union of regular languages is not recursive, but I can't figure out how to prove the statement above. Intuition is telling me that the statement is true, but I'm not sure. Does anybody know how would I go about it?

Any help is greatly appreciated.

  • 3
    $\begingroup$ Consider the infinite usion of languages of the form $\{w\}$, i.e., each containing a single word. $\endgroup$ Nov 12, 2013 at 0:29
  • $\begingroup$ @HendrikJan: I think this will just tell me that infinite set of recursive languages is not recursive. What I need to show that infinite set is recursively enumerable (or not). $\endgroup$
    – flashburn
    Nov 12, 2013 at 0:32
  • 3
    $\begingroup$ Why would $\bigcup_{w\in L} \{w\}$ be RE? $\endgroup$ Nov 12, 2013 at 0:36
  • $\begingroup$ @HendrikJan: I realize that my answer might sound stupid, but would you mind explaining why it is not RE? My professor is not very good at explaining the material and I would greatly appreciate any help. $\endgroup$
    – flashburn
    Nov 12, 2013 at 0:38
  • $\begingroup$ Not every language $L$ is RE. $\endgroup$ Nov 12, 2013 at 0:41

1 Answer 1


Choose an arbitrary language $L$ that is not RE. Denote $L_w=\{w\}$ the language containing a single word $w$. Clearly, $L=\bigcup_{w\in L} L_w$ is a union of infinitely many regular and recursive languages.

  • $\begingroup$ I think I'm missing something. I realize that this question might sound strange to someone but as I said my professor is not very good at explaining the material. My question is why I can make an assumption that I can choose a non RE language such that it is a union of regular languages? $\endgroup$
    – flashburn
    Nov 12, 2013 at 13:39
  • $\begingroup$ @flashburn, I'm disproving the statement "for all infinite sets of recursive languages, their union is RE" by showing a counterexample. In this case, I'm saying "look, here's one concrete language $L$ and and infinite set of regular languages $L_w$ whose union is $L$". Sure, I didn't actually say what $L$ is, but that's not really a problem -- all you need to prove is that there is at least one (and we kinda know that there is :) ). $\endgroup$
    – avakar
    Nov 12, 2013 at 14:27
  • $\begingroup$ @flashburn This works for the following reason: (1) Not every language is RE; (2) Every language can be expressed as an infinite union of languages containing a single word; (3) therefore, there are languages that are not RE that can be expressed as an infinite union of languages containing a single word. Similarly: (1) Not all mammals are people; (2) All mammals are living things; (3) therefore, there are mammals that aren't people that are living things. $\endgroup$
    – Patrick87
    Nov 12, 2013 at 20:18

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.