URM Computable Functions of One Variable is Countably Infinite

From ProofWiki
Jump to navigation Jump to search


The set $\mathbf U$ of all URM computable functions of $1$ variable is countably infinite.


Let $\mathbf U$ be the set of all URM computable functions.

For each $f \in \mathbf U$, let $P_f$ be a URM program which computes $f$.

Such a program is very probably not unique, so in order to be definite about it, we can pick $P_f$ to be the URM program with the smallest code $\gamma \left({P_f}\right)$.

This is possible from the Well-Ordering Principle.

Let us define the function $h: \mathbf U \to \N$ as:

$h \left({f}\right) = \gamma \left({P_f}\right)$

Since the same URM program can not compute two different functions of $1$ variable, it can be seen that $h$ is injective.

The result follows from Domain of Injection to Countable Set is Countableā€Ž.