cardinality of recursive/r.e/not r.e languages? [duplicate]

Question

I was just looking into properties of languages and wondered about the cardinality of them

• are all recursive languages countable or can they also be uncountable (can u have a recursive language which is uncountable?)

• can r.e languages be countable and uncountable? (can u have a r.e but not recursive language which is uncountable?)

• are all non r.e languages uncountable? (can u have a non r.e language which is countable?)

an explanation would be nice but i am not necessarily looking for a proof. thanks!

Answer 1

I assume you're talking about the cardinality of the sets $R$, $RE$, and $\overline{RE}$, as the set of all words in a language is always countable.

• $R$ (the family of recursive langauges) is countable, because there the set of Turing Machines is countable, and there is at least one TM for each $R$ language.
• $RE$ is countable, by the same logic, since there is a TM semi-deciding each $RE$ language.

• The set of non-$RE$ languages, $\overline{RE}$, is not countable, then by process of elimination. The set of all languages, $\mathcal{L}$, over an alphabet $\Sigma$ is $\mathcal{P}(\Sigma^*)$ i.e. the powerset of the set of all words. This set is uncountable, since $\Sigma^*$ is countable, and the powerset of a set always has higher cardinality.

  $\mathcal{L} = RE \cup \overline{RE}$, and $RE$ and its complement are disjoint, so since $RE$ is a countable subset, there must be an uncountable number of words in $\overline{RE}$.