Computability Theory — Fall 2013
Homework Problems
Friday, September 13
1. [9/6] Without using the recursion theorem, show that $K=\{e\colon \varphi_e(e)\downarrow\}$ is not an index set.
2. [9/6] Recall that $Tot=\{e\colon \varphi_e$ is total$\}$ and $Cof=\{e\colon \text{dom}(\varphi_e)$ is cofinite$\}$. Show that $Tot\leq_1 Cof$ and $\overline{Tot}\leq_1 Cof$. Monday, September 23
3. [9/11] Construct an infinite, coinfinite set $A$ such that $A\oplus A\nleq_1 A$. (This is interesting because it is obviously always the case that $A\oplus A\equiv_m A$.)
4. [9/16] Let $\text{Min} = \{e\colon (\forall i < e)\;\varphi_i\neq\varphi_e\}$. Show that $\text{Min}$ does not have an infinite c.e. subset. 5. [9/16] Let $f$ be a computable function and let $S\subseteq\omega$ be a computable set containing all of the fixed points of $f$. In other words, $\{e\colon\varphi_e=\varphi_{f(e)}\}\subseteq S$. Prove that $S$ contains indices for every partial computable function. Friday, Oct. 4th
6. [9/20] Show that there is a set $\mathcal{C}\subseteq \mathcal{P}(\omega)$ of size continuum such that distinct elements $A,B\in \mathcal{C}$ are Turing incomparable. Hint: build a tree of binary strings such that no path through the tree is isolated and any two distinct paths through the tree are Turing incomparable.
8. [9/25] Let $A$ be $1$generic. Show the following:
9. [9/25] Let $X$ be an infinite set. Show that $X$ is hyperimmune iff it is contained in every $\Sigma^0_1$ class that contains all of the finite sets. 10. [9/25] Let $X$ be an infinite set. Show that $X$ is hyperimmune iff there is a $1$generic $A\supseteq X$. Monday, October 28
11. Fix $n>1$. Show that for every $\Delta^0_n$ set $A$, there is a $\Delta^0_n$ set $B\nleq_m A$. (In other words, show that no set is $1$complete for $\Delta^0_n$.)
12. Show that if $A'\leq_m B$, then $A'\leq_1 B$. (This proves that if $n>0$, then $\Sigma_n$completeness is equivalent for $1$reducibility and $m$reducibility.) Hint: use the recursion theorem to threaten contradiction if the $m$reduction doesn't provide you with new numbers. 13. We call c.e. sets $A$ and $B$ computably inseparable if $A\cap B=\emptyset$ and there is no computable set $C$ such that $A\subseteq C$ and $C\cap B=\emptyset$. Prove that $A=\{e\colon \varphi_e(e)=0\}$ and $B=\{e\colon \varphi_e(e)=1\}$ are computably inseparable. 14. Let $\text{CInsep}=\{\langle e,i\rangle\mid W_e\text{ and }W_i\text{ are computably inseparable}\}$. Prove that $\text{CInsep}$ is $\Pi^0_3$complete. 15. Assume that $D$ is an upper bound of $\{\emptyset^{(n)}\}_{n\in\omega}$. Show that $D''\geq_T\emptyset^{(\omega)}$. 16. Show that there is an upper bound $D$ of $\{\emptyset^{(n)}\}_{n\in\omega}$ such that $D''\leq_T\emptyset^{(\omega)}$. Hint: add coding to the ftree construction of a set of hyperimmunefree degree. 17. Prove that there are $2^{\aleph_0}$ minimal degrees. (It is enough to show that there are $2^{\aleph_0}$ sets of minimal degree.) Monday, November 4
18. Show that every noncomputable c.e. set computes a $1$generic. 19. Assume that $X$ is the only nonisolated element of a $\Pi^0_1$ class $P$. Show that $X\leq_T\emptyset''$. Can it be true that $X\equiv_T \emptyset''$? Monday, November 18
20. Construct a nonempty perfect $\Pi^0_1$ class $P$ such that every element of $P$ is noncomputable and GL$_1$. 21. Let $X$ be a noncomputable c.e. set. Prove that there are computably inseparable c.e. sets $A$ and $B$ such that $X = A\cup B$. End of semester
22.
23. Let $X$ be a noncomputable c.e. set. Prove that there are computably inseparable c.e. sets $A$ and $B$ such that $X = A\cup B$. 24. Construct a $\Delta^0_2$ degree incomparable from every c.e. degree except $\bf 0$ and $\bf 0'$. Hint: say we are building a $\Delta^0_2$ set $A$. Consider the strategy that tries to ensure that if $W_e$ is not complete, then $\Phi_i^{W_e}\neq A$. This strategy cannot be allowed to change $A$ too often. Only let it change $A\upharpoonright n$ at stages where $\emptyset'\upharpoonright n$ has changed. Then you can show that if $\Phi_i^{W_e}$ is total, then either $W_e$ is complete or you were eventually allowed to make $A$ different from $\Phi_i^{W_e}$. 25.
26. If $T\subseteq\omega^{<\omega}$ is a computable (or even $\Pi^0_1$) tree, then the set of paths $[T]\subseteq\omega^\omega$ through $T$ is a $\Pi^0_1$ class in Baire space.
