Math Problems Vault

Example 4.32

Show that the function $\pi : \mathbf{N}^{2} \rightarrow \mathbf{N}$ , defined by

\pi (i, j)=\frac{(i+j)(i+j+1)}{2}+j,

is a pairing function.

?

Example 4.33

Show that the Fibonacci function is primitive recursive.

?

Example 4.34

Show that the function

\tau \left(n_{1}, \ldots , n_{k-1}, n_{k}\right)=\left\langle k-1,\left\langle n_{1},\left\langle \cdots \left\langle n_{k-1}, n_{k}\right\rangle \cdots \right\rangle \right\rangle \right\rangle

is a Gödel numbering.

?

Example 4.35

Show that the following functions are primitive recursive:

?

(a)

$\operatorname {list}(m, 0)=0$ and $\operatorname {list}(m, k)=[\underbrace{m, m, \ldots , m}_{k}]$ , if $k \geq 1$ .

(b)

$\operatorname {find}\left(\left[n_{1}, \ldots , n_{k}\right], m\right)= \begin{cases} \min \left\{ i \mid 1 \leq i \leq k, n_{i}=m\right\} & \text{ if such an } i \text{ exists }, \\ 0 & \text{ otherwise } \end{cases}$

(c)

$\operatorname {replace}\left(\left[n_{1}, \ldots , n_{k}\right], m, i\right) = \begin{cases} \left[n_{1}, \ldots , n_{i-1}, m, n_{i+1}, \ldots , n_{k}\right] & \text{ if } 1 \leq i \leq k, \\ \left[n_{1}, \ldots , n_{k}\right] & \text{ otherwise. } \end{cases}$

(d)

$\operatorname {conseq}\left(\left[n_{1}, \ldots , n_{k}\right],\left[m_{1}, \ldots , m_{\ell }\right]\right)=\left[n_{1}, \ldots , n_{k}, m_{1}, \ldots , m_{\ell }\right]$ .

(e)

$\operatorname {subseq}\left(\left[n_{1}, \ldots , n_{k}\right], i, \ell \right)$

= \begin{cases} {\left[n_{i}, n_{i+1}, \ldots , n_{i+\ell -1}\right]} & \text{ if } 1 \leq i \leq k, 1 \leq \ell \leq k-i+1 \\ 0 & \text{ otherwise. }\end{cases}

Example 4.36

Show that the function $f: \mathbf{N} \rightarrow \mathbf{N}$ , defined by $f(0)=1$ , $f(n+1)=f(0)^{n+1}+f(1)^{n}+\ldots +f(n)^{1}$ , is primitive recursive.

?

Example 4.38

The function sort : $\mathbf{N} \rightarrow \mathbf{N}$ maps a number $\left[n_{1}, n_{2}, \ldots , n_{k}\right]$ to the number $\left[n_{p_{1}}, n_{p_{2}}, \ldots , n_{p_{k}}\right]$ , where $\left(p_{1}, p_{2}, \ldots , p_{k}\right)$ is a permutation of $(1,2, \ldots , k)$ such that $n_{p_{1}} \leq n_{p_{2}} \leq \cdots \leq n_{p_{k}}$ . Show that sort is primitive recursive.

?

Problem 4.7.1

(a)(b)

Show that the following functions are pairing functions.

?

(a)

$f_{1}(n, m)=2^{n}(2 m+1)-1$ .

(b)

$f_{2}(n, m)=\max (n, m)^{2}+m+g(m, n)$ , where $g(m, n)=n$ if $m \geq n$ , and $g(m, n)=0$ if $n>m$ .

Problem 4.7.2

(a)(b)

Let $\tau_{1}: \bigcup_{k=1}^{\infty } \mathbf{N}^{k} \rightarrow \mathbf{N}$ be defined by $f\left(n_{1}, \ldots , n_{k}\right)=2^{n_{1}} 3^{n_{2}} \cdots p_{k}^{n_{k}}$ , where $p_{k}$ is the $k$ th prime.

?

(a)

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

(b)

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.)

Problem 4.7.3

Let $n_{1}, n_{2}, \ldots , n_{k}$ are $k$ nonnegative integers. Prove that if $1 \leq i_{1}< i_{2}<\cdots <i_{\ell } \leq k$ , then $\left[n_{i_{1}}, n_{i_{2}}, \ldots , n_{i_{\ell }}\right] \leq \left[n_{1}, n_{2}, \ldots , n_{k}\right]$ .

?

Problem 4.7.4

Assume that $f(n, 0)=g(n)$ and $f(n, m+1)=h(n, f(n, k(m)))$ for some primitive recursive $g, h$ and $k$ . Also assume that $k(m) \leq m$ for all $m>0$ . Prove that $f$ is also primitive recursive. (Note that Solution 1 of Example 4.38 actually used this result.)

?

Problem 4.7.5

(a)(b)

