Math Problems Vault

Problem III.4.1

Prove that:

?

(a)

$[x,y]$ is a bijection between $\mathbb {N}^{2}$ and $\mathbb {N}$ ;

(b)

$[x_{1}, \ldots , x_{n}]$ is a bijection between $\mathbb {N}^{n}$ and $\mathbb {N}$ ;

(c)

$[[x]_{1}^{2}, [x]_{2}^{2}] = x$ , $[[x,y]]_{1}^{2} = x$ , $[[x,y]]_{2}^{2} = y$ ;

(d)

$[[x]_{1}^{n}, \ldots , [x]_{n}^{n}] = x$ , $[[x_{1}, \ldots , x_{n}]]_{i}^{n} = x_{i}$ ;

(e)

$[x_{1}, \ldots , x_{m}, x_{m+1}, \ldots , x_{n}] = [[x_{1}, \ldots , x_{m}], x_{m+1}, \ldots , x_{n}]$ ;

(f)

$c(x_{0}, c(x_{1}, x_{2})) = [c(x_{0}, x_{1}), x_{2}]$ .

Problem III.4.2

(a)(b)

Prove that:

?

(a)

$K^{n+m+1}(x_{0}, x_{1}, \ldots , x_{n}, x_{n+1}, \ldots , x_{n+m}) = K^{m+1}([x_{0}, x_{1}, \ldots , x_{n}], x_{n+1}, \ldots , x_{n+m})$ ;

(b)

$K^{n}(c(x_{0}, x_{1}), x_{2}, \ldots , x_{n}) = U^{n+1}(x_{0}, x_{1}, x_{2}, \ldots , x_{n})$ .

Problem III.4.3

(a)(b)

Prove that:

?

(a)

$K^{n+1}(x_{0}, x_{1}, \ldots , x_{n})$ is universal for all $n$ -ary partial recursive functions;

(b)

for any partial recursive function $f^{n+m}$ there is a primitive recursive function $g^{n}$ such that

f(x_{1}, \ldots , x_{n}, y_{1}, \ldots , y_{m}) = K^{m+1}(g(x_{1}, \ldots , x_{n}), y_{1}, \ldots , y_{m}).

Problem III.4.4

Prove that every partial recursive function $f$ has infinitely many Kleene numbers.

?

Problem III.4.5

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

Construct primitive recursive functions that give, from the Kleene numbers of the original one-place functions, the Kleene numbers of the functions obtained from the originals:

?

(a)

by means of superposition;

(b)

by means of inversion;

(c)

by means of iteration;

(d)

by means of taking the sum of two functions.

Problem III.4.6

(a)(b)

Prove that there is a recursively enumerable set $P$ satisfying the conditions:

?

(a)

if $x \in P$ , then $\kappa_{x}$ is a primitive recursive function;

(b)

for any primitive recursive function $f$ there is $x \in P$ such that $f = \kappa_{x}$ .

Problem III.4.7

Prove that there is a general recursive function universal for the family of all one-place primitive recursive functions.

?

Problem III.4.8

(a)(b)(c)

Construct primitive recursive functions that give, from the Kleene numbers of the original functions, the Kleene numbers of the functions obtained from the originals:

?

(a)

by means of superposition;

(b)

by means of primitive recursion;

(c)

by means of the $\mu$ -operator.

Problem III.4.9

Prove that for any partial recursive function $f(x_{1}, \ldots , x_{n})$ there is a primitive recursive function $g(x_{1}, \ldots , x_{n})$ such that for any $x$

\kappa _{g(x_{1}, \ldots , x_{n})} = \begin{cases} \kappa _{f(x_{1}, \ldots , x_{n})}, & \text{if } f(x_{1}, \ldots , x_{n}) \text{ is defined,} \\ \omega & \text{otherwise.} \end{cases}

?

Problem III.4.10

(a)(b)

?

(a)

Prove that for every partial recursive function $f(x_{1}, \ldots , x_{n}, y)$ there is a primitive recursive function $g(x_{1}, \ldots , x_{n})$ such that

\kappa _{g(x_{1}, \ldots , x_{n})} = \begin{cases} \kappa _{f(x_{1}, \ldots , x_{n}, g(x_{1}, \ldots , x_{n}))}, & \text{if } f(x_{1}, \ldots , x_{n}, g(x_{1}, \ldots , x_{n})) \text{ is defined,} \\ \omega & \text{otherwise.} \end{cases}

(b)

Prove that for every partial recursive function $f(x)$ there is a natural number $a$ such that

\kappa _{a} = \begin{cases} \kappa _{f(a)}, & \text{if } f(a) \text{ is defined,} \\ \omega & \text{otherwise} \end{cases}

(the fixed-point theorem).

