Chapter 7

Let \(f\) be a unary computable function, and suppose that \(A \subseteq\) Dom \((f)\), and let \(g=f \mid A\). Prove that \(g\) is computable iff \(A\) is r.e.

Suppose that \(f\) is a total computable function, \(A\) a recursive set and \(B\) an r.c. set. Show that \(f^{-1}(A)\) is recursive and that \(f(A)\), \(f(B)\) and \(f^{-1}(B)\) are r.e. but not necessarily recursive. What extra information about these sets can be obtained if \(f\) is a bijection?

(a) Let \(K_{a}=\left\\{x: \phi_{n}(x)=0\right\\}\) and \(K_{1}=\left\\{x: \phi_{2}(x)=1\right\\}\). Show that \(K_{a}\) and \(K_{1}\) ire r.e., and that they are recursitely inseparabie, i.e. \(K_{0} \cap K_{1}=\mathscr{D}\) and there is no recursive set \(C\) such that \(K_{0} \leqq C\) and \(K_{1} \leq \bar{C} ;\) in particular neither \(K_{0}\) nor \(K_{1}\) is recursive. (Hint. Suppose that there is such a set \(C\) and let \(m\) be an index for its characteristic function: consider whether or not \(m \equiv C .)(b)\) Show that two disjoint sets \(A, B\) are recursively inseparable tin the above sense) iff whenever \(A \in W_{m}, B \subseteq W_{b}\) and \(W_{a} \cap W_{k}=\varnothing\), then there is a number \(x \in W_{a} \cup W_{b}\). LNote. Recursive inseparability for a pair of disjoint sets corresponds to nonrecursiveness for a single set; pairs of recursively inseparable sets that are also r.e. correspond to r.e. sets that are not recursive.)