Math Problems Vault

Problem III.1.1

Prove that every primitive recursive function is everywhere defined.

?

Problem III.1.2

(a)(b)(c)(d)

Prove that if the function $f^{n}(x_{1}, \ldots , x_{n})$ is primitive recursive, then the following functions are primitive recursive:

?

(a)

$f_{1}(x_{1}, x_{2}, \ldots , x_{n}) = f(x_{2}, x_{1}, \ldots , x_{n})$ (permutation of arguments);

(b)

$f_{2}(x_{1}, x_{2}, \ldots , x_{n}) = f(x_{2}, \ldots , x_{n}, x_{1})$ (cyclic permutation of arguments);

(c)

$f_{3}(x_{1}, \ldots , x_{n}, x_{n+1}) = f(x_{1}, \ldots , x_{n})$ (introduction of a dummy argument);

(d)

$f_{4}(x_{1}, \ldots , x_{n-1}) = f(x_{1}, x_{1}, \ldots , x_{n-1})$ (identification of arguments).

Problem III.1.3

Which functions are obtained from the simplest functions using superpositions alone?

?

Problem III.1.4

Prove that the functions $x+1$ and $2x$ cannot be obtained from $o^{1}$ and $I_{m}^{n}$ using superpositions and primitive recursion schemes.

?

Problem III.1.5

Prove that the following functions are primitive recursive:

?

(a)

$f(x) = x + n$ ;

(b)

$f(x) = n$ ;

(c)

$f(x, y) = x + y$ ;

(d)

$f(x, y) = x \cdot y$ ;

(e)

$f(x, y) = x^{y}$ (here $0^{0} = 1$ );

(f)

$f(x, y) = x!$ (here $0! = 1$ ).

Problem III.1.6

(a)(b)

Which function is obtained from $g$ and $h$ by means of the primitive recursion scheme:

?

(a)

$g(x) = x$ , $h(x, y, z) = z^{x}$ ;

(b)

$g(x) = x$ , $h(x, y, z) = x^{z}$ ?

Problem III.1.7

Prove that the following functions are primitive recursive:

?

(a)

$\operatorname {sg}(x) = \begin{cases} 0, & \text{if } x = 0, \\ 1, & \text{if } x > 0; \end{cases}$

(b)

$\overline{\operatorname {sg}}(x) = \begin{cases} 0, & \text{if } x > 0, \\ 1, & \text{if } x = 0; \end{cases}$

(c)

$x \symdiff 1 = \begin{cases} 0, & \text{if } x = 0, \\ x - 1, & \text{if } x > 0; \end{cases}$

(d)

$x \symdiff y = \begin{cases} 0, & \text{if } x \leq y, \\ x - y, & \text{if } x > y; \end{cases}$

(e)

$\left|x - y\right|$ ;

(f)

$\max (x, y)$ ;

(g)

$\min (x, y)$ .

Problem III.1.8

(a)(b)(c)(d)

Prove the following identities:

?

(a)

$x \symdiff y = s(x) \symdiff s(y)$ ;

(b)

$x + (y \symdiff x) = y + (x \symdiff y)$ ;

(c)

$x \symdiff (y+z) = (x \symdiff y) \symdiff z$ ;

(d)

$(x \symdiff y) \symdiff z = (x \symdiff z) \symdiff y$ .

Problem III.1.9

Let $g^{n+1}, \alpha^{m}, \beta^{m}$ be primitive recursive functions. Prove that the following functions are primitive recursive:

?

(a)

$f^{n+1}(x_{1}, \ldots , x_{n}, x_{n+1}) = \displaystyle \sum_{i=0}^{x_{n+1}} g(x_{1}, \ldots , x_{n}, i)$ ;

(b)

$f^{n+2}(x_{1}, \ldots , x_{n}, y, z) = \begin{cases} \displaystyle \sum_{i=y}^{z} g(x_{1}, \ldots , x_{n}, i), & \text{if } y \leq z, \\ 0, & \text{if } y > z; \end{cases}$

(c)

