Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

3 Answers 3

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.

share|improve this answer

aleph naught, right? The set can be covered by the set of halting turing machine programs.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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