Not All Natural Number Functions are Primitive Recursive

Theorem

Not all functions $f: \N \to \N$ are primitive recursive.

Proof

All primitive recursive functions are URM computable.

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

The set of $\Bbb F$ of natural number functions is uncountably infinite.

Hence there is no surjection from $\mathbf U \to \Bbb F$.

Hence $\mathbf U \subsetneq \Bbb F$.

Hence $\exists f \in \Bbb F: f \notin \mathbf U$.

$\blacksquare$