What is the cardinality of the set of recursive subsets of natural numbers?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
It is $\aleph_0$. There are $\aleph_0$ many Turing Programs. Partial Computable functions correspond to Turing programs. The c.e. sets are the domains of partial computable functions. Thus there are at most $\aleph_0$ c.e. sets. The computable (recursive) sets are among the c.e. sets. Of course there are infinitely many computable sets (for example each finite set), thus, the cardinality of the computable sets is $\aleph_0$.
In another perspective, the number of Turing machines is $\aleph_0$. The computable sets corresponds to those Turing Machines that halt on all input.
aleph naught, right? The set can be covered by the set of halting turing machine programs.
First, I'll use 'computable' and 'c.e.' instead of 'recursive' and 'r.e.', respectively. When I say 'countable', I mean 'countably infinite'.
As William Chan said, the answer is countable because there are at most countably many c.e. sets and computable sets are c.e. Then, every finite set is computable and so the cardinality must be at least countable as well (since there are countably many finite sets) . Thus there are at most and at least countably many computable sets and hence there must be exactly countably many computable sets. I will explain why there are at most countably many c.e. sets.
A c.e. set is the domain of a (partial) computable function. Every computable function is described by a Turing machine program. Since these programs are finite strings over a finite alphabet, there can be at most countably many of them.