# What is the relation between countability and recursive enumeration? [duplicate]

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.

## marked as duplicate by David Richerby, Evil, Yuval Filmus, Luke Mathieson, Rick DeckerDec 13 '17 at 17:32

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^*$.
• 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 ? – laura Jan 5 '18 at 20:57
• @laura Assuming that $\Sigma$ is finite, any subset (language) of $\Sigma^*$ is countable. It is also countable even when $\Sigma$ is infinitely countable. – fade2black Jan 5 '18 at 21:02