$f^{n+m}(x_{1}, \ldots , x_{n}, y_{1}, \ldots , y_{m}) = \begin{cases} \displaystyle \sum_{i=\alpha (y_{1}, \ldots , y_{m})}^{\beta (y_{1}, \ldots , y_{m})} g(x_{1}, \ldots , x_{n}, i), & \text{if } \alpha (y_{1}, \ldots , y_{m}) \leq \beta (y_{1}, \ldots , y_{m}), \\ 0, & \text{otherwise;} \end{cases}$

(d)

$f^{n+1}(x_{1}, \ldots , x_{n}, x_{n+1}) = \displaystyle \prod_{i=0}^{x_{n+1}} g(x_{1}, \ldots , x_{n}, i)$ ;

(e)

$f^{n+2}(x_{1}, \ldots , x_{n}, y, z) = \begin{cases} \displaystyle \prod_{i=y}^{z} g(x_{1}, \ldots , x_{n}, i), & \text{if } y \leq z, \\ 0, & \text{if } y > z; \end{cases}$

(f)

$f^{n+m}(x_{1}, \ldots , x_{n}, y_{1}, \ldots , y_{m}) = \begin{cases} \displaystyle \prod_{i=\alpha (y_{1}, \ldots , y_{m})}^{\beta (y_{1}, \ldots , y_{m})} g(x_{1}, \ldots , x_{n}, i), & \text{if } \alpha (y_{1}, \ldots , y_{m}) \leq \beta (y_{1}, \ldots , y_{m}), \\ 0, & \text{otherwise.} \end{cases}$

Problem III.1.10

Prove that if $f$ is obtained from primitive recursive functions $g$ and $h$ by means of the bounded $\mu$ -operator, then $f$ is primitive recursive.

?

Problem III.1.11

Let the functions $f_{0}^{n}, f_{1}^{n}, \ldots , f_{s}^{n}$ have the following property: for any natural values $x_{1}, \ldots , x_{n}$ , one and only one of these functions equals $0$ . We say that the function $g^{n}$ is defined by cases, if

g^{n}(x_{1}, \ldots , x_{n}) = \begin{cases} h_{0}^{n}(x_{1}, \ldots , x_{n}), & \text{if } f_{0}^{n}(x_{1}, \ldots , x_{n}) = 0, \\ \makebox[0pt][l]{\dotfill } \\ h_{s}^{n}(x_{1}, \ldots , x_{n}), & \text{if } f_{s}^{n}(x_{1}, \ldots , x_{n}) = 0. \end{cases}

Prove that if the functions $h_{0}^{n}, \ldots , h_{s}^{n}, f_{0}^{n}, \ldots , f_{s}^{n}$ are primitive recursive, then $g^{n}$ is primitive recursive.

?

Problem III.1.12

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

(k)

(l)

(m)

(n)

(o)

(p)

(q)

Problem III.1.13

(a)(b)

?

(a)

Prove that the function

c(x, y) = \frac{(x+y)^{2} + 3x + y}{2}

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

(b)

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

c(l(x), r(x)) = x.

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

Problem III.1.14

(a)(b)(c)

For each $n \geq 1$ define the functions

c^{1}(x_{1}) = x_{1}, \qquad c^{n+1}(x_{1}, x_{2}, x_{3}, \ldots , x_{n+1}) = c^{n}(c(x_{1}, x_{2}), x_{3}, \ldots , x_{n+1})

(see problem III.1.13).

Let $c_{i}^{n}$ ( $1 \leq i \leq n$ ) be such that $c^{n}(c_{1}^{n}(x), \ldots , c_{n}^{n}(x)) = x$ .

?

(a)

Prove the identities

c_{i}^{n}(c^{n}(x_{1}, \ldots , x_{n})) = x_{i} \ \text{for } 1 \leq i \leq n.

(b)

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

(c)

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

Problem III.1.15

How can all partial recursive functions be obtained from one-place partial recursive functions and the functions $c^{n}(x_{1}, \ldots , x_{n})$ ?

?

Problem III.1.16

(a)(b)

Call a one-place function $f(x)$ a function of large spread, if it takes on every natural number as its value infinitely many times.

?

(a)

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.

(b)

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

Problem III.1.17

Consider the Godel function

\beta (x, y, z) = \operatorname {rest}(x, 1 + y(z+1)).

