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.
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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.
answered Dec 13, 2017 at 5:05
-
$\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$– lauraCommented Jan 5, 2018 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$ Commented Jan 5, 2018 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$– lauraCommented Jan 5, 2018 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$ Commented Jan 5, 2018 at 21:02