# Infinite union of recursive languages

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.

• Consider the infinite usion of languages of the form $\{w\}$, i.e., each containing a single word. – Hendrik Jan Nov 12 '13 at 0:29
• @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). – flashburn Nov 12 '13 at 0:32
• Why would $\bigcup_{w\in L} \{w\}$ be RE? – Hendrik Jan Nov 12 '13 at 0:36
• @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. – flashburn Nov 12 '13 at 0:38
• Not every language $L$ is RE. – Hendrik Jan Nov 12 '13 at 0:41

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.
• @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 :) ). – avakar Nov 12 '13 at 14:27