# Cardinality of the recursive subsets of the naturals

What is the cardinality of the set of recursive subsets of natural numbers?

-
You might also want to refer to JDH's answer on this question –  Asaf Karagila Aug 16 '11 at 12:26

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.

-