URM Programs are Countably Infinite

From ProofWiki
Jump to navigation Jump to search

Theorem

The set $\mathbf P$ of all URM programs is countably infinite.


Proof

We can immediately see that $\mathbf P$ is infinite as the number of URM instructions is infinite.


From Unique Code for URM Program, we see that $\gamma: \mathbf P \to \N$ is also an injection.

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

$\blacksquare$