Course ID:	Math 773
Time:	MWF 1:20—2:10PM
Place:	Van Vleck Hall B235

Mariya Soskova
Office:	523 Van Vleck
Email:	msoskova@math.wisc.edu
Office hours:	M 9:45AM-10:30AM, W 3:15PM—4:00PM

This is an introductory course in computablity (or recursion) theory, covering the following topics: Computable sets and (partial) computable functions The Recursion Theorem Computably enumerable sets; the halting problem Relativization; Turing reducibility (relative computability); the Turing degrees The Turing jump Strong reducibilities; the arithmetical hierarchy; its relationship to the jump Complexity of index sets Low and high degrees; Martin's high domination theorem; other jump classes Forcing the jump; Friedberg and Shoenfield jump inversion Minimal pairs; exact pairs; degrees without a meet 1-generic, hyperimmune, and hyperimmune-free degrees Minimal degrees Immune, simple, hypersimple, cohesive, and maximal sets Diagonally non-computable functions; Arslanov's completeness criterion Π01-classes; PA degrees; the low and hyperimmune-free basis theorems Finite Injury; simple permitting; the Friedberg-Muchnik theorem; cone avoidance; Sacks splitting theorem Priority trees; infinite injury; Sacks jump inversion Computable well-orderings; constructive ordinals; Kleene's O Hyperarithmetical hierarchy; the analytical hierarchy; the Harrison linear order A summary of the course information can be downloaded here.

We will mainly be following the most current draft of "Lecture notes for a first course in computability" by Uri Andrews and Joseph Miller. This draft will be made available to you through the canvas webage for the course. It is not to be distributed! Other sources for this course, available at the library are:

"Turing computability: theory and applications" by Robert Soare

"Recursively enumerable sets and degrees: a study of computable functions and computably generated sets" by Robert Soare

"Computability Theory" by S. Barry Cooper

"Computable structures and the hyperarithmetical hierarchy" by Chris Ash and Julia Knight

Weekly homework will determine your final grade. Homework will be assigned throughout the week and published here every Friday. Homework will be due the following Friday at the beginning of class. Late homework will not be accepted, except in case of illness or family emergency.

A strict level of rigor is necessary in your solutions. Pictures are never proofs, but are always encouraged along with proofs. Your solution should not be just a sequence of equations and formulas, write in complete sentences.

It is okay, even encouraged, if you work on the homeworks in groups. If you do, please acknowledge that in your homework. The solutions you submit, have to be written by each student individually. Copying is not allowed and will be acted against.

ber. Show that nonempty special $\Pi^0_1$ classes correspond to

HW 1(due Feb 2)	Ex 1.2.9, 1.2.16, 1.2.18.
	${ }$
HW 2(due Feb 9)	1. Prove that there are $m$ and $n$ such that $W_m = \{n\}$ and $W_n = \{m\}$.
	2. Prove that if $A$ and $B$ are c.e. sets then there are c.e. sets $A_0\subseteq A$ and $B_0\subseteq B$ such that $A_0\cap B_0 = \emptyset$ and $A_0 \cup B_0 = A\cup B$.
	3. Prove that there is no partial computable function $\psi$ such that for every $i$ if $W_i$ is a finite set then $\psi(i)\downarrow$ and $\psi(i)$ is the canonical code of the finite set $W_i$.
	and Ex 1.5.9, 1.5.10.
	${ }$
HW 3(due Feb 16)	1. Prove that $A\leq_T B$ if and only if there is a c.e. set $W\subseteq 2^{<\omega}\times\omega\times\{0,1\}$, such that for all $\sigma, x, y$ if $(\sigma, x, y)\in W$ and $\tau\succeq \sigma$ then $(\tau, x, y)\in W$ and if $(\sigma, x, y_1)\in W$ and $(\sigma, x, y_2)\in W$ then $y_1 = y_2$ and such that $x\in A$ if and only if for some $\sigma\preceq B$ we have that $(\sigma, x, 1)\in W$ and $x\notin A$ if and only if for some $\sigma\preceq B$ we have that $(\sigma, x, 0)\in W$.
	2. For a sequence of sets $\{A_i\}_{i<\omega}$ we set $\bigoplus_{i<\omega} A_i =\{ \langle i, x\rangle |\ x\in A_i\}$. Prove that this operation gives a least uniform upper bound to the sequence in the sense that if there is a total computable function $g$ such that $A_i = \Phi_{g(i)}^B$ then $\bigoplus_{i<\omega} A_i\leq_T B$. Prove further that this operation is not well defined on degrees.
	and Ex 1.6.9, 1.6.11.
	${ }$
