# 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

## 1 Answer

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.

• 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? – flashburn Nov 12 '13 at 13:39
• @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
• @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. – Patrick87 Nov 12 '13 at 20:18