Prove that, whatever the finite sequence of natural numbers $a_{1}, \ldots , a_{n}$ may be, the system of equations

\begin{cases} \beta (x, y, 0) = \alpha _{0}, \\ \makebox[0pt][l]{\dotfill } \\ \beta (x, y, n) = \alpha _{n}, \end{cases}

has at least one solution $x, y$ .

?

Problem III.1.18

Prove that if the functions $g, h, t_{1}, \ldots , t_{s}$ are primitive recursive and $f$ is obtained from them by course-of-values recursion with delays, then the function $f$ is primitive recursive.

?

Problem III.1.19

Prove that the function enumerating the Fibonacci numbers in order:

\begin{cases} f(0) = 0, \quad f(1) = 1, \\ f(n+2) = f(n) + f(n+1), \end{cases}

is primitive recursive.

?

Problem III.1.20

Let the functions $f$ and $g$ be defined as follows:

\begin{cases} f(0) = a, \quad g(0) = b, \\ f(x+1) = h_{1}(x, f(x), g(x)), \\ g(x+1) = h_{2}(x, f(x), g(x)). \end{cases}

Prove that if the functions $h_{1}$ and $h_{2}$ are primitive recursive, then the functions $f$ and $g$ are primitive recursive.

?

Problem III.1.21

Let $f_{1}^{n+1}, \ldots , f_{k}^{n+1}$ be defined by means of simultaneous recursion:

\begin{cases} f_{i}^{n+1}(x_{1}, \ldots , x_{n}, 0) = g_{i}^{n}(x_{1}, \ldots , x_{n}), \\ f_{i}^{n+1}(x_{1}, \ldots , x_{n}, y+1) = \\ \hphantom {f_{i}^{n+1}(x_{1}, \ldots , x_{n}, y+1) =} \, h_{i}^{n+k+1}(x_{1}, \ldots , x_{n}, y, f_{1}(x_{1}, \ldots , x_{n}, y), \ldots , f_{k}(x_{1}, \ldots , x_{n}, y)) \end{cases}

for all $1 \leq i \leq k$ .

Prove that if the functions $g_{1}, \ldots , g_{k}, h_{1}, \ldots , h_{k}$ are primitive recursive, then the functions $f_{1}, \ldots , f_{k}$ are primitive recursive.

?

Problem III.1.22

Prove that every primitive recursive function is general recursive.

?

Problem III.1.23

(a)(b)(c)

?

(a)

Prove that the superposition of general recursive functions is a general recursive function.

(b)

Prove that applying the primitive recursion operator to general recursive functions yields a general recursive function.

(c)

Give an example of a general recursive function from which the $\mu$ -operator yields a function that is not general recursive.

Problem III.1.24

(a)(b)(c)(d)

Prove that if the function $f(x_{1}, \ldots , x_{n})$ is partial recursive, then the following functions are partial recursive:

?

(a)

$f_{1}(x_{1}, x_{2}, \ldots , x_{n}) = f(x_{2}, x_{1}, \ldots , x_{n})$ (permutation of arguments);

(b)

$f_{2}(x_{1}, x_{2}, \ldots , x_{n}) = f(x_{2}, \ldots , x_{n}, x_{1})$ (cyclic permutation of arguments);

(c)

$f_{3}(x_{1}, \ldots , x_{n}, x_{n+1}) = f(x_{1}, \ldots , x_{n})$ (introduction of a dummy argument);

(d)

$f_{4}(x_{1}, \ldots , x_{n-1}) = f(x_{1}, x_{1}, \ldots , x_{n-1})$ (identification of arguments).

Problem III.1.25

(a)(b)(c)

Prove that:

?

(a)

there are exactly $\aleph_{0}$ partial recursive functions;

(b)

there is a partial numerical function that is not partial recursive;

(c)

there is an everywhere defined numerical function that is not general recursive.

Problem III.1.26

Prove that the following functions are partial recursive:

?

(a)

the nowhere defined function $\omega$ , i.e., the function $\omega$ with empty domain of definition;

(b)

$f(x, y) = \begin{cases} x - y, & \text{if } x \geq y, \\ \text{undefined otherwise}; \end{cases}$

(c)

