Math Problems Vault

Example 5.18

Show that the set $F$ of functions from $\mathbf{N}$ to $\left\{ 0,1\right\}$ is uncountable.

?

Example 5.19

Show that there exists a co-r.e. set that is not r.e.

?

Example 5.21

We say a partial recursive function $f: \left\{ 0,1\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$ is extendable if there exists a recursive function $g: \left\{ 0,1\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$ such that $g(x)=f(x)$ whenever $f(x) \downarrow$ . Show that there exists a partial recursive function that is not extendable.

?

Example 5.22

Show that TOT $=\left\{ n \mid W_{n}= \left\{ 0,1\right\}^{*}\right\} =\left\{ n \mid \phi_{n}\text{ is recursive }\right\}$ is not r.e.

?

Example 5.23

Show that there exists a simple set.

?

Problem 5.3.1

Let $A$ be any set (not necessarily countable). Show that there does not exist a one-to-one correspondence between set $A$ and the set $2^{A}$ of all subsets of $A$ .

?

Problem 5.3.2

Show that the set $F_{1}$ of all one-to-one, increasing functions from $\mathbf{N}$ to N is uncountable.

?

Problem 5.3.3

(a)(b)

What are wrong with the following diagonalization proofs?

?

(a)

We show that there exists a partial recursive function $f: \left\{ 0,1\right\}^{*} \rightarrow \left\{ 0,1\right\}^{*}$ which is not enumerated in $\phi_{0}, \phi_{1}, \ldots$ . Define $f(n)= \phi_{n}(n)+1$ . Then, by the existence of the universal DTM, we can see that $f$ is partial recursive. Thus, we have obtained a partial recursive function $f$ that is different from every $\phi_{n}$ at input $n$ , $n \geq 0$ .

(b)

We show that the set $\operatorname {REC}=\left\{ x \mid W_{x}\text{ is recursive }\right\}$ is not r.e. Suppose, by way of contradiction, that REC is r.e. Then, there exists a recursive function $g$ whose range is equal to REC. Define $A=\left\{ x \mid x \notin W_{g(x)}\right\}$ . Since each $W_{g(x)}$ is recursive, it is decidable whether $x \in W_{g(x)}$ . Therefore, $A$ is a recursive set. But this is a contradiction, since $A \neq W_{g(x)}$ for every $x \geq 0$ .

Problem 5.3.4

Assume that $A \subseteq \mathbf{N}$ is a set with the following properties: (i) $\phi_{n}$ is recursive for all $n \in A$ , and (ii) for all recursive functions $f, f=\phi_{n}$ for some $n \in A$ . Show that $A$ is not an r.e. set.

?

Problem 5.3.5

(a)(b)

?

(a)

Show that the class of primitive recursive functions is effectively enumerable (in the sense that there is an r.e. set $B$ such that (i) $\phi_{n}$ is primitive recursive, for all $n \in B$ , and (ii) for all primitive recursive function $g, g=\phi_{n}$ for some $n \in B$ ).

(b)

Show that there exists a recursive function that is not primitive recursive.

Problem 5.3.6

Show that set $A=\left\{ n \mid \phi_{n}\text{ halts on }n\text{ and its output is greater than }n\right\}$ is not a recursive set.

?

Problem 5.3.7

Show that the set $\left\{ \langle i, j\rangle \mid W_{i}=\overline{W_{j}}\right\}$ is not an r.e. set.

?

Problem 5.3.8

We say two sets $A$ and $B$ are recursively separable if there exists a recursive set $C$ such that $A \subseteq C$ and $B \subseteq \bar{C}$ . Show that for any $n \neq m \in \mathbf{N}$ , sets $K_{n}$ and $K_{m}$ are not recursively separable, where $K_{n}=\left\{ x \mid \phi_{x}(x)\text{ is defined and is equal to }n\right\}$ .

?

Problem 5.3.9

Give a formal proof that set $S$ defined in Example 5.23 is r.e. That is, let $h(e)$ be the string printed out in stage $e$ by the algorithm for $S$ ( $h(e) \uparrow$ if it does not output any string in stage $e$ ). Prove that $h$ is partial recursive (without using the Church-Turing Thesis).

?

Problem 5.3.10

Show that there exists a set $A$ such that both $A$ and $\bar{A}$ are infinite but neither has an infinite r.e. subset.

?