3
$\begingroup$

Is the cardinality of the set of partially recursive functions greater than the cardinality of the set of recursive functions ?

$\endgroup$
7
$\begingroup$

No they have the same cardinality. They have the cardinality $\aleph_0$. Both sets are infinite in size so we have to compare them based on their level of infiniteness, since as we know there are infinite levels of infinity. Both sets are countably infinite so we say they have the same cardinality.

To expand on this and show why this is the case:

The set of partially recursive functions are infinite by design. Also they are computable, so by the Church-Turing thesis they are solvable by a Turing machine. Since there are only countably infinite Turing machines there can only be countably infinite partial recursive functions.

The same argument can be used on the set of recursive functions.

$\endgroup$
  • $\begingroup$ Do you know how to proof this, @lPlant ? I mean, formally. I research about and maybe we can construct a bijection between sets and the natural numbers, but I dont know how to construct such bijection. $\endgroup$ – chgsilva Sep 22 '14 at 3:24
  • 1
    $\begingroup$ I expanded to provide a reasoning for this. This is a case where the strangeness of infinite comes into play. We can see functions in one set but not the other but since they are infinite the cardinality is said to be the same. $\endgroup$ – lPlant Sep 22 '14 at 3:31
  • $\begingroup$ @chgsilva Any encoding of TMs into the naturals suffices (it does not have to be bijective for this purpose here). Such are (or should be) given in every computability textbook since they are essential to the theory (we even need special encodings, so-called Gödel numberings). $\endgroup$ – Raphael Sep 22 '14 at 6:41
  • $\begingroup$ Maybe a better way is to observe that they are both represented by finite strings. The set of all finite strings is countable. Both classes are at most countable. Seeing also that for any natural number $c$, you have the constant function $f_c:x \mapsto c$, gives that both sets are infinite. Hence both classes are infinite and countable. $\endgroup$ – Pål GD Sep 22 '14 at 20:41

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.