URM Instructions are Countably Infinite
Jump to navigation
Jump to search
Theorem
The set $\Bbb I$ of all basic URM instructions is countably infinite.
Proof
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.
$\blacksquare$