# 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. Commented Sep 22, 2014 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.
• 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. Commented Sep 22, 2014 at 20:41