$f(x, y) = \begin{cases} \dfrac {x}{y}, & \text{if } y \text{ divides } x, \\ \text{undefined otherwise}; \end{cases}$

(d)

$f(x, y) = \begin{cases} z, & \text{if } z^{y} = x, \\ \text{undefined otherwise}; \end{cases}$

(e)

a function defined at finitely many points.

Problem III.1.27

Prove that if the functions $g^{n+1}, h^{n+1}$ , and $t^{n+1}$ are partial recursive, then the following functions are partial recursive:

?

(a)

$\mu y \left[g(x_{1}, \ldots , x_{n}, y) = h(x_{1}, \ldots , x_{n}, y)\right]$ ;

(b)

$\mu y \left[g(x_{1}, \ldots , x_{n}, y) \neq h(x_{1}, \ldots , x_{n}, y)\right]$ ;

(c)

$\mu y \left[g(x_{1}, \ldots , x_{n}, y) \leq h(x_{1}, \ldots , x_{n}, y)\right]$ ;

(d)

$\mu y \left[g(x_{1}, \ldots , x_{n}, y) < h(x_{1}, \ldots , x_{n}, y)\right]$ ;

(e)

$\mu y \left[g(x_{1}, \ldots , x_{n}, y) = 0 \text{ and } h(x_{1}, \ldots , x_{n}, y) = 0\right]$ ;

(f)

$\mu y \left[g(x_{1}, \ldots , x_{n}, y) = 0 \text{ or } h(x_{1}, \ldots , x_{n}, y) \leq t(x_{1}, \ldots , x_{n}, y)\right]$ .

Problem III.1.28

(a)(b)

?

(a)

Prove that the function $f^{n+1}$ , arising from the partial functions $g^{n}$ and $h^{n+2}$ by means of the primitive recursion operator, can be obtained by means of a special recursion of the form:

\begin{cases} F(x, 0) = x, \\ F(x, y+1) = G(F(x, y)) \end{cases}

and superpositions from the functions $g^{n}, h^{n+2}, o, s, I_{m}^{n}$ and $c, l, r$ from problem III.1.13.

(b)

Prove that the function $f(x)$ , obtained from $a$ and $h(x, y)$ by means of the primitive recursion operator, can be obtained by means of iteration and superpositions from the functions $a, h, o, s, I_{m}^{n}$ and $c, l, r$ from problem III.1.13.

Problem III.1.29

Prove that the function $f^{n}$ , obtained from the partial function $g^{n+1}$ by means of the $\mu$ -operator, can be obtained from the functions $g, I_{m}^{n}$ and $c, l, r$ from problem III.1.13 by means of superpositions and a $\mu$ -operator of the special form.

F(x) = \mu y \left[G(x, y) = 0\right].

?

Problem III.1.30

Prove that the function $f^{n+1}$ , obtained by means of the primitive recursion operator from everywhere defined functions $g^{n}$ and $h^{n+2}$ , can be obtained from these functions and the functions $+, \symdiff , s, o, I_{m}^{n}$ and $c, l, r, \beta$ from problems III.1.13, III.1.17, by means of superpositions and a $\mu$ -operator of the special form from problem III.1.29.

?

Problem III.1.31

(a)(b)(c)

?

(a)

Let $\sqrt{2} = a_{0}, a_{1}a_{2}, \ldots$ be the expansion of the number $\sqrt{2}$ as an infinite decimal fraction. Prove that the function $a_{n}$ is general recursive.

(b)

Let $e = a_{0}, a_{1}a_{2}, \ldots$ be the expansion of the number $e$ as an infinite decimal fraction. Prove that the function $a_{n}$ is general recursive.

(c)

Let $\pi = a_{0}, a_{1}a_{2}, \ldots$ be the expansion of the number $\pi$ as an infinite decimal fraction. Prove that the function $a_{n}$ is general recursive.

Problem III.1.32

Let $\alpha = a_{0}, a_{1}a_{2}, \ldots$ be the expansion of the real number $\alpha$ as an infinite decimal fraction. Call the number $\alpha$ general recursive (constructive), if $a_{n}$ is a general recursive function of $n$ . Prove that algebraic numbers are general recursive.