Show that the following functions are primitive recursive:

?

(a)

$f(n, m)=$ the number of occurrences of integer $m$ in the sequence $n=\left[n_{1}, \ldots , n_{k}\right]$ .

(b)

$g(n)=\left[d_{k}, d_{k-1}, \ldots , d_{0}\right]$ , where $d_{k} d_{k-1} \cdots d_{0}$ is the decimal representation of $n$ (e.g., $g(2801)=[2,8,0,1]$ ).

Problem 4.7.6

(a)(b)

We may extend the notion of primitive recursive functions to functions from $\mathbf{Z}^{k}$ to $\mathbf{Z}$ , where $\mathbf{Z}$ is the set of integers. All we need is to treat a pair $\left\langle n_{1}, n_{2}\right\rangle$ as a represention of an integer in $\mathbf{Z}$ : If $n_{1}>0$ , then it represents $n_{2}$ , otherwise it represents $-n_{2}$ . Show that the following functions on integers are primitive recursive:

?

(a)

$\operatorname {inner}(n, m)=$ the inner product of two $k$ -dimensional vectors $n$ and $m$ , if $\operatorname {size}(n)=\operatorname {size}(m)=2 k$ (and it is 0, otherwise). (We treat a list $\left[n_{1}, n_{2}, \ldots , n_{2 k}\right]$ as a $k$ -dimensional integer vector whose $i$ th element is the integer represented by $\left\langle n_{2 i-1}, n_{2 i}\right\rangle$ ; that is, it is $n_{2 i}$ if $n_{2 i-1}>0$ , and is $-n_{2 i}$ if $n_{2 i-1}=0$ .)

(b)

$\operatorname {det}(n)=$ the determinant of the matrix $n$ if $\operatorname {size}(n)=2 k^{2}$ for some $k \geq 1$ (and it is 0 otherwise). (We treat $\left[n_{1}, n_{2}, \ldots , n_{2 k^{2}}\right]$ as a $k \times k$ integer matrix $M$ with $M_{i j}$ equal to the integer represented by the pair $\left\langle n_{2(i-1) k+2 j-1}, n_{2(i-1) k+2 j}\right\rangle$ .)

Problem 4.7.7

We say a sequence $n=\left[n_{1}, \ldots , n_{k}\right]$ is balanced if there exists a partition of $\left\{ 1,2, \ldots , k\right\}$ into two subsets $B$ and $C$ (i.e., $B \cup C=\left\{ 1,2, \ldots , k\right\}$ and $B \cap C=\emptyset$ ) such that $\sum_{i \in B} n_{i}=\sum_{j \in C} n_{j}$ . Prove that the predicate $[n$ is balanced] is primitive recursive.

?

Problem 4.7.8

(a)(b)

?

(a)

Show that the function $\operatorname {merge}(n, m)$ that merges two sorted sequences into a single sorted sequence (and output 0 if any of the two inputs is not sorted) is primitive recursive.

(b)

Prove that sort is primitive recursive using the algorithm of merge sort.

Problem 4.7.9

Assume that $g: \mathbf{N} \rightarrow \mathbf{N}$ and $h: \mathbf{N}^{2} \rightarrow \mathbf{N}$ are two primitive recursive functions. Show that the following function $f$ is primitive recursive:

\begin{aligned} f(0, n) & =g(n) \\ f(m+1, n) & =f(m, h(m, n)) \end{aligned}

?

Problem 4.7.10

Assume that $g_{1}, g_{2}$ and $h$ are all primitive recursive. Show that the following function $f$ is primitive recursive:

\begin{aligned} f(0, n) & =g_{1}(n) \\ f(m+1,0) & =g_{2}(m) \\ f(m+1, n+1) & =h(m, n, f(m+1, n), f(m, n+1)) \end{aligned}

?

Problem 4.7.11

Assume that $g_{1}, g_{2}$ and $h$ are all primitive recursive. Show that the following function $f$ is primitive recursive:

\begin{aligned} f(0, n) & =g_{1}(n) \\ f(m+1,0) & =g_{2}(m) \\ f(m+1, n+1) & =h(m, n, f(m, n), f(n, m), f(m, m), f(n, n)) \end{aligned}

?

Problem 4.7.12

Assume that $g_{1}, g_{2}, h_{1}$ and $h_{2}$ are all primitive recursive. Let $f_{1}$ and $f_{2}$ be functions defined by the following formulas:

\begin{aligned} f_{1}(m, 0) & =g_{1}(m) \\ f_{2}(m, 0) & =g_{2}(m) \\ f_{1}(m, n+1) & =h_{1}\left(m, n, f_{1}(m, n), f_{2}(m, n)\right) \\ f_{2}(m, n+1) & =h_{2}\left(m, n, f_{1}(m, n), f_{2}(m, n)\right) \end{aligned}

Show that both $f_{1}$ and $f_{2}$ are primitive recursive:

?