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:

  1. $A'\equiv_T A\oplus\emptyset'$ (i.e., $A$ is GL$_1$).
  2. If $A=A_0\oplus A_1$, then $A_0$ and $A_1$ are a minimal pair (hence $A_0\mid_T A_1$).
  3. $A$ does not compute a noncomputable c.e. set.
  4. $A$ is hyperimmune.
  5. $\overline{A}$ is $1$-generic.

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 f-tree construction of a set of hyperimmune-free 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


  1. Construct a d.c.e. set that is not Turing equivalent to a c.e. set.
  2. Show that every noncomputable d.c.e. set computes a noncomputable c.e. set.

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}$.


  1. Show that every cohesive set is hyperimmune.
  2. Show that every maximal set is dense simple, meaning that the principal function of its complement dominates every computable function. This shows that maximal sets are high.
  3. Show that $\omega$ is the disjoint union of countably many cohesive sets.
  4. Show that $\omega$ is not the union of finitely many cohesive sets.

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.

  1. Show that if $\{f\}$ is a $\Pi^0_1$ class in Baire space, then $f$ is hyperarithmetical.
  2. Buid a computable tree $T\subseteq\omega^{<\omega}$ such that $[T]=\{f\}$ where $f\equiv_T\emptyset'$.
  3. Buid a computable tree $T\subseteq\omega^{<\omega}$ such that $[T]=\{f\}$ where $f\equiv_T\emptyset^{(\omega)}$.

    Using the same method, it can be shown that for any computable ordinal $\alpha$, there is a computable tree $T\subseteq\omega^{<\omega}$ such that $[T]=\{f\}$ where $f\equiv_T\emptyset^{(\alpha)}$. So $\Pi^0_1$ singletons in Baire space can be arbitrarily high in the hyperartihmetical hierarchy. But not every hyperarithmetical degree is realized in this way.

  4. Show that if $f\in\omega^\omega$ is hyperimmune-free and noncomputable, then $\{f\}$ is not a $\Pi^0_1$ class in Baire space.