0
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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}$.

$\endgroup$
  • $\begingroup$ i think i phrased the question slightly wrong. what i was essentially asking was:can u have a recursive language which is uncountable? can u have a r.e but not recursive language which is uncountable? can u have a non r.e language which is countable? ill edit the question $\endgroup$ – Csbk Apr 28 '17 at 23:02
  • 1
    $\begingroup$ In that case, this is a duplicate of the question I linked. All languages over finite alphabets are countable. $\endgroup$ – jmite Apr 28 '17 at 23:10

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