Problem III.4.11

Prove that for any partial recursive function $f(x,y)$ there is a number $n$ such that $f(n,y) = \kappa_{n}(y)$ for all $y$ .

?

Problem III.4.12

(a)(b)

Prove that there is a number $n$ such that:

?

(a)

$\kappa_{n}(0) = n$ ;

(b)

$\kappa_{n}(n) = n$ .

Problem III.4.13

Prove that there is a primitive recursive function $f$ such that for any $x$ , if $\kappa_{x}$ is a general recursive function, then

\kappa _{\kappa _{x}(f(x))} = \kappa _{f(x)}.

?

Problem III.4.14

(a)(b)(c)

Construct partial recursive functions $\kappa_{a}$ such that:

?

(a)

$\kappa_{a} = \chi_{\left\{ a\right\} }$ ;

(b)

$\kappa_{a} = \chi_{\left\{ a\right\} }^{*}$ ;

(c)

$\kappa_{a} = \chi_{\mathbb {N} - \left\{ a\right\} }^{*}$ .

Problem III.4.15

Let $\mathcal{F}$ be the family of all one-place partial functions. We call a map $F: \mathcal{F} \to \mathcal{F}$ an effective operator, if the function $g(n,x) = (F(\kappa_{n}))(x)$ is partial recursive. Prove that for any effective operator $F$ there is a partial recursive function $f$ such that $f = F(f)$ .

?

Problem III.4.16

(a)(b)

Prove that for any partial recursive functions $\alpha , \gamma , \delta$ there is a partial recursive function $f$ satisfying the conditions:

?

(a)

if $\alpha (x) = 0$ , then $f(x) = 0$ ;

(b)

if $\alpha (x) > 0$ , then $f(x) = \gamma (f(\delta (x)))$ .

Problem III.4.17

Let $\mathcal{A}$ be a nonempty family of one-place partial recursive functions, distinct from the family of all such functions. Prove that the set

\kappa ^{-1}(\mathcal{A}) = \left\{ x \mid \kappa _{x} \in \mathcal{A}\right\}