?

Problem III.1.33

Prove that:

?

(a)

$\mathbf{i}(ax+b) = b \cdot \dfrac {a^{x} - 1}{a - 1}$ for $a > 1$ ;

(b)

$\mathbf{i}\left(1 + \left[\dfrac {x}{2}\right]\right) = \operatorname {sg} x$ ;

(c)

$\mathbf{i}\left(x + 1 + \left[\dfrac {x+1}{2}\right] - \left[\dfrac {x}{2}\right]\right) = 2x \symdiff 1$ ;

(d)

$\mathbf{i}(\overline{\operatorname {sg}}\, x + 2x) = 2^{x-1} \symdiff \overline{\operatorname {sg}}\, x$ ;

(e)

$\mathbf{i}(x + 1 + \sqrt{4x+1}) = x^{2} + x$ ;

(f)

$\mathbf{i}\left(x + 1 + 2\left[\sqrt{x}\right]\right) = x^{2}$ .

Problem III.1.34

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

(k)

(l)

(m)

Problem III.1.35

Prove that every primitive recursive function can be obtained from the functions $s(x) = x+1$ and $q(x) = x \symdiff \left[\sqrt{x}\right]^{2}$ by means of the operations of substitution, iteration, and addition of two functions (R. Robinson's theorem).

?

Problem III.1.36

(a)(b)

Prove that:

?

(a)

$I_{1}^{1}(f(x)) = f(I_{1}^{1}(x)) = f(f^{-1}(f(x))) = f(x)$ ;

(b)

$f^{-1}(f(f^{-1}(x))) = f^{-1}(x)$ .

Problem III.1.37

(a)(b)(c)

Prove that:

?

(a)

if $f^{-1}(x)$ is defined at some point $a$ , then

f(f^{-1}(a)) = a;

(b)

if $f^{-1}(x)$ is everywhere defined, then

f(f^{-1}(x)) = I_{1}^{1}(x);

(c)

there exists $f(x)$ such that $f^{-1}(x)$ is everywhere defined, but

f^{-1}(f(x)) \neq I_{1}^{1}(x).

Problem III.1.38

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

Problem III.1.39

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

(k)

(l)

(m)

Problem III.1.40

Let $f(x) = \mu y \left[h(x, y) = 0\right]$ . Prove that $f(x)$ can be obtained from $h, s(x) = x+1$ , and $q(x) = x \symdiff \left[\sqrt{x}\right]^{2}$ by means of the operations of substitution, inversion, and addition of two functions.

?

Problem III.1.41

Prove that every partial recursive function can be obtained from $s(x) = x+1$ , $q(x) = x \symdiff \left[\sqrt{x}\right]^{2}$ by means of the operations of substitution, inversion, and addition of two functions (Yu. Robinson's theorem).

?

Problem III.1.42

Consider the following Ackermann functions:

B(0, y) = 2+y; \qquad B(x+1, 0) = \operatorname {sg} x; \qquad B(x+1, y+1) = B(x, B(x+1, y)); \qquad A(x) = B(x, x).

Call an everywhere defined function $f(x_{1}, \ldots , x_{n})$ $B$ -majorized, if there is a natural number $m$ such that

f(x_{1}, \ldots , x_{n}) < B(m, \max (x_{1}, \ldots , x_{n}) + 3).

Prove that:

?

(a)

$B(x, y)$ and $A(x)$ are general recursive;

(b)

$B(n+2, x+1) \geq 2^{x+1}$ ;

(c)

$B(n+1, x+2) \geq B(n+1, x+1)$ ;

(d)

$B(n+2, x+3) \geq B(n+1, x+4)$ ;

(e)

the simplest functions are $B$ -majorized;

(f)

a function obtained by means of superposition from $B$ -majorized functions is $B$ -majorized;

(g)

a function obtained by means of primitive recursion from $B$ -majorized functions is $B$ -majorized;

(h)

the function $A$ is not primitive recursive.

Problem III.1.43

Prove that there is no primitive recursive function universal for the family of all $n$ -ary primitive recursive functions.

?

Problem III.1.44

Prove that there is no partial recursive function universal for the family of all $n$ -ary general recursive functions.

?