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$

1 Answer 1

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$
3
  • $\begingroup$ Ah, right, so it has measure zero. $\endgroup$
    – Xodarap
    Aug 21, 2017 at 21:30
  • $\begingroup$ Not only that, there are computably countably infinitely many r.e. sets. $\endgroup$ Aug 22, 2017 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, 2017 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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