URM Instructions are Countably Infinite

From ProofWiki
Jump to navigation Jump to search


The set $\Bbb I$ of all basic URM instructions is countably infinite.


We can immediately see that $\Bbb I$ is infinite as, for example, $\phi: \N \to \Bbb I$ defined as:

$\phi \left({n}\right) = Z \left({n}\right)$

is definitely injective.

From Unique Code for URM Instruction, we see that $\beta: \Bbb I \to \N$ is also an injection.

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