# Are there more partially recursive functions than and recursive functions?

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

• What have you tried and where did you get stuck? Note also this closely related question.
– Raphael
Sep 22 '14 at 6:37

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.

• 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. Sep 22 '14 at 3:24
• 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. Sep 22 '14 at 3:31
• @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).
– Raphael
Sep 22 '14 at 6:41
• 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. Sep 22 '14 at 20:41