HW 4(due Feb 23)	Ex 3.2.9.
	2. For a sequence of sets $\{A_i\}_{i<\omega}$ suppose that $\bigoplus_{i<\omega} A_i$ is $1$-generic. Prove that $\{A_i\}_{i<\omega}$ is an independant sequence, i.e. $A_i\nleq_T \bigoplus_{j\neq i} A_j$.
	3. If $\{A_i\}_{i<\omega}$ is an independent sequence, show that for all pairs of computable sets $I$ and $J$ we have that $I\subseteq J$ if and only if $\bigoplus_{i\in I}A_i\leq_T \bigoplus_{j\in J} A_j$. Can this statement be extended to all pairs of c.e. sets?
	4. Let $\mathcal{L} = (\omega, \leq_L)$ be a partial ordering on $\omega$ such that the binary relation $\leq_L$ is computable. We say that $\mathcal{L}$ is a computable partial ordering. Show that $\mathcal{L}$ can be embedded in the Turing degrees below the degree of any $1$-generic set $A$. Hint: Consider the set $\{i|\ i\leq_L n\}$.
	5. Prove that every countable partial ordering can be embedded into a computable partial ordering.
	${ }$
HW 5(due March 2)	Ex 2.3.8. (Hint it is sufficient to prove that (Cof, Compl)) is ($\Sigma^0_3, \Pi^0_3$) complete. Why? Make the $i$-th element of the complement of $B_x$ larger than the stage at which $i$ enters $K$ (if ever))
	2. Show that (Cof, non-Ext) is ($\Sigma^0_3, \Pi^0_3$) complete, where non-Ext $= \{e|\ \varphi_e \text{ is not extendable to a total computable function}\}$.
	2.3.10 and 2.3.11 (Hint make $\varphi_{h(x)}$ a $\{0,1\}$-valued function, where $h$ is the reduction function witnessing that 2. is true.)
	${ }$
HW 6(due March 16)	1. Prove that there are a pair of degrees $\mathbf{a}\leq \mathbf{0}'$ and $\mathbf{b} \leq \mathbf{0}'$ that don't have a greatest lower bound.
	2. Show that every hyperimmune degree contains a set that is hyperimmune and a set that is not hyperimmune.
	Ex 3.2.10, Ex 3.2.11., Ex 3.2.19, 3.2.20.
	${ }$
HW 7(due March 23)	1. Prove that $X$ is PA if and only if $X$ computes a total extension to every $\{0,1\}$-valued partial computable function.
	2. A $\Pi^0_1$-class is special if it contains no computable mem perfetct computable trees. Show that if $P$ is a special nonempty $\Pi^0_1$ class and $A\geq_T \emptyset'$ then there is a member $X\in P$ such that $X'\equiv_T X\oplus \emptyset'\equiv_T A$.
	Ex 3.3.17 (optional, can be submiited after break), Ex 4.2.6.
	${ }$
HW 8(due April 13)	1. Prove that there is a perfect $\Pi^0_1$ class such that any two members of it are Turing incomparable (Theorem 6.0.15) using the tree method.
	2. Prove that for every non-computable c.e. set $C$ there is a simple set $A\ngeq_T C$ (Theorem 6.0.20) using the tree method.
	3. Prove that there are low c.e. sets $A_0$ and $A_1$ such that for any incomputable c.e. set $B$ there are $B_0\leq_T A_0$ and $B_1\leq_T A_1$ such that $B_0\cup B_1 = B$ and $B_0\cap B_1 = \emptyset$.
	Ex 6.0.14, 6.0.18, 6.0.33.
	${ }$
HW 9(due April 27)	1. A c.e. degree is called nonbranching if it is not the greatest lower bound (meet) of two incomparable c.e. degrees. Prove that there is an incomplete nonbranching c.e. degree.
	and Ex 6.0.14, 6.0.18, 6.0.33 (if not already submitted with previous homework).
	${ }$
HW 10(will not be collected but discussed on May 4)	Ex 8.2.5, 8.2.6, 8.2.7.