Pairing and tupling functions are primitive recursive

Show that the $\tau_{1}$ is onto, primitive recursive and monotone. Also show that $\tau_{1}$ is almost one-to-one in the sense that if $\tau_{1}\left(n_{1}, \ldots , n_{k}\right)=\tau_{1}\left(m_{1}, \ldots , m_{\ell }\right)$, and if $k \leq \ell$, then $n_{i}=m_{i}$ for all $i, 1 \leq i \leq k$, and $m_{j}=0$ for all $j, k<j \leq \ell$.

Verify that if we use $\tau_{1}$ as a Gödel numbering, then the functions size, item and the functions of Example 4.35 all remain primitive recursive. (Here, $\operatorname {size}(n)$ is the number of items in the sequence $n$, excluding the trailing zeros.)

Prove that the function

(the Cantor pairing function) is a bijection between $\mathbb {N}^{2}$ and $\mathbb {N}$ (i.e., it numbers pairs of natural numbers).

Let $l(x)$ and $r(x)$ be such that

Prove that $l(x)$ and $r(x)$ are primitive recursive and $l(c(x, y)) = x$, $r(c(x, y)) = y$.

Prove the identities

Prove that the functions $c^{n}$ and $c_{i}^{n}$ are primitive recursive.

Prove that the functions $c^{n}(x_{1}, \ldots , x_{n})$ are bijections between $\mathbb {N}^{n}$ and $\mathbb {N}$ (i.e., they number $n$-tuples of natural numbers).

Let the pair of functions $\langle f_{1}(x), f_{2}(x) \rangle$ map $\mathbb {N}$ onto $\mathbb {N}^{2}$. Prove that $f_{1}(x)$ and $f_{2}(x)$ are functions of large spread.

Let $f_{1}(x)$ be an arbitrary primitive recursive function of large spread. Construct a primitive recursive function $f_{2}(x)$ so that the functions $f_{1}(x)$ and $f_{2}(x)$ form a bijection between $\mathbb {N}$ and $\mathbb {N}^{2}$.