Recursive and Recursively Enumerable Sets

Prove that the following predicates are primitive recursive:

Prove that if $P(x_{1}, \ldots , x_{n})$ and $Q(x_{1}, \ldots , x_{n})$ are recursive (primitive recursive) predicates, then the following predicates are also recursive (primitive recursive):

Prove that if the predicate $R(x_{1}, \ldots , x_{n}, y)$ is recursive (primitive recursive), then the predicates $\exists y (y \leq z\ \& \ R(x_{1}, \ldots , x_{n}, y))$ and $\forall y (y \leq z \supset R(x_{1}, \ldots , x_{n}, y))$ are also recursive (primitive recursive).

Prove that if the predicate $R(x_{1}, \ldots , x_{n}, y, z)$ is primitive recursive, then $M = \left\{ \langle x_{1}, \ldots , x_{n} \rangle \mid \exists y \exists z\, R(x_{1}, \ldots , x_{n}, y, z)\right\}$ is a recursively enumerable set.

Prove that there exists a set that is not recursively enumerable.

Prove that any finite set of natural numbers is primitive recursive.

Prove that a set of $n$-tuples is recursive (primitive recursive) if and only if its characteristic function is general recursive (primitive recursive).

Prove that if $f$ is a general recursive (primitive recursive) function and $a$ is a fixed number, then the set of solutions of the equation $f(x_{1}, \ldots , x_{n}) = a$ is recursive (primitive recursive).

Let the function $f$ be partial recursive but not general recursive. Prove that the domain of definition of the function $f^{-1}$ is primitive recursive.

Prove that if the sets $A$ and $B$ are recursive (primitive recursive), then the sets $A \cap B$, $A \cup B$, $\mathbb {N} \setminus A$ are also recursive (primitive recursive).

Prove that if the sets $A$ and $B$ are recursively enumerable, then the sets $A \cap B$ and $A \cup B$ are recursively enumerable.

Prove that every primitive recursive set is recursively enumerable.

Let the sets $A$ and $B$ differ by finitely many elements. Prove that:

Prove that if a set $A$ and its complement $\mathbb {N} \setminus A$ are recursively enumerable, then $A$ is recursive (Post's theorem).

Let $M \subseteq \mathbb {N}^{n}$. Set

where $c^{n}$ is defined in problem III.1.14. Prove that:

Let $M \subseteq \mathbb {N}$ be a nonempty set. Prove that $M$ is recursively enumerable if and only if there is a primitive recursive function $\alpha (x)$ such that $M = \left\{ \alpha (x) \mid x \in \mathbb {N}\right\}$.

Let $M$ be a nonempty set of $n$-tuples. Prove that the set $M$ is recursively enumerable if and only if there are one-place primitive recursive functions $\alpha_{1}, \ldots , \alpha_{n}$ such that

Let the general recursive function $f(x)$ satisfy the condition: $f(x) \geq x$ for all $x \in \mathbb {N}$. Prove that the range of values $\rho_{f}$ of the function $f$ is recursive.

Prove that an infinite set $A$ is recursive if and only if $A$ is the range of values of a strictly increasing general recursive function.

Prove that a nonempty set $A$ is recursive if and only if $A$ is the range of values of a monotonically (not necessarily strictly) increasing general recursive function.

Prove that every infinite recursively enumerable set contains an infinite recursive subset.

Prove that every infinite recursively enumerable set can be represented as $A = \rho_{f}$ for some 1--1 general recursive function $f$.

Prove that the graph of a general recursive function is recursive.

Prove that if the graph $\Gamma_{f}$ of a function $f$ is recursively enumerable, then the function $f$ is partial recursive.

Prove that the full preimage of a recursive set under a general recursive function is recursive.

Let $A$ be a recursive set, $f$ a general recursive function with $\rho_{f} = \mathbb {N}$, $f(A) \cap f(\mathbb {N} \setminus A) = \emptyset$. Prove that $f(A)$ is recursive.

Let $A, B$ be recursively enumerable sets, and $C$ a recursive set such that $A \cap B = \emptyset$, $A \subseteq C \subseteq A \cup B$. Prove that $A$ is recursive.

Let $f, g$ be general recursive functions, with $g$ a 1--1 function. Suppose also that $f(x) \geq g(x)$ for all $x$. Prove that if $\rho_{g}$ is recursive, then $\rho_{f}$ is recursive.

Let $A, B$ be recursively enumerable sets. Prove that there exist recursively enumerable sets $A_{1} \subseteq A$, $B_{1} \subseteq B$ such that $A_{1} \cap B_{1} = \emptyset$, $A_{1} \cup B_{1} = A \cup B$.

Prove that:

Prove that a function is partial recursive if and only if its graph is recursively enumerable (the graph theorem).

Prove that the domain of definition of a partial recursive function is a recursively enumerable set.

Prove that the range of values of a partial recursive function is recursively enumerable.

Prove that any recursive set is recursively enumerable.

Prove that a set of $n$-tuples is recursively enumerable if and only if its partial characteristic function is partial recursive.

Prove that:

Prove that the set $A$ of solutions of the equation

is recursively enumerable, if $f$ is a partial recursive $n$-ary function.

Prove that if $f^{n+1}$ is a partial recursive function, then the set $M = \left\{ \langle x_{1}, \ldots , x_{n} \rangle \mid \exists y\, f(x_{1}, \ldots , x_{n}, y) = 0\right\}$ is recursively enumerable.

Let $M_{1}, \ldots , M_{k}$ be pairwise disjoint recursively enumerable sets of $n$-tuples, $f_{1}, \ldots , f_{n}$ partial recursive functions. Prove that $g(x_{1}, \ldots , x_{n})$, defined as follows:

is partial recursive.

Prove that any partial recursive function $f(x_{1}, \ldots , x_{n})$ is representable in Kleene normal form, i.e., in the form

where $g(x_{1}, \ldots , x_{n}, t)$ is a suitable primitive recursive function, and $l$ is the function from problem III.1.13 (cf. problem III.2.25).

Prove that a partial function $f(x_{1}, \ldots , x_{n})$ is representable in the form

for a suitable primitive recursive function $g(x_{1}, \ldots , x_{n}, t)$ if and only if the graph of the function $f(x_{1}, \ldots , x_{n})$ is primitive recursive.

Let $F(x,y)$ be defined by means of recursion on two variables:

Prove that if the functions $\varphi , \psi , \alpha , \gamma , \tau$ are general recursive, then the function $F$ is general recursive.

Prove that the set

where $T_{1}$ is the function from problem III.2.25, is recursively enumerable but not recursive.

Prove that if the domain of definition of a partial recursive function $f^{n}$ is a recursive set, then $f^{n}$ has a recursive extension.

Prove that if $V(n,x)$ is a partial recursive function universal for the class of all one-place partial recursive functions, then the set $M = \left\{ x \mid V(x,x) = 0\right\}$ is recursively enumerable but not recursive.

Find a partial recursive function $f(x)$ that has no general recursive extension.

Find a partial recursive function $f(x)$ not representable in the form

for any general recursive function $g$.

Prove that if $V(n,x)$ is a partial recursive function universal for the class of all one-place partial recursive functions, then the set

is not recursively enumerable.