Does recursive enumeration implies countability? Does countability implies recursive enumeration?

I believe the first implication holds but not sure about the second. A good example would suffice.


If a language is recursively enumerable then it is countable. However, there are languages that are countable but not recursively enumerable. For example, consider the $A_{TM}$, the language of the Halting problem. This language is recursively enumerable while its complement $\Sigma^*-A_{TM}$ is not recursively enumerable, otherwise $A_{TM}$ would be decidable. However, $\Sigma^*-A_{TM}$ is clearly countable since it is a subset of a countable set $\Sigma^*$.

Hence one simple relation between countability and enumeration is that every r.e. set is countable, but the opposite is not always true.

| cite | improve this answer | |
  • $\begingroup$ sir first of all thanks for your awesome answer..I have a small query that -: "if a language is Recursive enumerable then it may be infinitely uncountable " ? $\endgroup$ – laura Jan 5 '18 at 15:59
  • $\begingroup$ @laura First of all the word "infinitely" in "infinitely uncountable" is redundant. If a set is uncountable it is already infinite since any finite set is countable. Second, if a language is recursively enumerable then it is countable. As its name "enumerable" implies this set can be enumerated, i.e., put in one to one correspondence with a set of a natural numbers, and hence countable. $\endgroup$ – fade2black Jan 5 '18 at 17:19
  • $\begingroup$ sir can we conclude that any language is a subset of $\sum ^ {*}$ and as $\sum ^ {*}$ is countable so a non Recrsive enumerable is countable too ? $\endgroup$ – laura Jan 5 '18 at 20:57
  • $\begingroup$ @laura Assuming that $\Sigma$ is finite, any subset (language) of $\Sigma^*$ is countable. It is also countable even when $\Sigma$ is infinitely countable. $\endgroup$ – fade2black Jan 5 '18 at 21:02

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