is not recursive (Rice's theorem).

?

Problem III.4.18

Prove that the following sets are not recursive:

?

(a)

$A_{1} = \left\{ x \mid \kappa_{x} \text{ is a constant}\right\}$ ;

(b)

$A_{2} = \left\{ x \mid \kappa_{x}(a) = b\right\}$ , where $a, b$ are fixed numbers;

(c)

$A_{3} = \left\{ c(x,y) \mid y \in \delta_{\kappa_{x}}\right\}$ ;

(d)

$A_{4} = \left\{ c(x,y) \mid y \in \rho_{\kappa_{x}}\right\}$ ;

(e)

$A_{5} = \left\{ c(x,y) \mid \kappa_{x} = \kappa_{y}\right\}$ .

Problem III.4.19

(a)(b)(c)

Prove the recursive enumerability of the sets of all Kleene numbers of the following families of one-place partial recursive functions:

?

(a)

functions defined at the point $0$ ;

(b)

functions $f$ such that $f(a) = b$ for given numbers $a$ and $b$ ;

(c)

functions with nonempty domain of definition.

Problem III.4.20

Prove that every recursively enumerable set has infinitely many Post numbers.

?

Problem III.4.21

Let $\mathcal{A}$ be a nonempty family of recursively enumerable sets, distinct from the family of all recursively enumerable sets. Prove that the set

\pi ^{-1}(\mathcal{A}) = \left\{ x \mid \pi _{x} \in \mathcal{A}\right\}

is not recursive (Rice's theorem).

?

Problem III.4.22

Prove that the following sets are not recursive:

?

(a)

$\left\{ x \mid \pi_{x} \neq \emptyset \right\}$ ;

(b)

$\left\{ x \mid \pi_{x} = \mathbb {N}\right\}$ ;

(c)

$\left\{ x \mid a \in \pi_{x}\right\}$ , where $a$ is a fixed number;

(d)

$\left\{ x \mid \pi_{x} \text{ is finite}\right\}$ ;

(e)

$\left\{ c(x,y) \mid \pi_{x} = \pi_{y}\right\}$ .

Problem III.4.23

(a)(b)

Prove that the sets of all Post numbers of the following families of recursively enumerable sets are recursively enumerable:

?

(a)

those containing a given number $a$ ;

(b)

the nonempty ones.

Problem III.4.24

Prove that for any partial recursive function $f^{n}$ there is a primitive recursive function $g^{n}$ such that

\pi _{g(x_{1}, \ldots , x_{n})} = \begin{cases} \pi _{f(x_{1}, \ldots , x_{n})}, & \text{if } f(x_{1}, \ldots , x_{n}) \text{ is defined,} \\ \emptyset & \text{otherwise.} \end{cases}

?

Problem III.4.25

Prove that for every recursively enumerable set $P \subseteq \mathbb {N}^{n+1}$ ( $n > 0$ ) there is a primitive recursive function $\alpha (x_{1}, \ldots , x_{n})$ such that

\langle x_{0}, x_{1}, \ldots , x_{n} \rangle \in P \Leftrightarrow x_{0} \in \pi _{\alpha (x_{1}, \ldots , x_{n})}.

?

Problem III.4.26

Prove that there exist primitive recursive functions $f, g, h, u, v, w$ such that:

?

(a)

$\pi_{x} \cap \pi_{y} = \pi_{f(x,y)}$ ;

(b)

$\pi_{x} \cup \pi_{y} = \pi_{g(x,y)}$ ;

(c)

$\left\{ x\right\} = \pi_{h(x)}$ ;

(d)

$\left\{ c(s,t) \mid s \in \pi_{x}, t \in \pi_{y}\right\} = \pi_{u(x,y)}$ ;

(e)

$\kappa_{y}(\pi_{x}) = \pi_{v(x,y)}$ ;

(f)

$\kappa_{y}^{-1}(\pi_{x}) = \pi_{w(x,y)}$ .

Problem III.4.27

(a)(b)

Prove that there exist primitive recursive functions $f$ and $g$ such that:

?

(a)

$\delta_{\kappa_{x}} = \rho_{\kappa_{f(x)}}$ ;

(b)

$\rho_{\kappa_{x}} = \delta_{\kappa_{g(x)}}$ .

Problem III.4.28

(a)(b)

?

(a)

Prove that for any partial recursive function $f^{n+1}$ there is a primitive recursive function $g^{n}$ such that

\pi _{g(x_{1}, \ldots , x_{n})} = \begin{cases} \pi _{f(x_{1}, \ldots , x_{n}, g(x_{1}, \ldots , x_{n}))}, & \text{if } f(x_{1}, \ldots , x_{n}, g(x_{1}, \ldots , x_{n})) \text{ is defined,} \\ \emptyset & \text{otherwise.} \end{cases}

(b)

Prove that for any partial recursive function $f$ there is a number $a$ such that

\pi _{a} = \begin{cases} \pi _{f(a)}, & \text{if } f(a) \text{ is defined,} \\ \emptyset & \text{otherwise} \end{cases}

(the fixed-point theorem).

Problem III.4.29

Prove that for any recursively enumerable set $M \subseteq \mathbb {N}^{n+2}$ there is a primitive recursive function $g^{n}$ such that

\langle x_{0}, x_{1}, \ldots , x_{n}, g(x_{1}, \ldots , x_{n}) \rangle \in M \Leftrightarrow x_{0} \in \pi _{g(x_{1}, \ldots , x_{n})}.

?

Problem III.4.30

(a)(b)(c)

Prove that there is a number $n$ such that:

?

(a)

$\pi_{n} = \left\{ n\right\}$ ;

(b)

$\pi_{n} = \left\{ n^{2}\right\}$ ;

(c)

$\pi_{n} = \mathbb {N} \setminus \left\{ n\right\}$ .

Problem III.4.31

Prove that the relation $\leq_{m}$ is reflexive and transitive.

?

Problem III.4.32

Prove that every recursive set is $m$ -reducible to any nonempty set with nonempty complement.

?

Problem III.4.33

Prove that if $A$ is $m$ -reducible to a recursive (recursively enumerable) set, then $A$ is recursive (recursively enumerable).

?

Problem III.4.34

Prove that the set

K_{1} = \left\{ c(x,y) \mid x \in \pi _{y}\right\}

is $m$ -universal.

?

Problem III.4.35

Prove that every $m$ -universal set is not recursive.

?

Problem III.4.36

Prove that the set

K = \left\{ x \mid x \in \pi _{x}\right\}

is creative.

?

Problem III.4.37

Prove that every creative set is not recursive.

?

Problem III.4.38

Prove that if $A$ is a creative set, $A \leq_{m} B$ , and $B$ is recursively enumerable, then $B$ is creative.

?

Problem III.4.39

Prove that every creative set is $m$ -universal.

?

Problem III.4.40

Prove that a set is $m$ -universal if and only if it is creative.

?

Problem III.4.41

Prove that the set

K_{2} = \left\{ x \mid \pi _{x} \neq \emptyset \right\}

is creative.

?

Problem III.4.42

Prove that there is a primitive recursive function $\sigma (x)$ such that the Turing machine with number $\sigma (x)$ computes the function $\kappa_{x}$ .

?

Problem III.4.43

Prove that the set $H$ from problem III.3.43 of 3 is creative.

?