2
$\begingroup$

I'm trying to get some notion of how "many" recursively enumerable sets there are.

Here's one way of formalizing the question: consider $S =\{q: q\in Q\cap [0,1]\}$ and $R\subset S$ the set of recursively innumerable subsets of $S$.

What is the measure of $R$? My intuition is that it is 0 (i.e. a given set is almost surely not RE), but I am having difficulty proving it.

$\endgroup$
3
$\begingroup$

Countably infinite. Each RE set corresponds to a TM $M$ recognizing that RE set, where the set of all TMs is countably infinite.

$\endgroup$
  • $\begingroup$ Ah, right, so it has measure zero. $\endgroup$ – Xodarap Aug 21 '17 at 21:30
  • $\begingroup$ Not only that, there are computably countably infinitely many r.e. sets. $\endgroup$ – Andrej Bauer Aug 22 '17 at 16:29
  • $\begingroup$ @AndrejBauer thanks for feedback, could you give me a reference to the definition of computably countably (infinite) set? $\endgroup$ – fade2black Aug 22 '17 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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