# 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$