% LaTex2e %\documentclass[twoside,12pt]{article} \documentclass[12pt]{article} \usepackage{amssymb,latexsym,xspace} %\usepackage{anysize} %\marginsize{left}{right}{top}{bottom} %\marginsize{2cm}{2cm}{1cm}{1cm} \pagestyle{myheadings} \def\header{{\hfill \mytitle \hfill A. Miller \hfill \today \hfill}} \def\al{{\alpha}} \def\be{{\beta }} \def\blank{\;\tilde{ }\;} \def\cconj{\wedge{\kern -5pt\wedge}} \def\comp(#1){\overline{#1}} \def\conj{\wedge} \def\conv{\downarrow} \def\ddisj{\vee{\kern -5pt\vee}} \def\degrees{{\mathcal D}} \def\delone{\Delta_1^0} \def\dex#1{{\it #1}} \def\disj{\vee} \def\div{\uparrow} \def\dotminus{\dot{-}} \def\dualGamma{\widetilde{\Gamma}} \def\emp{\emptyset} \def\ga{\gamma} \def\iff{\leftrightarrow} \def\implies{\rightarrow} \def\join{\oplus} \def\jump(#1){#1^\prime} \def\lattice{{\mathcal E}} \def\la{\langle} \def\la{\langle} \def\lesss{\lhd} \def\less{\unlhd} \def\om{\omega} \def\pair(#1,#2){\langle #1,#2\rangle} \def\pione{\Pi^0_1} \def\poset{{\mathbb P}} \def\pow{{\mathcal P}} \def\proof{\par\noindent Proof\par\noindent} \def\proves{\vdash} \def\pr{\prime} \def\qed{\par\noindent QED\par} \def\rationals{{\mathbb Q}} \def\ra{\rangle} \def\ra{\rangle} \def\res{{\upharpoonright}} \def\rmand{\mbox{ and }} \def\rmiff{\mbox{ iff }} \def\rmor{{\mbox{ or }}} \def\sigone{\Sigma^0_1} \def\sig{\sigma} \def\si{\sig} \def\sm{\setminus} \def\sq{\subseteq} \def\su{\sq} \def\st{\;:\;} \def\uu{{\mathcal U}} \def\vv{{\mathcal V}} \def\xx{{\mathcal X}} %%%%% specials %%%%%%%%%%%%%%%%%% \def\redegrees{{\mathcal R}} \def\rec{recursive\xspace} \def\re{r.e. } \def\anre{an r.e. } \def\Anre{An r.e. } \def\recenum{recursively enumerable\xspace} \def\prec{partial recursive\xspace} \def\mytitle{Lecture notes in Recursion Theory } \def\recly{recursively\xspace} % \def\redegrees{{\mathcal P}} \def\rec{pineapple\xspace} \def\re{p.j. } \def\anre{a p.j. } \def\Anre{A p.j. } \def\recenum{pineapplely juicy\xspace} \def\prec{sweet pineapple\xspace} \def\mytitle{Lecture notes in Pineapple Theory } \def\recly{pineappleably\xspace} % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % \def\hmwk#1#2{\par\bigskip\noindent {\bf Hmwk #1.} (#2)} \def\hmwk#1#2{\par\bigskip\noindent \addtocounter{theorem}{1} {\bf Exercise \thetheorem . }} % {\bf Exercise \thetheorem . ( #2 )}} \def\exer{\hmwk{nothing}{nothing}} \def\prob{\hmwk{nothing}{nothing}} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{cor}[theorem]{Corollary} \newtheorem{claim}[theorem]{Claim} \newtheorem{question}[theorem]{Question} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{prop}[theorem]{Proposition} \newtheorem{example}[theorem]{Example} \newtheorem{define}[theorem]{Definition} \newtheorem{exercise}[theorem]{Exercise} % \def\exerlabel#1{\begin{exerlabelx}\label{#1}\end{exerlabelx}} \markboth\header\header \begin{document} \begin{center} \mytitle \\ Arnold W. Miller \end{center} These are lecture notes from Math 773. There were mostly written in 2004 but with some additions in 2007. \bigskip\noindent DESCRIPTION: Abstract theory of computation. Turing degree and jump, arithmetic hierarchy, index sets, simple and (hyper)hypersimple sets, Kleene-Post results in Turing degrees, finite injury priority arguments: Friedberg-Muchnik Theorem, Sacks Splitting Theorem, existence of a maximal set. Infinite injury priority arguments: Lachlan minimal pair, Sacks density theorem, Shoenfield incomplete high degrees. Recursive ordinals and the hyperarithmetical hierarchy. \bigskip\noindent Some general references in this area are: \par\noindent Hartley Rogers, Theory of recursive functions, 1967 \par\noindent Robert Soare, Recursively enumerable sets and degrees, 1987 \par\noindent Piergiorgio Odifreddi, Classical recursion theory, vol 1,2 1989,1999 \par\noindent Barry Cooper, Computability theory, 2004 \par\noindent Robert Soare, Computability theory and applications, 2008 \bigskip \tableofcontents \bigskip \section{UR-Basic programming} We begin by giving a formal definitions of computability, a toy programming language: UR-BASIC. \par\noindent Variables are any string of letters or numerals, A-Za-z0-9. \par\noindent Statements are of the form \par Let $X=X+1$ \par Let $X=X\dotminus 1$ \par If $X\leq Y$ then goto $k$ \par\noindent where $X$ and $Y$ are any variables and $k$ is a nonnegative integer, i.e. $k\in\om$, which is a line number. A UR-Basic program is a sequence $S_0$, $S_1$, $S_2$, $\ldots$, $S_n$ of statements. Variables only take on nonnegative integer values. The symbol $\dotminus$ means subtraction unless the result is negative and then it yields zero. The program halts if we ``goto'' to a line $k>n$. A function $f:\om\to\om$ is UR-Basic computable iff there exists a program $P$, designated input variable $X$ and output variable $Y$ such that for any $n\in\om$ if we put $X=n$ and all other variables zero and start with the first statement of $P$, then $P$ eventually halts with $f(n)$ in variable $Y$. There is a similar definition for $f:\om^m\to \om$ to be UR-Basic computable. Next we indicate how to simulate more complex statements using these three kinds of statements. When substituting multiline statements for a single statement, the ``goto'' numbers must be adjusted. \begin{tabbing} XXXXXXXXXXXXXXX \= XXXXXXXXXXXXXXXXXXXX \= \kill \underline{Basic}: \> \underline{UR-Basic}: \\ Go to k \> If $X\leq X$ then goto $k$ \\ Continue \> Let Donothing=Donothing+1\\ \> \\ Let Y=X \> 1 If $X\leq Y$ then go to 4\\ \> 2 Let Y=Y+1\\ \> 3 Go to 1 \\ \> 4 If $Y\leq X$ then go to 7 \\ \> 5 Let $Y=Y\dotminus 1$ \\ \> 6 Go to 4 \\ \> 7 Continue \\ \> \\ Constants \\ 0 \> this is a variable - we agree never to change it\\ 1 \> let $1=1+1$\\ \> \\ 2 \> Let $2=2+1$ \\ \> Let $2=2+1$ \\ \> \\ If $X Let $tempX =X$ \\ \> Let $tempX=tempX+1$\\ \> if $tempX \leq Y$ then goto $k$ \\ \>\\ If $X=Y$ then goto $k$ \> 1 If $X < Y$ then goto 4 \\ \> 2 If $Y< X$ then goto 4 \\ \> 3 Go to $k$ \\ \> 4 continue \\ \>\\ For $i=1$ to $n$ \> 1 If $n=0$ then goto 7 \\ \phantom{AAA} $S_1$ \> 2 Let $i=1$\\ \phantom{AAA} $\ldots$ \> 3 $S_1$\\ \phantom{AAA} $S_k$ \> $\ldots$ \\ Next $i$ \> 4 $S_k$\\ \> 5 Let $i=i+1$ \\ \> 6 If $i\leq n$ then goto 3\\ \> 7 continue\\ \>\\ \end{tabbing} \begin{example} The pair of functions remainder and quotient are UR-Basic computable i.e., input $n,m$ then output $q,r$ with $n=qm+r$ and $0\leq r0\\ 0 & \mbox{ if } x=0\\ \end{array}\right.$$ by $sign(x)=1\dotminus(1\dotminus x)$. \bigskip \begin{prop} The predicates $x\leq y$, $x=y$, $x1$ and $\forall y\leq x$ if $y$ divides $x$, then $y=1$ or $y=x$. \noindent are primitive recursive predicates. \bigskip\noindent Bounded search: define $f(\vec{x},z)=\mu y\leq z \; P(\vec{x},y)$ where $f$ is the least $y\leq z$ which satisfies $P(\vec{x},y)$ and $f=0$ if no $y\leq z$ can be found. \begin{prop} Suppose $Q$ is a primitive recursive predicate and $h$ a primitive recursive function. Then $$g(\vec{x})=\mu y\leq h(\vec{x}) \; P(\vec{x},y)$$ is primitive recursive. \end{prop} \proof Let $$Q(\vec{x},y)\equiv P(\vec{x},y)\wedge \forall u0$ output $q,r$ with $n=qm+r$ and $r0\to c(V,i)=0)$$ Since this is the start we want to start with Statement 0, i.e., $y=(0,V)$ and $v_0=x$ and $v_i=0$ for all $i$ with $0x$. Prove that nextprime$(x)$ is primitive recursive. \par (b) Define: $p_0=2$ and $p_n$ is the $n^{th}$ odd prime. Prove that the function $n\mapsto p_n$ is primitive recursive. \par (c) Define $c(x,i)=k$ iff $k$ is the least integer such that $p_i^{k+1}$ does not divide $x$. Prove that $c$ is primitive recursive and for any finite sequence $x_0,x_1,\ldots, x_n$ there exists $x$ such that $c(x,k)=x_k$ for all $k\leq n$. \exer Suppose that $f:\om\to\om$ is UR-Basic computable by a program $P$ and there exists a primitive recursive function $s:\om\to\om$ such that for every $x$ the program $P$ computes $f(x)$ in $\leq s(x)$ steps. Prove that $f$ is primitive recursive. \exer The programming language P-Basic has only four kinds of statements \par (a) Let $X=X+1$ \par (b) Let $X=X\dotminus 1$ \par (c) Let $X=Y$ \par \noindent where $X$, $Y$ are any variables \par (d) for-next loops, e.g. \begin{tabbing} For $i=1$ to $n$ \\ \phantom{AAA} $S_1$ \\ \phantom{AAA} $\vdots$ \\ \phantom{AAA} $S_k$ \\ Next $i$ \\ \end{tabbing} The loop variable $i$ and $n$ must be distinct and in the body of the loop ($S_1,\dots,S_k$) the variables $i$ and $n$ are not allowed to be changed, i.e., For n= 1 to $\ldots$ For i= 1 to $\ldots$ Let n = $\ldots$ Let i = $\ldots$ \noindent are not allowed. Prove that the P-Basic computable functions are the same as the primitive recursive functions. \begin{exercise}\label{pairexer} Another popular pairing function $p:\om^2\to \om$ is described by Figure \ref{pairfig}. Show that $p$ is a polynomial. Hint: the point $(m,n)$ is on the diagonal of the square of area $(m+n)^2$. \end{exercise} \def\text#1{\makebox(0,0)[cc]{#1}} \unitlength=1.20mm \begin{figure} \begin{picture}(50,50) \put(10,10){\vector(0,1){35}} \put(10,10){\vector(1,0){35}} \put(10,10){{\circle*{1}}} \put(20,10){{\circle*{1}}} \put(30,10){{\circle*{1}}} \put(40,10){{\circle*{1}}} \put(10,20){{\circle*{1}}} \put(20,20){{\circle*{1}}} \put(30,20){{\circle*{1}}} \put(10,30){{\circle*{1}}} \put(20,30){{\circle*{1}}} \put(10,40){{\circle*{1}}} \put(18,12){{\vector(-1,1){6}}} \put(28,12){{\vector(-1,1){6}}} \put(38,12){{\vector(-1,1){6}}} \put(18,22){{\vector(-1,1){6}}} \put(28,22){{\vector(-1,1){6}}} \put(18,32){{\vector(-1,1){6}}} \put(10,07){\text{0}} \put(20,07){\text{1}} \put(30,07){\text{3}} \put(40,07){\text{6}} \put(07,20){\text{2}} \put(07,30){\text{5}} \put(07,40){\text{9}} \put(22,22){\text{4}} \put(32,22){\text{7}} \put(22,32){\text{8}} \put(30,32){\text{$=p(1,3)$}} \end{picture} \caption{Pairing function $p(n,m)$, see exercise \ref{pairexer}. \label{pairfig}} \end{figure} \section{Church-Turing Thesis} \bigskip \begin{quote} Church-Turing Thesis: \par Every intuitively computable function is recursive. \end{quote} \bigskip Good evidence for Church's thesis is the fact that all other ways people have come up with to formalize the notion of effectively computable function (e.g. RAM machines, register machines, generalized recursive functions, neural nets, etc) can be shown to define the same set of functions. Church's original formal definition was using the lambda calculus. However it is not easy to see that even the elementary arithmetic functions such as successor or addition are representable in the lambda calculus. It took his student, Kleene, several weeks to prove this. Similarly, it is also true that all computable functions can be represented in John Conway's Game of Life. But this is difficult to see and so does not really give convincing evidence that the informal notion of effectively calculable has been captured. In section \ref{tur} we define the notion of Turing computable function and include Turing's analysis of why every effectively calculable function should be Turing computable. \begin{prop} There exists a \rec function $f:\om\to\om$ which is not primitive recursive. \end{prop} \proof Make an effective list $f_n:\om^{k_n}\to \om$ of all the primitive recursive functions. Define $f(n)=f_n(n)+1$ if $f_n$ is a 1-ary function, otherwise put $f(n)=0$. Since the listing is effective by the Church-Turing Thesis the function $f$ is recursive. But by the usual diagonal argument $f$ is not on the list. \qed \hmwk{3}{Fri 9-11} Prove that there exists a (total) $h:\om\to\om$ whose graph is a primitive recursive predicate but $h$ is not a primitive recursive function. Hint: consider $h(x)=\mu z \; Q(e,x,z)$. \hmwk{4}{Mon 9-13} Prove there exists a primitive recursive bijection $p:\om\to\om$ such that $p^{-1}$ is not primitive recursive. \section{Universal partial \rec function} \begin{prop}(Turing) There exists a universal \prec function $$\psi:\om\to\om$$ i.e. if we define $\psi_e(x)=\psi(\pair(e,x))$ then $\{\psi_e\st e\in\om\}$ is a uniformly computable listing of all \prec functions. \end{prop} \proof $\psi(\pair(e,x))=g(\mu z\;Q(e,x,z))$. \qed Note that for any $n\geq 2$ if $f(x_1,\ldots,x_n)$ is a \prec function then there will be $e$ such that $$\forall x_1,\ldots,x_n \;\; \psi(\la e,\la x_1,\ldots,x_n\ra\ra) =f(x_1,\ldots,x_n).$$ So $\psi$ is universal for \prec functions of any arity. \begin{prop} (Padding Lemma) There exists a 1-1 \rec function $p$ such that $\psi_e=\psi_{p(e,n)}$ for every $e,n$. \end{prop} \proof To pad the program $S_0,S_1,\ldots,S_m$ coded by $e$ just add the statement $$S_{m+1}=\rm{Let }Donothing\pair(e,n)=Donothing\pair(e,n)+1$$ and let $p(e,n)$ code this new program. \qed \begin{prop}(S-n-m Theorem). There exists a \rec function $S$ such that $\psi_{e}(\pair(x,y))=\psi_{S(e,x)}(y)$ for all $e,x,y$. \end{prop} \proof Given $\mathcal P$ the program coded by $e$ and input $x$ make-up a new program coded by $S(e,x)$ which puts $x$ into $\mathcal P$'s first input variable and then pops into program $\mathcal P$. \qed The name S-n-m comes from the obvious generalization to n-tuple $\vec{x}$ and m-tuple $\vec{y}$ $$\psi_{e}(\pair(\vec{x},\vec{y}))=\psi_{S_{n,m}(e,\vec{x})}(\vec{y})$$ so what we are stating is the S-1-1 Theorem. These propositions can be combined as follows: \begin{prop}\label{1-1-s-1-1} Suppose $\theta(x,y)$ is a \prec function. Then there is a one-to-one \rec function $f:\om\to\om$ such that $$\forall x,y\;\;\;\psi_{f(x)}(y)=\theta(x,y).$$ \end{prop} \proof Suppose $\theta=\psi_{e_0}$. Then $$\theta(x,y)=\psi_{p(S(e_0,x),x)}(y)$$ and so $f(x)=p(S(e_0,x),x)$ works. \qed We call this the 1-1-S-1-1 Theorem. \section{The \recenum sets } \begin{define} For $A\sq\om$ define: \begin{enumerate} \item $A$ is \recenum iff either $A$ is empty or $A$ is the range of a \rec function, i.e., $A=\{a_0,a_1,a_2,\ldots\}$ where the function $n\mapsto a_n$ is \rec. This is abbreviated \re \item $A$ is $\sigone$ iff there exists a \rec predicate $R\sq\om^2$ such that $$A=\{n\st \exists m \; R(n,m)\}.$$ \end{enumerate} \end{define} \begin{define}\label{defWe} $W=\{\pair(e,x)\st\psi(\pair(e,x))\conv\}$. Then $\{W_e\st e\in\om\}$ where $W_e=\{x\st \pair(e,x)\in W\}$ is a uniform listing of the \re sets. \end{define} \begin{prop}\label{simplere} For $A\sq \om$ the following are equivalent: \par (1) $A$ is \recenum. \par (2) $A$ is the domain of a \prec function. \par (3) $A$ is $\sigone$. \par (4) $A$ is finite or $A$ has a one-to-one \rec enumeration. \par (5) There exists $e$ such that $A=W_e$. \end{prop} \proof $(1)\implies (2)$: Given a \rec enumerable listing $a_n$ describe a partial \rec function $f$ by: \begin{itemize} \item input $x$ \item look for $x$ on the list: $a_0,a_1,a_2,\ldots$ \item halt if you find it, otherwise continue looking forever. \end{itemize} $(2)\implies (1)$: Define $\psi_{e,s}(x)\conv=y$ to mean that $$e,x,yx$. \item Then $x\in A$ iff $x\in \{a_i\st ib_n$. \qed \begin{prop} If $A$ and $B$ are \re sets, then $A\cap B$ is \re and $A\cup B$ is \re If $A$ and $B$ are \rec sets, then $A\cap B$, $A\cup B$, and $\comp(A)$ are all \rec sets. \end{prop} \proof Domain of $f+g$ is the intersection of domain $f$ and domain $g$. Enumerate $A\cup B$ by $x_{2n}=a_n$ and $x_{2n+1}=b_n$. \qed \hmwk{6}{Fri 9-17} Suppose that $V\sq\om$ is \re For each $n$ define $V_n=\{x\st \pair(n,x)\in V\}$. Prove that $\cup_nV_n$ is \re \hmwk{5}{Wed 9-15} Prove that every nonempty \recenum set $A$ is the range of a primitive recursive function. Extra Credit: prove that not every infinite \recenum set is the range of a one-to-one primitive recursive function. \exer (a) For a partial function $f:\om\to\om$ prove that $f$ is \prec iff its graph is \recenum. \par (b) For a \prec $h$ prove there is a \prec $g$ with $dom(g)\supseteq range(h)$ such that $$\forall y \in range(h)\;\;\; h(g(y))= y.$$ \par (c) Give an example for (b) for which $g$ cannot be total. \exer Consider a partial function $f:\om\to\om$ and the three set: \begin{enumerate} \item $dom(f)\sq\om$ \item $graph(f)\sq\om\times\om$ \item $range(f)\sq\om$. \end{enumerate} For each of the sets $(1),(2),(3)$ could be: (a) \rec or (b) \recenum but not \rec. \noindent For each of the 8 possibilities, either give an example of such an $f$ or prove there is no such $f$. Extra credit: consider the third possibility (c) not \recenum. \exer % from qual 2003-8 If $f:\omega \to \omega$, then $f^n$ denotes $f$ applied $n$ times; e.g., $f^3(0) = f(f(f(0)))$. Give an example of a (total) \rec $f$ such that $\{f^n(0):n \in \om\}$ is not \rec. \exer % from qual 2003-8 and 2001 #8 Define $V_e=\{x : \la e,x \ra\in V\}$. Prove or disprove: \begin{enumerate} \item $\exists V$ \recenum such that $\{V_e : e\in\om\}$ is the set of all \rec sets. \item $\exists V$ \rec such that $\{V_e : e\in\om\}$ is the set of all \rec sets. \item $\exists V$ \re such $\{V_e:e\in\omega\}$ is the set of all nonempty \re sets. \item $\exists f$ a \rec function such that for all $e\;\;$ $W_e\not=\emptyset$ implies $f(e)\in W_e$. \item $\exists f$ \prec such that for all $e\;\;$ $W_e\not=\emptyset$ implies $f(e)\downarrow\in W_e$. \end{enumerate} \begin{exercise} Prove there exists a \rec function $f:\om\to\om$ such that for every $e$ $$ W_e\mbox{ infinite } \to (\psi_{f(e)}:\om \to W_e \mbox{ is total, one-to-one, and onto}).$$ \end{exercise} For the definition of $W_e$ see Definition \ref{defWe}. \section{Separation and reduction} \begin{example}\label{insep} There exists disjoint \re sets $K_0$ and $K_1$ which are \recly inseparable, i.e., there is not exists a \rec set $R\sq\om$ with $K_0\sq R$ and $K_1\sq\comp(R)$. \end{example} \proof $$K_0=\{e\st \psi_e(e)\conv=0\}\rmand K_1=\{e\st \psi_e(e)\conv=1\}$$ \qed \begin{define}\label{reduction} For any $\Gamma\sq P(\om)$ define $\dualGamma$ to be the set of all $\comp(A)$ for $A\in\Gamma$ and define $\Delta=\Gamma\cap\dualGamma$. $Sep(\Gamma)$ is the property that for every $A,B\in\Gamma$ disjoint there exists $C\in\Delta$ with $A\sq C$ and $B\sq\comp(C)$. $Red(\Gamma)$ (the reduction principle) is the property that for every $A,B\in\Gamma$ there exists disjoint $A^\pr\sq A$ and $B^\pr\sq B$ with $A^\pr,B^\pr\in\Gamma$ and $A\cup B=A^\pr\cup B^\pr$. \end{define} \begin{prop} $Red(\Gamma)$ implies $Sep(\dualGamma)$. \end{prop} \proof Apply reduction to the complements. \qed \begin{prop} \label{red->sep} $Red(\sigone)$ and hence $Sep(\pione)$. \end{prop} \proof $A=\{x\st\exists u\; R(u,x)\}$ and $B=\{x\st\exists v\; S(v,x)\}$. Put $$x\in A^\pr\iff \exists u\; R(u,x)\rmand \forall v\leq u \neg S(v,x)$$ $$x\in B^\pr\iff \exists v\; S(v,x)\rmand \forall u < v \neg R(u,x)$$ \qed In example \ref{insep} it follows that $K_0$ and $K_1$ cannot be separated by disjoint $\pione$ sets $B_0$ and $B_1$ because such a $B_0$ and $B_1$ could be \recly separated. \hmwk{7}{Mon 9-20} Prove $Sep(\Gamma)$ for $\Gamma=\{A\cup B\st A\in\sigone,\; B\in\pione\}$. \section{Many-one reducibility} \begin{define} For $A,B\sq\om$ define: \begin{enumerate} \item $A\leq_m B$ iff there exists a \rec function $f$ such that $$\forall x\in\om\;\; x\in A \iff f(x)\in B.$$ Equivalently, $f^{-1}(B)=A$. Also equivalently $f(A)\sq B$ and $f(\overline{A})\sq \overline{B}$. \item $A\leq_1 B$ iff the $f$ in the definition of $\leq_m$ can be taken to be one-to-one. \end{enumerate} \end{define} \begin{prop} \begin{enumerate} \item $A\leq_1 B$ implies $A\leq_m B$. \item $A\leq_m B$ iff $\comp(A)\leq_m \comp(B)$ and similarly for $\leq_1$. \item $\leq_m$ and $\leq_1$ are transitive and reflexive. \item $A\leq_m B$ and $B$ is \rec, then $A$ is \rec. \item $A\leq_m B$ and $B$ is \recenum, then $A$ is \recenum. \end{enumerate} \end{prop} \proof Most of these are trivial. Note that $f$ reduces $A$ to $B$ then it also reduces $\comp(A)$ to $\comp(B)$. Transitivity follows by composition. For (4) if $f$ witnesses $A\leq_mB$, i.e., $$\forall n\;\; n\in A \rmiff f(n)\in B,$$ then $\chi_A(n)=\chi_B(f(n))$. For (5) suppose that $$n\in B\rmiff \exists m\;\;R(n,m)$$ and $$\forall n\;\; n\in A \rmiff f(n)\in B.$$ Then $$\forall n\;\; n\in A \rmiff \exists m\;\; R(f(n),m).$$ \qed \begin{define} \begin{enumerate} \item $A\equiv_mB$ iff $A\leq_m B$ and $B\leq_m A$. \item $m-deg(A)=\{B\st A\equiv_mB\}$, the many-one degree of $A$. \item $A\equiv_1B$ iff $A\leq_1 B$ and $B\leq_1 A$. \item $1-deg(A)=\{B\st A\equiv_1B\}$, the one degree of $A$. \end{enumerate} \end{define} \begin{exercise} \label{reduceonto}Suppose $A$ and $B$ are infinite \re sets and $A \leq_1 B$. Show there is a computable one-to-one reduction of $A$ to $B$ which maps $A$ onto $B$. \end{exercise} \section{Rice's index Theorem} Recall that $\{W_e\st e\in\om\}$ is the standard listing of all \re sets (\ref{defWe}). \begin{example} $Empty=\{e\st W_e=\emp\}$ is not \rec. \end{example} \proof Define $$\theta(e,x)=\left\{ \begin{array}{ll} \conv=0 & \mbox{ if } e\in K\\ \div & \mbox{ otherwise }\\ \end{array}\right. $$ By the S-n-m theorem there exists $f$ \rec such that $$\forall e,x\;\;\; \psi_{f(e)}(x)=\theta(e,x)$$ But then $e\in K$ iff $W_{f(e)}\neq\emp$ iff $f(e)\notin E$ so $K\leq_m \comp(E)$ and therefore $E$ not \rec. \qed \begin{prop} (Rice) If $A$ is a nontrivial index set, then $A$ is not \rec. \end{prop} \proof This is like the proof for Empty. Without loss of generality assume the index of the empty function is in $A$ and the index $e_0$ of some nonempty partial computable function is not in $A$. Define $$\theta(e,x)=\left\{ \begin{array}{ll} \psi_{e_0}(x) & \mbox{ if } e\in K\\ \div & \mbox{ otherwise }\\ \end{array}\right. $$ By the S-n-m theorem there exists $f$ \rec such that $$\forall e,x\;\;\; \psi_{f(e)}(x)=\theta(e,x)$$ But then $$e\in K \rmiff f(e)\notin A$$ and therefore $A$ is not \rec. \qed \section{Myhill's \rec permutation Theorem} \begin{theorem}\label{bij} (Myhill) $A\leq_1 B$ and $B\leq_1A$ iff there exists a \rec bijection $\pi:\om\to\om$ with $\pi(A)=B$. \end{theorem} \proof The Schroeder-Bernstein Theorem says: if there exists a 1-1 $f:A\to B$ and 1-1 $g:B\to A$, then there exists a bijection $h:A\to B$. One way to prove this is to assume $A$ and $B$ are disjoint and define a bipartite graph on the vertices $A\cup B$. Put $a\in A$ connected to $b$ iff either $f(a)=b$ or $g(b)=a$. As $f$ and $g$ are 1-1 the order of every vertex is either 1 or 2. The connected components of this graph come in 4 types, see figure \ref{fig1}. Note that in Type 1 the point $a\in A$ is not in the range of $g$ and in Type 2 the point $b\in B$ is not in the range of $f$. Type 4 components are infinite in both `directions' while Type 3 is the only finite component. \def\text#1{\makebox(0,0)[cc]{#1}} \unitlength=1.20mm \begin{figure} \begin{picture}(100,150) \put(20,70){\begin{picture}(80,80)(0,10) \put(10,90){\text{$A$}} \put(30,90){\text{$B$}} \put(5,80){\text{$a$}} \put(10,80){\vector(2,-1){19}} \put(10,80){\circle{1}} \put(20,78){\text{$f$}} \put(30,70){\vector(-2,-1){19}} \put(30,70){\circle{1}} \put(20,68){\text{$g$}} \put(10,60){\vector(2,-1){19}} \put(10,60){\circle{1}} \put(20,58){\text{$f$}} \put(30,50){\vector(-2,-1){19}} \put(30,50){\circle{1}} \put(20,48){\text{$g$}} \put(10,40){\circle{1}} \put(10,40){\vector(2,-1){19}} \put(20,30){\text{$\vdots$}} \put(20,20){\text{Type 1}} \put(50,90){\text{$A$}} \put(70,90){\text{$B$}} \put(75,80){\text{$b$}} \put(70,80){\vector(-2,-1){19}} \put(70,80){\circle{1}} \put(60,78){\text{$g$}} \put(50,70){\vector(2,-1){19}} \put(50,70){\circle{1}} \put(60,68){\text{$f$}} \put(70,60){\vector(-2,-1){19}} \put(70,60){\circle{1}} \put(60,58){\text{$g$}} \put(50,50){\vector(2,-1){19}} \put(50,50){\circle{1}} \put(60,48){\text{$f$}} \put(70,40){\vector(-2,-1){19}} \put(70,40){\circle{1}} \put(60,30){\text{$\vdots$}} \put(60,20){\text{Type 2}} \end{picture}} \put(15,-10){\begin{picture}(90,80)(0,10) \put(10,90){\text{$A$}} \put(30,90){\text{$B$}} \put(10,80){\vector(1,0){19}} \put(10,80){\circle{1}} \put(20,82){\text{$f$}} \put(30,80){\vector(-2,-1){19}} \put(30,80){\circle{1}} \put(20,77){\text{$g$}} \put(10,70){\vector(1,0){19}} \put(10,70){\circle{1}} \put(20,72){\text{$f$}} \put(30,70){\vector(-2,-1){19}} \put(30,70){\circle{1}} \put(20,67){\text{$g$}} \put(10,60){\vector(1,0){19}} \put(10,60){\circle{1}} \put(20,62){\text{$f$}} \put(30,60){\vector(-2,-1){19}} \put(30,60){\circle{1}} \put(20,57){\text{$g$}} \put(10,50){\vector(1,0){19}} \put(10,50){\circle{1}} \put(20,52){\text{$f$}} \put(30,50){\vector(-2,3){19}} \put(30,50){\circle{1}} \put(28,55){\text{$g$}} \put(20,35){\text{Type 3}} \put(60,90){\text{$A$}} \put(80,90){\text{$B$}} \put(70,85){\text{$\vdots$}} \put(80,80){\vector(-2,-1){19}} \put(80,80){\circle{1}} \put(70,77){\text{$g$}} \put(60,70){\vector(1,0){19}} \put(60,70){\circle{1}} \put(70,72){\text{$f$}} \put(80,70){\vector(-2,-1){19}} \put(80,70){\circle{1}} \put(70,67){\text{$g$}} \put(60,60){\vector(1,0){19}} \put(60,60){\circle{1}} \put(70,62){\text{$f$}} \put(80,60){\vector(-2,-1){19}} \put(80,60){\circle{1}} \put(70,57){\text{$g$}} \put(60,50){\vector(1,0){19}} \put(60,50){\circle{1}} \put(70,52){\text{$f$}} \put(70,45){\text{$\vdots$}} \put(70,35){\text{Type 4}} \end{picture} } \end{picture} \caption{ Schroeder-Bernstein connected components\label{fig1}} \end{figure} \begin{figure} \unitlength=1.36mm \begin{picture}(40,40)(-25,40) \put(10,80){\vector(1,0){19}} \put(10,80){\circle{1}} \put(20,82){\text{$f$}} \put(30,80){\vector(-2,-1){19}} \put(30,80){\circle{1}} \put(20,77){\text{$g$}} \put(10,70){\vector(1,0){19}} \put(10,70){\circle{1}} \put(20,72){\text{$f$}} \put(30,70){\vector(-2,-1){19}} \put(30,70){\circle{1}} \put(20,67){\text{$g$}} \put(10,60){\vector(1,0){19}} \put(10,60){\circle{1}} \put(20,62){\text{$f$}} \put(30,60){\vector(-2,-1){19}} \put(30,60){\circle{1}} \put(20,57){\text{$g$}} \put(10,50){\vector(1,0){19}} \put(10,50){\circle{1}} \put(20,52){\text{$f$}} \put(30,50){\vector(-2,3){19}} \put(30,50){\circle{1}} \put(28,55){\text{$g$}} \put(5,80){\text{$n_0$}} \put(5,70){\text{$n_1$}} \put(5,60){\text{$n_2$}} \put(5,50){\text{$n_3$}} \put(35,80){\text{$m_0$}} \put(35,70){\text{$m_1$}} \put(35,60){\text{$m_2$}} \put(35,50){\text{$m_3$}} \end{picture} \caption{Myhill back and forth\label{fig2}} \end{figure} To get $h$ simply define $h=f$ on any component of type 1,3, or 4 and $h=g^{-1}$ on components of type 2. The proof of Myhill's theorem is similar except we may never know exactly which type of component we are looking at. Suppose $f$ and $g$ are 1-1 \rec functions reducing $A$ to $B$ and $B$ to $A$. Effectively construct a sequence $\pi_s$ of bijections with \begin{enumerate} \item $\pi_s:D_s\to E_s$ is a bijection. \item $D_s$ and $E_s$ are finite subsets of $\om$. \item $\pi_s\sq \pi_{s+1}$. \item $n\in D_{2n}$ and $n\in E_{2n+1}$. \item if $\pi_s(n)=m$, then \label{five} either $m=fgfg\cdots f n$ or $n=gfgf\cdots g m$. \end{enumerate} In the condition \ref{five} we have dropped the parentheses to make it more readable. If we then take $\pi=\cup_s\pi_s$, then $\pi$ is a recursive bijection since we effectively constructed the sequence. It takes $A$ to $B$, because suppose $\pi(n)=m$. Then if $m=fgfg\cdots f n$ $$n\in A\rmiff fn\in B\rmiff gfn\in A\rmiff fgfn\in B\rmiff \cdots \rmiff m=fgfg\cdots f n\in B$$ similarly if $n=gfgf\cdots g m$ $$m\in B\rmiff gm\in A\rmiff fgm\in B\rmiff gfgm\in A\rmiff \cdots \rmiff n=gfgf\cdots g m\in A$$ either way $n\in A$ iff $m\in B$. At stage s=0 we take $\pi_0$ to be the empty function. At stage s+1 suppose we are given $\pi_s:D_s\to E_s$. If $s=2n$ we try to extend $\pi_s$ to include $n\in D_{s+1}$. If its already there we let $\pi_{s+1}=\pi_s$. Otherwise consider the following sequences: Let $n=n_0$, $fn_0=m_0$ and in general $f(n_k)=m_k$ and $g(m_k)=n_{k+1}$, see figure \ref{fig2}. \bigskip \par\noindent Case 1. For some $k$ we have that $m_k\notin E_s$. In this case we put $\pi_{s+1}=\pi_s\cup\{\pair(n_0,m_k)\}$. \bigskip \par\noindent Case 2. Not case 1. \bigskip In this case the connected component of the graph (see Figure \ref{fig1}) must be of Type 3, i.e., a finite closed loop. Suppose $g(m_k)=n_0$. But by condition \ref{five} if all the $m_k$ are in $E_s$, then they must map via $\pi_s^{-1}$ to the set $\{n_0,n_1,\ldots,n_k\}$ (although not in any particular order). But this is a contradiction, since $n=n_0\notin D_s$. Hence Case 2 cannot happen. \bigskip The construction at stage s+1 where $s=2n+1$ is entirely analogous except we make sure $n\in E_{s+1}$. \qed \exer Define $$Q=\{\la e_1,e_2\ra \st e_1\in W_{e_2}, \; e_2\in W_{e_1}, \rmand e_1\neq e_2\}.$$ Prove that $Q$ is creative. \section{Roger's adequate listing Theorem} \begin{theorem} (Rogers) Suppose $\rho:\om\to\om$ is \prec and we define $\rho_e(x)=\rho(e,x)$. Suppose \begin{enumerate} \item $\rho$ is universal, i.e., $\{\rho_e\st e\in\om\}$ includes all \prec functions. \item $\rho$ satisfies padding, i.e., there exists one-to-one \rec $p:\om\times\om\to\om$ such that $$\forall e,n \;\; \rho_{e}=\rho_{p(e,n)}$$ \item $\rho$ satisfies S-1-1, i.e., there exists a \rec $S:\om\times\om\to\om$ such that $$\forall e_1,e_2,x\;\; \rho_{e_1}(\pair(e_2,x))=\rho_{S(e_1,e_2)}(x)$$ \end{enumerate} Then there exists a \rec bijection $\pi:\om\to\om$ such that $$\forall e\;\; \psi_e=\rho_{\pi(e)}$$ \end{theorem} \proof Let $\psi=\rho_{e_0}$. Using padding and S-1-1 for $\rho$ we can find a 1-1 \rec function $f(e)=p(S(e_0,e))$ such that $$\forall e\;\; \psi_e=\rho_{S(e_0,e)}=\rho_{f(e)}$$ similarly there is a 1-1 \rec function $g$ such that $$\forall e\;\; \rho_e=\psi_{g(e)}.$$ By the proof of Theorem \ref{bij} there is a \rec bijection $\pi:\om\to\om$ with the property that whenever $\pi(n)=m$ then either $m=fgfg\cdots f n$ or $n=gfgf\cdots g m$. But $$\psi_n=\rho_{f n}=\psi_{gf n}=\ldots =\rho_{fgfg\cdots f n}=\rho_m$$ and $$\rho_m=\psi_{g m}=\rho_{fg m}=\ldots =\psi_{gfgf\cdots g m}=\psi_n$$ so in either case $\psi_n=\rho_{\pi(n)}$. \qed \hmwk{8}{Wed 9-22} Find an example of a \prec $\rho$ which is universal but fails to satisfy padding. Find an example which is universal, satisfies padding but fails to satisfy S-1-1. (S-1-1 implies padding see Soare p.25-26.) \section{Kleene's Recursion Theorem} \begin{theorem} (Kleene - Recursion Theorem) For any \rec function $f$ there exists an $e$ with $\psi_e=\psi_{f(e)}$. \end{theorem} \proof Define a \prec function $\theta$ by $$\theta(u,x)=\psi_{\psi_u(u)}(x)=\psi(\la\psi(\la u,u\ra),x\ra)$$ By padding-S-1-1 we can find a (one-to-one) \rec function $d:\om\to\om$ such that $$\forall u\;\; \psi_{d(u)}(x)=\theta(u,x)$$ Let $v$ be an index for $f\circ d$, i.e., $$\forall x \;\; \psi_v(x)=f(d(x))$$ Put $e=d(v)$ then $$\psi_e(x)=\psi_{d(v)}(x)=\theta(v,x)=\psi_{\psi_v(v)}(x)= \psi_{f\circ d(v)}(x)=\psi_{f(e)}(x)$$ \qed From the proof we can get an infinite \rec set of fixed points $e$, since we can take any $v^\pr$ such that $\psi_{v^\pr}=f\circ d$ and set $e^\pr=d(v^\pr)$. Also note that our fixed point $e$ is obtained effectively from an index for $f$, so given a \rec $f:\om\times\om\to \om$ if we let $f_n:\om\to\om$ be defined by $f_n(x)=f(n,x)$ then we get a fixed points $e_n$ $$\psi_{e_n}=\psi_{f_n(e_n)}$$ and the function $h(n)=e_n$ is \rec. This is called the recursion theorem with parameters: \begin{theorem} For any \rec function $f:\om^2\to\om$ there exists a 1-1 \rec function $h:\om\to\om$ such that $\psi_{h(x)}=\psi_{f(x,h(x))}$ for all $x$. \end{theorem} \begin{example} There are infinitely many $e$ such that $\psi_e(0)=e$. There are infinitely many $e$ such that $W_e=\{e\}$. \end{example} \proof Define $\theta(e,x)=e$ for all $e$. By the S-n-m Theorem there exists a \rec $f$ such that $$\forall e,x\;\; \psi_{f(e)}=\theta(e,x)$$ By the Recursion Theorem there are infinitely many fixed points for $f$, i.e., $$\psi_e=\psi_{f(e)}$$ and for each of these $\psi_e$ is the constant function $e$. Define a \prec function $\theta$ by $$\theta(e,x)=\left\{ \begin{array}{ll} \conv=0 & \mbox{ if } e=x \\ \div & \mbox{ otherwise } \end{array}\right. $$ By S-n-m theorem there is a \rec function $g$ with $\psi_{g(e)}(x)=\theta(x)$. By the definition of $\theta$ we see that for every $e$: $$ W_{g(e)}=\{e\}$$ By the Recursion Theorem there are infinitely many fixed points for $g$ and for any of them $$W_e=W_{g(e)}=\{e\}.$$ \hmwk{9}{Fri 9-24} Prove: \par (a) for every $f,g$ \rec functions, there exists $e_1$ and $e_2$ such that $\psi_{f(e_1)}=\psi_{e_2}$ and $\psi_{g(e_2)}=\psi_{e_1}$ \par (b) $\exists e_1\neq e_2\;\;\;\; W_{e_1}=\{e_2\}, \; W_{e_2}=\{e_1\}$ \par (c) $\exists e_1>e_2>e_3\;\;\;\; W_{e_1}=\{e_2\}, \; W_{e_2}=\{e_3\}, \; W_{e_3}=\{e_1\}$ \exer Suppose $V\subseteq \omega$ is \recenum. Show there exists infinitely many $e$ such that $W_e=V_e$ where $V_e=\{n:\la e,n\ra\in V\}$. \exer Prove there is a strictly increasing \rec function $f:\om\to\om$ such that $W_{f(n)}=\{n+f(n)\}$ for all $n$. \begin{example} (Smullyan) For any \rec functions $f(x,y)$ and $g(x,y)$ there exists $a,b\in\om$ such that $$\psi_{f(a,b)}=\psi_a \rmand \psi_{g(a,b)}=\psi_b$$ \end{example} \proof By the recursion theorem $$\forall x\;\exists y \;\; \psi_{g(x,y)}=\psi_{y}$$ but since the fixed point $y$ is obtained effectively from $x$ and an index for $g$ there exists a \rec function $h$ such that $$\forall x\;\; \psi_{g(x,h(x))}=\psi_{h(x)}$$ Apply the fixed point theorem to $f(x,h(x))$ there exists $a\in\om$ such that $$\psi_{f(a,h(a))}=\psi_a$$ Letting $b=h(a)$ does the job. \qed \hmwk{10}{Mon 9-27} Prove \par (a) $\exists e_1\hat{d}(e-1)$ or \item $d(e_s)=d(e_t)$ for some $t2e\; x\in W_{e,s}$. Put $A_{s+1}=A_s\cup\{x\}$ for the least $e$ and $x$ for which this is true. If this happens we say that $e$ has acted at stage $s+1$. If there no such $e$, then put $A_{s+1}=A_s$. The set $A=\cup_s A_s$ is simple. Note that each $e$ can act at most once. Hence if $W_e$ is infinite and $W_e\cap A=\emp$, eventually there will come a stage $s$ where $\exists x>2e\; x\in W_{e,s}$ and all smaller $e$'s which will ever act have already acted at a previous stage. But then $e$ will act, which is a contradiction. Also we see that $\comp(A)$ is infinite because for all $e$ $|A\cap 2e|\leq e$ since the only $e^\pr$ which can put an $x$ into $A$ with $x\leq 2e$ are those $e^\pr$ with $e^\prn\}$. (Hint: it is easier to show there exists $e\in A$ such that $W_e=\{e\}$.) \begin{exercise} \label{simplereduce} Show that \begin{enumerate} \item[(a)] If $A\leq_1 B$ and $B$ is simple, then $A$ is simple or $\comp(A)$ is finite. \item[(b)] If $A$ and $B$ are simple, then $A \cup B$ is simple. \item[(c)] If $A$ is simple, $b\in\comp(A)$, and $B=A\cup\{b\}$, then $B<_1 A$ and if $B\leq_1 C\leq_1 A$ then $C\equiv_1 B$ or $C\equiv_1 A$. \end{enumerate} \end{exercise} \section{Oracles} \begin{define} $A\leq_T B$ or $A$ is Turing reducible to $B$. Add to the UR-Basic programming language statements of the form: $$\mbox{ Let } y=\chi_B(x)$$ for any variables $x,y$. This programming language is called Oracle UR-Basic. Then $A\leq_T B$ iff there is an Oracle UR-Basic program with Oracle for $B$ which computes the characteristic function $\chi_A$ of $A$. \end{define} \section{Dekker deficiency set} \begin{prop}\label{dekker} (Dekker Deficiency Set) For every \re set $A$ which is not \rec there exists a simple set $B$ with $B\equiv_T A$. \end{prop} \proof Let $\{a_n\st n\in \om\}$ be a 1-1 \rec enumeration of $A$. Define $$B=\{n\st \exists m>n\;\; a_ma_n$ for all $n>N$ and then $A$ would be \rec. $A\leq_T B$: Input $x$. Find $n\in\comp(B)$ such that $a_n>x$. Then $x\in A$ iff $x\in\{a_i:ic$, $b>c$, and for all $d$ if $d\leq a$ and $d\leq b$ then $d\leq c$. \end{prop} \proof This is a relativization of the above argument. Construct $A_0$ and $B_0$ so that for every $e$ $$\{e\}^C\neq A_0\join C \rmand \{e\}^C\neq B_0\join C$$ and $$\{e_1\}^{A_0\join C}= \{e_2\}^{B_0\join C}=D \implies D\leq_T C$$ Then take $A=A_0\join C$ and $B=B_0\join C$. \qed \prob Find a minimal triple, i.e., $a,b,c\in\degrees\sm\{0\}$ such that $$\forall d\;\; (d\leq a\rmand d\leq b\rmand d\leq c)\to d=0$$ but no 2 are a minimal pair. \par Hint: Construct $X,Y,Z$ non \rec so that $$(\{e_0\}^{X\oplus Y}=\{e_1\}^{Y\oplus Z}=\{e_2\}^{X\oplus Z}=D) \to D \leq_T 0.$$ \prob Prove: \par (a) There exists $A\su\om$ such that $A_n\not\leq_T\hat{A}_n$ for every $n$ where $$A_n=\{x:\la n,x\ra\in A\} \rmand \hat{A}_n=\{\la m,x\ra : m\neq n \rmand \la m,x\ra\in A\}.$$ \par (b) There exists Turing degrees $a_r$ for $r\in {\mathbf Q}$ such that for all $r,s\in {\mathbf Q}\;\;$ ($ro$ there exists $a\in\degrees$ with $a>o$ and $a\wedge b=0$. \exer Prove that for every $c\in\degrees$ with $c\geq o^\pr$ that there exists incomparable degrees $a$ and $b$ with $a\wedge b=0$, and $a\vee b = c$. Hint: one way to code a set $C$ into $A\join B$ is to use boot-strapping. Define $$x_{2n}=\mu x>x_{2n-1}\; A(x)=1$$ $$x_{2n+1}=\mu x>x_{2n}\; B(x)=1$$ $$n\in C \rmiff x_n \mbox{ is even. }$$ \section{Spector: exact pairs} \begin{prop}(Spector) \label{exactpair} Given $(a_n\st n<\om)$ in $\degrees$ with $a_nn$ that $f_s(\pair(n,m))=f_{n+1}(\pair(n,m))$. Furthermore, except for the finitely many element of the domain of $\si_{n+1}$ we have that $A_n(m)=f_{n+1}(\pair(n,m))$. It follows that $A_n=^*B_n$ and so $A_n\leq_T B_n\leq_T B$. Similarly for $C$. \bigskip Claim. Suppose that $D\leq_T B$ and $D\leq_T C$. Then $D\leq_T A_n$ for some $n<\om$. To see this suppose that $$\{e_1\}^B=\{e_2\}^C=D$$ and $s=\pair(e_1,e_2)$. Since the characteristic functions of $B$ and $C$ extend $\sig_{s+1}$ and $\tau_{s+1}$ respectively it is evident that Case (a) could not have occurred. So we assume Case (b). Note that in this case it is impossible that there exists $n,\rho_1,\rho_2$ with $\sig_s\sq \rho_1$ and $\sig_s\sq\rho_2$, and each of $\rho_1$ and $\rho_2$ compatible with $f_s$ such that $$\{e_1\}^{\rho_1}(n)\conv\neq \{e_1\}^{\rho_2}(n)\conv.$$ This is because $\{e_2\}^C(n)\conv$ and so then we would be in Case (a). It follows easily as before that $D=\{e_1\}^B\leq_T f_s$. But $$f_s\leq_T A_0\join A_1\join\cdot\join A_{s-1}\leq_t A_{s-1}$$ so $D\leq_T A_{s-1}$. \qed \exer Suppose $a,b\in\degrees$ and $a\wedge b$ does not exist. Prove there exists $(c_n\in\degrees:n<\om)$ such that \begin{enumerate} \item $c_n\leq a$ and $c_n\leq b$ for all $n$, \item $c_nq$ with $q^\prq$ put $f_{s+1}(q^\pr)=$`waiting'. \end{enumerate} We say that $R_q$ acted at stage $s+1$. If there is no such $q$ then we just continue to wait. In either case assign $x=(s,s+1)$ to be the follower of $R_s$ and put $f_{s+1}(s)=$`waiting'. This ends the stage and the construction. Note that the sequence $$(A_{s,0},A_{s,1},f_s,x_{q,s}\st s\in\om,\;qs_0$ the follower of $R_q$ at stage $s$ is that same as at stage $s_0$. \item $R_q$ is met, i.e, $\{e\}^{A_i}\neq A_{1-i}$ \item $R_q$ acts at most finitely many times. \end{enumerate} \proof This is the main claim and it is proved by induction on $q$. So suppose that (3) is true for all $q^\prs_0$ we have that $\{e\}^{A_{i,s}}_s(x_q)\conv =0$ with use less than $s$ or \noindent (b) not (a). \bigskip Suppose (a). In this case since no higher priority $q^\pr$ acts after stage $s_0$ then $R_q$ will act. Hence $x_q$ is put into $A_{1-i}$. Furthermore all other followers of lower priority requirements appointed now or at future stages will be larger than the use of the computation $\{e\}^{A_{i,s}}_s(x_q)$ (we assume that $s\leq \pair(q^\pr,s)$). Hence $$\{e\}^{A_{i}}(x_q)\conv=0\neq 1=A_{1-i}(x_q)$$ Suppose (b). In this case it must be that either $$\{e\}^{A_{i}}(x_q)\div \rmor \{e\}^{A_{i}}(x_q)\conv\neq 0.$$ In either case $x_q$ is never put into $A_{1-i}$ - this is because the possible followers of two distinct requirements are disjoint and no follower is used again for the same requirement. So $A_{1-i}(x_q)=0\neq \{e\}^{A_{i}}(x_q)$ and thus $R_q$ is met. So as we see $R_q$ will act at most one more time after stage $s_0$ and so it acts only finitely many times. This proves the Claim and the Theorem. \qed We say that $R_q$ is injured when it is made to appoint new followers and start over. Hence, the terminology `finite injury priority argument'. \begin{cor} There exists a set $A$ which is \re and $0<_T A<_T \jump(0)$. \end{cor} \proof Since $0$ and $\jump(0)$ are $\leq_T$ comparable to every \re set it must be that both $A_i$ from the Friedberg-Muchnik Theorem are strictly in between. \qed \exer (Trachtenbrock) % Soare p.121 2.5 \par Define $A$ is auto-reducible iff there exists $e$ such that for all $x$, $$\{e\}^{A\setminus\{x\}}(x)\downarrow=A(x).$$ Prove \par (a) For all $B$ there exists $A\equiv_m B$ such that $A$ is auto-reducible. \par (b) There exist \anre $A$ which is not auto-reducible. \par (c) There exist a low \re $A$ which is not auto-reducible. \par (d)* There exist a \re $A\equiv_T K$ which is not auto-reducible? \section{Embedding in the \re degrees} \bigskip We define $$A_n=\{x\st \pair(n,x)\in A\}$$ and $$\join_{k\neq n}A_k=\{\pair(k,x)\in A\st k<\om\rmand k\neq n\}.$$ \begin{theorem} There exists \anre set $A$ such that for every $n$ $$A_n\not\leq_T \join_{k\neq n}A_k$$ \end{theorem} \proof This is a minor modification of the Friedberg-Muchnic argument (Theorem \ref{fm}). Our requirements are: $R_{\pair(e,n)}\;\;\;\;\;\; \{e\}^{\join_{k\neq n}A_k}\neq A_{n}$ for $e,n\in\om$. And the construction is nearly the same: At stage $s+1$ look for the least $q=\pair(e,n)q$ with $q^\prq$ put $$f_{s+1}(q^\pr)=\mbox{`waiting'}.$$ \end{enumerate} Finally, assign $x=(s,s+1)$ to be the follower of $R_s$ and $f_{s+1}(s)=$`waiting'. The verification is virtually the same as in the Friedberg-Muchnic Theorem. \qed \begin{cor} Every \rec partially ordered set embeds into the \re degrees $\redegrees$. \end{cor} \proof Let $\poset=(\om,\unlhd)$ be a partial order with $\unlhd$ a \rec binary relation on $\om$. Define $J(p)=\{\pair(q,x)\in A \st q\unlhd p\}$ and let $j(p)=deg(J(p))$. Then $$j:\poset\to \redegrees$$ is an order preserving embedding. \qed \hmwk{20}{Mon 10-25} Prove there exists a \rec partial order $\poset_0=(\om,\leq_0)$ such that every countable partial order $\poset_1$ can be embedded into it, i.e., there exists a 1-1 mapping $j:\poset_1\to\poset_0$ such that $p\leq_1 q$ iff $j(p)\leq_0 j(q)$. Hint: Construct $\poset_0$ so that for every pair of finite posets $\poset_1\su \poset_2$ and embedding $j_1:\poset_1\to\poset_0$ there is an embedding $j_2:\poset_2\to\poset_0$ with $j_1\su j_2$. \bigskip It follows from this exercise that every countable partial order embeds into the \re degrees. \hmwk{21}{Wed 10-27} Prove that for every creative set $A$ there exist a set $B$ which is \re and disjoint from $A$ but cannot be separated from it by a \rec set. Prove that there exists disjoint \re sets $A_0$ and $A_1$ which are \recly inseparable but not creative. Hint: Construct $A_0$ and $A_1$ as in Theorem \ref{fm} with the additional requirements: $$ R_e\;\;\;\; \psi_e = D \rightarrow D \mbox{ does not separate } A_0 \rmand A_1$$ \section{Limit Lemma and Ramsey Theory} \begin{lemma}\label{limitlemma} (The Limit Lemma) Suppose $g\in\om^\om$, then \noindent $g\leq_T \jump(0)$ iff \noindent there exists $f:\om\times\om\to\om$ \rec such that for all $n$ $$\lim_{s\to\infty}f(n,s)=g(n).$$ \end{lemma} \proof Suppose $g=\{e\}^{\jump(0)}$. Let $(\jump(0)_s\st s\in\om)$ be a \rec enumeration of $\jump(0)$, e.g., $\jump(0)_s=\{es_0$ we have that $f(n,s)=f(n,s_0)$. (Try $s_0=0$ and ask the oracle if the computation that searches for a change in $f$ ever terminates. If yes, try $s_0=1$, etc. Continue incrementing $s_0$ until the oracle says that beyond this stage $f$ does not change.) It follows that $g(n)=f(n,s_0)$. Hence there is an algorithm with oracle $\jump(0)$ which computes $g$. \qed \begin{define} $[X]^n=\{s\sq X\st |X|=n\}$ \end{define} Ramsey Theorem says that for every $n,k<\om$ and $f:[\om]^n\to k$ there is $H\in [\om]^\om$ such that $f\res [H]^n$ is constant. This $H$ is called homogeneous for $f$. \begin{example} (Jockusch, Spector) There is a \rec $f:[\om]^3\to 2$ such that $\jump(0)\leq_T H$ for every infinite $H$ which is homogeneous for $f$. \end{example} \proof Define $$f(\{e_02e$ and $A_s\cap W_{e,s}=\emp$ and put $x$ into $A_{s+1}$. The strategy for $N_e$ is to wait until we see convergence and then try to prevent the computation from changing by restraining numbers less than the use of the computation from entering $A$. The requirement $P_e$ is positive since the strategy trys to put things into $A$ while the requirement $N_e$ is negative since it tries to keep things out of $A$. \begin{center} Construction \end{center} At each stage in the construction we will have $A_s$ and $r(e,s)$ for each $e$. We will always have that $r(e,s)=0$ for $e\geq s$ so the function $r$ is really a finite function. Stage $s+1$. Look for the least $e2e$ with $x\in W_{e,s}$ and $x>r(e^\pr,s)$ for all $e^\prs_0$ and $e^\prs_0$ there will be a $x\in W_{e,s}$ such that $x>2e+R$. At stage $s+1$ either $A_s\cap W_{e,s}\neq\emp$ or $P_e$ will act. In either case $P_e$ is met. (2) Choose $s_0$ so that no $P_{e^\pr}$ for $e^\pr\leq e$ acts after stage $s_0$. This means that after stage $s_0$ no positive requirement can ever injure a computation of $N_e$. Hence if there is some $s_1>s_0$ such that $\{e\}_{s_1}^{A_{s_1}}(e)\conv$ then no $xs_0$ or we see convergence and then $r(e,s)=r(e,s_1)$ for all $s>s_1$. \bigskip This finishes the proof of the Claim and the Theorem. \qed \hmwk{19}{Fri 10-22} (From Soare) A set $A$ is auto-reducible iff there exists $e$ such that for every $x$ we have $$\{e\}^{A\sm \{x\}}(x)\conv=A(x).$$ Prove there is a \re set which is not auto-reducible. Extra credit: Prove that there exists a $A$ low simple set which is not auto-reducible. \section{Friedberg splitting Theorem} \begin{theorem} (Friedberg Splitting) Every \re set which is not \rec is the disjoint union of two \recenum sets which are not \rec. \end{theorem} \proof Suppose $B=\{b_s\st s<\om\}$ is a one-one \rec enumeration of the non\rec set $B$. We will decide at each stage to put $b_s$ into either $A_0$ or $A_1$. Hence at any stage $s$ we will have $$B_s=\{b_t\st ts_0$ such that $x\in B_s\cup W_e^s$. Case 1. $x\in B_s$. Hence $x\in B$. Case 2. $x\in W_e^s\sm B_s$. We claim that $x\notin B$. If it were then for some $t>s>s_0$ we would have $x=b_t$ and at that stage we would put $b_t$ into $A_i$. But we are assuming $A_i\cap W_e=\emptyset$ and this would be a contradiction. \qed \exer Suppose $B$ is a \re set which is not \rec. Prove there exists a partial \rec function $f$ with domain $B$ such that for every $n<\om$ the set $f^{-1}\{n\}$ is not computable. \exer Prove or disprove. There exists $A_n$ for $n<\om$ pairwise disjoint \re sets which are not \rec such that $$\om=\sqcup_{n<\om}A_n.$$ \hmwk{22}{Fri 10-29} Define $f$ is proper iff $f$ is a \prec function and both the domain and range of $f$ are non\rec subsets of $\om$. Prove that for every proper $f$ that there exists proper $f_0$ and $f_1$ with $f$ the disjoint union of $f_0$ and $f_1$. (We are identifying the functions with their graph.) \exer Show that if $B$ is \re but not \rec, then there exists $A_i$ \re such that $B=A_0\sqcup A_1$ and $A_0$ and $A_1$ cannot be separated by a \rec set. Hint: If $\psi_e$ is total, show that there must be infinitely many $s$ such that $\psi_{e,s}(b_s)\downarrow$. \section{Sacks splitting Theorem} \begin{theorem} (Sacks) Suppose $0<_T C\leq_T \jump(0)$ and $A$ is \re Then there exists \re sets $A_0$ and $A_1$ such that \begin{enumerate} \item $A$ is the disjoint union of $A_0$ and $A_1$, i.e., $A=A_0\sqcup A_1$, \item $C\not\leq_T A_i$ for $i=0,1$, and \item $A_i$ is of low degree for $i=0,1$, i.e., $\jump(A_i)\equiv_T\jump(0)$. \end{enumerate} \end{theorem} \proof By the limit lemma there exists a \rec function $g:\om\times\om\to 2$ such that for every $n$ $$C(n)=\lim_{s\to \infty} g(s,n).$$ To simplify notation let $C_s(n)=g(s,n)$. Let $A=\{a_s\st s\in\om\}$ be a 1-1 \rec enumeration of $A$. If $A$ is finite or even \rec the result is trivially true, so we don't have to worry about that case. We will achieve the splitting of $A$ by simply putting $a_s$ into exactly one of the two sets $A_0$ or $A_1$ at stage $s+1$. \begin{center} The Requirements \end{center} The lowness of the sets will be achieved by the same requirements as in the low simple set proof: $N_{e,i}\;\;\;\;\;\; (\exists^\infty s \;\;\{e\}^{A_{i,s}}(e)\conv )\implies \{e\}^{A_{i}}(e)\conv$ \noindent Our new requirements are for each $e\in\om$ and $i=0,1$: $R_{e,i}\;\;\;\;\;\;\; \{e\}^{A_i}\neq C$ \noindent which we will write $R_q=R_{e,i}$ where $q=2e+i$. If we meet each of these, then $C\not\leq_T A_i$ for $i=0,1$. The strategy used for meeting $R_{e,i}$ is to preserve the length of agreement between $\{e\}^{A_i}$ and $C$. This seems contradictory, since we want them to be different. The reason it succeeds is because otherwise we will be able to compute $C$. For each $q$ we will have two variables $l_q$ and $u_q$ which are the length of agreement and the use of some computations. We will use $u_q$ to restrain for both $N_q$ and $R_q$. \begin{center} The Construction \end{center} At stage $s=0$ put $A_{i,s}=\emp$ and put $u_q=l_q=0$. \bigskip \noindent {\bf Stage $s+1$.} Begin by computing the length of agreement $l_q$ and the usage $u_q$ for each $qs_0$ and also $\{e\}^{A_i}\res x$ will be same computations as $\{e\}^{A_{i,s_0}}_{s_0}\res x$, i.e., the use of the oracle has settled down. After $s_0$ the variable $l_q$ will be incremented until it is at least $x$, if it isn't already. This proves subclaim (a). \bigskip\noindent Now go to a stage $s_0$ such that for all $s>s_0$ \begin{enumerate} \item for all $p \max\{U_{p}\st ps_0$ is a stage where $l_q$ is incremented then $$C(x)=\{e\}^{A_{i,s}}_s(x).$$ for any $xs_0$ where $l_q>x$ and it has just been incremented. Then $C(x)=\{e\}^{A_{i,s}}_s(x)$. This contradiction proves the main Claim part (1) that $R_q$ is met. \begin{center} Proof of (2) \end{center} \noindent Since $R_q$ is met there exists $x$ such that either \par (a) $\{e\}^{A_{i}}(x)\div$ or \par (b) $\{e\}^{A_{i}}(x)\conv\neq C(x)$. \noindent Fix any such $x$. Go to a stage $s_0$ such that for all $s>s_0$ \begin{enumerate} \item for all $p \max\{U_{p}\st ps_0$ where $l_q>x$ that $l_q$ is incremented. This is because at such a stage $s$ $$\{e\}_s^{A_{i,s}}(x)\conv= C_s(x).$$ For the rest of the construction $u_q$ will protect the computation $\{e\}_s^{A_{i,s}}(x)$. But then $$\{e\}^{A_{i}}(x)=\{e\}_s^{A_{i,s}}(x)= C_s(x)=C(x)$$ which contradicts the choice of $x$. \begin{center} Proof of (3) \end{center} \noindent Note that $u_q$ changes only when either $l_q$ is incremented or when we see $\{e\}^{A_{i,s}}_s(e)$ converges. Hence if we go to a stage $s_0$ such that for all $s>s_0$ \begin{enumerate} \item for all $p \max\{U_{p}\st pR_\beta$ with $x\in F_\beta$ and $xn: f\res n\sq f_s\}$$ these are the true stages and note that $T_{n}\sq T_{n-1}$. The set $T_n$ is a \rec set which (by induction) is infinite. Define $f(n)$ by $$f(n)=\liminf_{s\in T_n} f_s(n).$$ If $\beta=f\res n$ is working on $P_{e,i}$, then $f(n)=$`act' if $P_{e,i}$ every acts, and otherwise $f(n)=$`wait', meaning we wait forever. In the case $\alpha=f\res n$ is working on a negative requirement $f(n)$ will be $\infty$ if there are infinitely many $s\in T_n$ in which the length of agreement $l_\alpha$ has been incremented and otherwise it will be the final value of $l_\alpha$. \bigskip \noindent {\bf Claim.} For each $n$ the requirement that $f\res n$ is working on is met. \proof \bigskip {\bf Case} $f\res n=\beta$ is working on $P_{e,i}$. \medskip If $f(n)=$`act', then for some $x$ we put $x$ into $A_i$ at a stage $s$ where we saw $\psi_{e,s}(x)\conv=0$. But then $A_i(x)=1\neq \psi_e(x)$. If $f(n)=$`wait', let us first prove that $R_\beta$ does not change at any stage $s\geq \min(T_n)$. We first note that for every $s>\min(T_n)$ that it is not true that $f_s<_{lex} \beta$. Why? Suppose $f_s\res k=\beta\res k$ and $f_s(k)<\beta(k)$. If $\beta(k)=$`wait' and $f_s(k)$=`act', then we get a contradiction, since then $\beta$ is not on the true path $f$. In the case of a negative requirement $\alpha=\beta\res k$ then $\beta(k)=l<\om$ (since nothing is to the left of $\infty$), but this would mean that the true path would go to the left of $\beta$. It follows that for every $s\in T_n$ the variables $\{u_\alpha:\alpha<_{lex}\beta\}$ will be what they were at the stage $s=min(T_n)$. Similarly for any $u_\alpha$ with $\alpha\sq\beta$ and $\beta(|\alpha|)\neq\infty$ these variables will have also reached their maximum since $u_\alpha$ is only changed when $l_\alpha$ is incremented. To see that $P_{e,i}$ is met in this case let $R_\beta^*$ be this final value of $R_\beta$. Let $x\in F_\beta$ with $x>R_\beta^*$. It is not the case that $\psi_e(x)\conv=0$, because if this ever happened then for some large enough stage $s\in T_n$ the worker $\beta$ would have acted (either putting this or some smaller $x$ into $A_i$. Since $x$ is never put into $A_i$ the requirement is met because $\psi_e(x)\neq 0=A_i(x)$. \bigskip {\bf Case} $f\res n=\alpha$ is working on $N_{e_0,e_1}$. \medskip {\bf Subcase} $f(n)=l$ \noindent Then for every $s\in T_{n+1}$ the length of agreement was less than $l+1$, i.e. for some $x\leq l+1$ it was not true that: $$\{e_0\}^{A_0,s}_s(x)\conv = \{e_1\}^{A_1,s}_s(x)\conv$$ otherwise we would have incremented $l_\alpha$. It follows that $$\neg (\{e_0\}^{A_0}=\{e_1\}^{A_1}=B)$$ and so $N_{e_0,e_1}$ is satisfied. \medskip {\bf Subcase} $f(n)=\infty$ \noindent Then we claim that $B$ is \rec. To see this suppose $s_1g_s$ such that $V_{e,s}\sq [0,g]$, and \item permanently assign $V_x$ to be $[0,g_{s+1}]$, i.e., set $V_{x,s+1}=[0,g_{s+1}]$ and never change $V_x$ again. \end{enumerate} End the stage. \begin{center} Verification \end{center} \bigskip \noindent {\bf Claim 1.} The following are equivalent for any $e$: \begin{enumerate} \item $W_e$ is not an initial segment of $\om$ and $W_e\neq W_{\hat{e}}$ for each $\hat{e}y$ will be appointed after stage $s_0$. But such a follower will always remain loyal. \qed Let $D=\cup_{s\in\om} D_s$ be the set of disloyal followers. Then $\comp(D)$ is the set of permanent followers. \bigskip \noindent {\bf Claim 2.} \begin{enumerate} \item $\{V_x\st x\in\comp(D)\}$ is the set of \re sets which are not initial segments. \item There exist a \rec set $G$ such that $$\{[0,n]\st n\in G\}=\{V_x\st x\in D\}.$$ \item $V_x\neq V_{x^\pr}$ unless $x= x^\pr$. \end{enumerate} \bigskip \proof Part (1) follows from Claim 1. For Part (2), since the sequence $g_s$ is non-decreasing we see that $$G=\{g_s\st s\in\om\}$$ is \rec. For Part (3) note that there are two types of $V_x$. If $x$ is a permanent follower of some $R_e$ and then $V_x=W_e$ where $W_e$ is not an initial segment and $W_e$ is distinct from each $W_{\hat{e}}$. Or $x$ is a disloyal follower at some stage $s+1$ and then $V_x=[0,g_{s+1}]$. Since the sequence $g_s$ is bumped up each time it is used we see that the $V_x$ for disloyal followers are distinct finite initial segments. This proves Claim. \qed Let us show how to modify $V$ to $U$ to prove Friedberg's enumeration without repetition theorem. Note that $V$ uniquely enumerates every \re set except $\om$, $\emp$, and the finite initial segments of the form $[0,n]$ where $n\notin G$. Let $\{x_n:11$, and $U_{2n+1}=V_n$. \qed \begin{define}\label{defreclass} A family of subsets $\vv$ of $\om$ is called \anre class iff there exists \anre set $V$ such that $$\vv=\{V_e\st e\in\om\}$$ where $V_e=\{x\st \la e,x\ra\in V\}$. $V$ is call an enumeration of $\vv$. If $V_e\neq V_{e^\pr}$ whenever $e\neq e^\pr$ then $V$ is called a Friedberg enumeration of $\vv$. \end{define} \begin{theorem} If $\vv$ is \anre class containing all initial segments, then $\vv$ has a Friedberg enumeration. \end{theorem} \proof This is an obvious modification of the proof of Theorem \ref{uniqenum}. \qed \begin{example} (Pour-El, Putnam) There is \anre class consisting of infinitely many one and two element sets which has no Friedberg enumeration. \end{example} \proof Take $A$ to be any set which is \re but not \rec. Let $F_n=\{2n,2n+1\}$ and $G_n=\{2n\}$. Then $$\vv=\{F_n\st n\in\om\}\cup \{G_n\st n\in\comp(A)\}$$ is \anre class. This is because we just enumerate $2n+1$ into $G_n$ turning it into $F_n$ when $n$ is enumerated into $A$). But $\vv$ cannot have a Friedberg enumeration $V$ since then: $$\forall n\;\; (n\in\comp(A) \rmiff \exists x,y\;\; x\neq y \rmand 2n\in (V_x\cap V_y)).$$ \qed \begin{example} (Pour-El, Putnam) There is an infinite \re class $\vv$ containing $\om$ such that any enumeration of $\vv$ must list $\om$ infinitely many times. \end{example} \proof Let $A$ be any \re set which is not \rec. Let $\vv$ be the class of \re sets $B$ such that $B\su\comp(A)$ or $B=\om$. To see that $\vv$ is \anre class just enumerate each $W_e$ into $V_e$ as long as you see that $A_s\cap W_{e,s}=\emp$. If this ever fails, enumerate all of $\om$ into $V_e$. If there is an enumeration of $\vv$ which only lists $\om$ finitely many times, then there is an enumeration $U$ of the elements of $\vv$ which are not $\om$. But then $$\comp(A)=\bigcup\{U_e\st e\in\om\}$$ would the be \anre set. \qed It seems to require a more complicated proof than that for Theorem \ref{unique} to show: \begin{theorem} (Friedberg) The class of graphs of partial \rec function has a Friedberg enumeration. \end{theorem} \exer Prove that the family of \rec sets is \anre class and has a Friedberg enumeration. \exer Prove that the family of \re sets which are not simple is \anre class and has a Friedberg enumeration. \section{Hypersimple sets} \begin{define} Coding finite sets. For $D\sq \om$ let $x=\sum_{n\in D} 2^n$. Write $D_x=D$. \end{define} \begin{define} $(D_x\st x\in R)$ is a strong array iff $R$ is an infinite \rec set and for every $x,y\in R$ we have $D_x\cap D_y=\emp$ whenever $x\neq y$. \end{define} \begin{define} A set $A\sq\om$ is hypersimple iff $A$ is \re, $\comp(A)$ is infinite, and for every strong array $(D_x\st x\in R)$ there exists $x\in R$ such that $D_x\sq A$. \end{define} \begin{prop} (Post) \label{posthsimple} \par(1) Hypersimple implies simple. \par(2) There is a simple set which is not hypersimple. \par(3) There is a hypersimple set. \end{prop} \proof \noindent (1) If $A$ is not simple, then there exists an infinite \rec set $R\sq\comp(A)$. Then $\{D_{2^x}\st x\in R\}$ witnesses that $A$ is not hypersimple. \noindent (2) In Post's original construction of a simple set $A$ (see Theorem \ref{simple}) we constructed a simple set $A$ by waiting until there was some $x\in W_{e,s}$ with $x>2e$ and $W_{e,s}\cap A_s=\emp$ and then putting $x$ into $A$. The reason that $\comp(A)$ was infinite was because for every $e$ we had that $|[0,2e]\cap A|\leq e$. This means that for every $a$ we have that $$[a,4a]\cap \comp(A)\neq\emp$$ because $[a,4a]$ is $3/4$ of the interval $[0,4a]$. So define $a_0=5$ and $a_{n+1}=4a_n+1$. Take $x_n$ so that $D_{x_n}=[a_n,4a_n]$ and note that $D_{x_n}\cap \comp(A)\neq \emp$ for each $n$ so the \rec set $R=\{x_n\st n<\om\}$ witnesses that $A$ is not hypersimple. \noindent (3) This is a consequence of the following proposition, although originally Post gave a construction similar to his construction of a simple set. \qed \begin{prop} (Dekker) Deficiency sets are hypersimple. \end{prop} \proof See Theorem \ref{dekker}. Suppose that $A=\{a_s\st s\in\om\}$ is a 1-1 \rec enumeration of $A$ and $A$ is not \rec. Define $$D=\{s\st \exists t>s\;\;\; a_tt$ we have $a_s>a_t$. Hence $u\in A$ iff $u=a_s$ for some $s\leq \max{D_x}$. \qed \hmwk{25}{Wed Nov 10} Define $A$ to be bdd-hypersimple iff $A$ is \re, $\comp(A)$ is infinite, and for every strong array $(D_x\st x\in R)$ such that there exists $N<\om$ such that $|D_x|\leq N$ for all $x\in R$, there exists $x\in R$ such that $D_x\sq A$. Prove that bdd-hypersimple is equivalent to simple. \begin{define} For any set $A\sq \om$ such that $\comp(A)$ is infinite define $\overline{a}_n$ to be the $(n+1)^{th}$ element of $\comp(A)$, i.e., $$\comp(A)=\{\overline{a}_0<\overline{a}_1 <\cdots<\overline{a}_n<\cdots\}.$$ \end{define} \begin{prop} \label{hsimple} For any \re set $A$ with $\comp(A)$ infinite the following are equivalent: \begin{enumerate} \item $A$ is hypersimple. \item For any \rec increasing sequence $n_kl\}$ is a strong array for any $l$. $(2)\implies (3)$. Given a \rec $f$ construct a \rec sequence $n_{k+1}>n_k$ with the property that $f(n_k+1)< n_{k+1}$ for each $k$. For any $k$ such that $[n_k,n_{k+1})\sq A$ note that $\comp(A)\cap [0,n_{k+1})\sq [0,n_k)$ and so $\overline{a}_{n_k+1}=(n_k+1)^{th}$ element of $\comp(A)$ must be greater than $n_{k+1}$. Hence $f(n_k+1)<\overline{a}_{n_k+1}$. $(3)\implies (1)$. Suppose $A$ is not hypersimple and hence there exists a strong array $(D_x\st x\in R)$ such that $D_x\cap\comp(A)\neq\emp$ for all $x\in A$. Let $\{x_n\st n\in\om)$ be a 1-1 \rec enumeration of $R$ and define $$f(n)=1+\max(\cup_{m\leq n}D_{x_m})$$ Then $|\comp(A)\cap[0,f(n))|> n$ and so $f(n)>\overline{a}_n$. \qed \begin{exercise} Suppose $A$ is hypersimple and $f:\om\to\om$ is \rec. Prove there exist an infinite \rec set $C$ such that $f(n)<\overline{a}_n$ for all $n\in C$. \end{exercise} \hmwk{26}{Fri 11-12} Prove that for every \re set $A\sq\om$ if $\comp(A)$ is infinite, then there exists a hypersimple set $B\supseteq A$. \bigskip Consider propositional logic with the set of atomic letters $$\{P_n\st n\in\om\}.$$ For any propositional sentence $\psi$ and subset $A\sq\om$ define $$A\models \psi$$ inductively by $$A\models P_n\rmiff n\in A$$ $$A\models \neg\psi \rmiff \mbox{ not } A\models \psi$$ $$A\models (\psi\vee\theta) \rmiff ( A\models \psi \rmor A\models \theta )$$ and so forth for the other logical symbols. By coding symbols as elements of $\om$ and thinking of sentences as strings of symbols or finite sequences of elements of $\om$, we identify the set of propositional sentences with a \rec subset of $\om,\;\;$ SENT. The details of this coding are left to the reader. The following notion is known as truth-table (tt) reducibility. \begin{define} $A\leq_{tt} B$ iff there exists a \rec sequence $$(\theta_n\in SENT\st n\in\om)$$ such that for all $n\in\om$ $$n\in A\rmiff B\models \theta_n$$ \end{define} Note: It is easy to see that $A\leq_{tt} C$ and $B\leq_{tt} C$ implies $(A\cap B)\leq_{tt} C$ and $\comp(A)\leq_{tt} C$. Hence the family of sets which are truth-table reducible to $C$ is closed under finite boolean combinations. It is easy to see that $\leq_m$-reducible is stronger than $\leq_{tt}$, and $\leq_{tt}$ is stronger than $\leq_{T}$. \begin{prop} (Nerode) The following are equivalent: \begin{enumerate} \item $A\leq_{tt}B$. \item There exist $e$ with the property that $$\forall X\;\forall x\; \{e\}^X(x)\conv$$ and $\{e\}^B=A$. \item There exists $e$ and $f\in\om^\om$ \rec such that $$\forall x \;\{e\}^B_{f(x)}(x)\conv$$ and $\{e\}^B=A$. \end{enumerate} \end{prop} \proof $(1)\implies (2)$. Given $(\theta_n\st n\in\om)$ witnessing that $A\leq_{tt} B$, it is easy to construct an oracle machine $e$ such that for any input $x$ and oracle $X$ that $\{e\}^X(x)\conv=1$, if $X\models\theta_x$ and $\{e\}^X(x)\conv=0$, if $X\models\neg\theta_x$. $(2)\implies (3)$. We show that the same $e$ works. Input $x$ and let $$T_x=\{\si\in 2^{<\om}\st \{e\}^\si_{|\si|}(x)\div\}.$$ The trees $T_x$ are uniformly \rec in $x$. By Konig's tree lemma, since $T_x$ has no infinite branch, it is finite. Therefore we can compute the least $n$ such that for all $\si\in 2^n$ we have that $\si\notin T_x$. Put $f(x)=n$. $(3)\implies (1)$. Input $x$. Compute a use bound $u_x$ so that for every possible computation $\{e\}^?_{f(x)}(x)$ the computation only asks about $is\;\; a_ta_{s_2}>a_{s_3}>\cdots$$ which is a contradiction. \qed \exer Prove that if $A$ is hypersimple and $(D_x:x\in C)$ is a strong array then there exists an infinite computable $E\su C$ such that $D_x\su A$ for all $x\in E$. \section{Maximal sets} \begin{define} \par $A\sq^*B$ iff $B\sm A$ is finite. \par $A=^* B$ iff $A\sq^* B$ and $B\sq^*A$ \par $\forall^{\infty}$ means `for all but finitely many' \par $\exists^\infty$ means `exists infinitely many' \end{define} \begin{define} $M\sq \om$ is maximal iff $M$ is \re, $\comp(M)$ is infinite, and for every $A$ \re if $M\sq A$ then $M=^*A$ or $A=^*\om$. \end{define} \begin{prop} Maximal sets are hyperhypersimple. \end{prop} Suppose $V$ is a weak array such that $V_e\cap \comp(A)\neq\emp$ for all $e$. Define $$B=A\cup\bigcup_{e<\om}V_{2e}$$ then $A\neq^*B$ and $B\neq^*\om$, so $A$ is not maximal. \qed \begin{theorem} (Friedberg) Maximal sets exist. \end{theorem} \proof We will construct the maximal set $M$ as follows. We use the notation $p_n$ for the $n^{th}$ element of the complement of $M$, i.e., $$\comp(M)=\{p_0m_2$ the markers $p_j$ for $j\leq m_2$ have stopped moving and their final $n$-states are their states at stage $s_0$. But by the construction some marker $\leq p_{m_1}$ must move. \qed This final claim proves the Theorem, since if $n=e+1$ we have that \noindent $\tau(e)=1$ implies $\forall^\infty m \;\;p_m\in W_e$ and \noindent $\tau(e)=0$ implies $\forall^\infty m \;\;p_m\notin W_e$ \qed \begin{example} There exists a hyperhypersimple set which is not maximal. \end{example} \proof First we note that it easy to get $M_1$ and $M_2$ maximal so that $M_1\neq^* M_2$. Take any maximal set $M$ and let $R\sq M$ to be an infinite \rec subset. Let $\pi:\om\to\om$ be a \rec bijection which takes $R$ to $\comp(R)$. Let $M_1=M$ and let $M_2=\pi(M_1)$. Now let $A=M_1\cap M_2$. Then $A$ is hyperhypersimple (see exercise) but not maximal since $A\sq M_1\sq\om$ and $A\neq^* M_1$ and $M_1\neq^*\om$. \qed Remark. Yates noted that we can add to the maximal set construction an extra `kick' to the $p_e$ marker to ensure that $\{e\}(e)\conv$ iff $\{e\}_{p_e}(e)$. Then the maximal set constructed will be Turing equivalent to $K$. \hmwk{28}{Wed 11-17} Suppose $A=\{a_n:n<\om\}$ is a 1-1 \rec enumeration of a hyperhypersimple set $A$. Let $B=\{a_{a_n}:n<\om\}$. Prove that $B$ is hyperhypersimple but not maximal. \hmwk{29}{Fri 11-19} \Anre set $A\sq \om$ is simple in $R$ where $R$ is an infinite \rec set iff $\comp(A)\cap R$ is infinite but contains no infinite \re subset. Is every \re set which is not \rec, simple in some infinite \rec set? Hint: Split a maximal set. \section{The lattice of \re sets} \begin{define} The lattice of \re sets is $\lattice =(\re sets, \sq)$. A subset $X\sq\lattice$ is definable iff there is a first order formula $\theta(v)$ in the language of $\sq$ such that $$X=\{A\in\lattice\st \lattice \models \theta(A)\}.$$ Similarly for $X\sq \lattice^2$ or $X\sq\lattice^3$. \end{define} \begin{example} The following are definable in $\lattice$. \begin{enumerate} \item $\{(A,B,C)\in\lattice^3\st A\cup B =C\}$ \item $\{(A,B,C)\in\lattice^3\st A\cap B =C\}$ \item $\{\emp\}$ \item $\{\om\}$ \item \rec sets \par $A$ is \rec iff $\lattice\models \exists B\;\; B\cap A=\emp \rmand B\cup A=\om$ \item \re but not \rec sets \item infinite \re sets \par $A$ is infinite \re iff $\lattice\models \exists B\;\; B\sq A $ and $B$ is not \rec \item finite sets \item cofinite sets \item $\su^*$, $=^*$ \item simple sets \item maximal sets \end{enumerate} \end{example} \begin{define} $\pi$ is an automorphism of $\lattice$ iff $\pi:\lattice\to\lattice$ is a bijection such that for every $A,B\in\lattice$ $$ A\sq B \rmiff \pi(A)\sq \pi(B).$$ \end{define} Note that for any first-order formula $\theta(v_1,\ldots,v_n)$ in the language of $\lattice$, i.e., $\sq$, that for any $\pi\in aut(\lattice)$ and $A_1,\ldots,A_n\in\lattice$ we have that $$\lattice\models \theta(A_1,\ldots,A_n)\rmiff \lattice\models \theta(\pi(A_1),\ldots, \pi(A_n))$$ Hence definable sets are closed under automorphisms. \begin{example} If $A\in\lattice$, then $\{A\}$ is definable in $\lattice$ iff $A=\emp$ or $A=\om$. \end{example} \proof If $A$ is neither $\emp$ or $\om$, then we can choose $n,m<\om$ such that $n\in A$ and $m\notin A$. Let $\pi:\om\to\om$ be the identity except $\pi(n)=m$ and $\pi(m)=n$. Define $\pi:P(\om)\to P(\om)$ by $\pi(A)=\{\pi(n):n\in A\}$. Then since $\pi$ is \rec it is clear that $\pi\in aut(\lattice)$. But since $$\pi(A)=(A\sm\{n\})\cup\{m\}$$ we see that $\{A\}$ is not closed under automorphisms and hence cannot be definable. \qed \begin{prop} \begin{enumerate} \item For every $\pi\in aut(\lattice)$ there exists a bijection $\hat{\pi}$ of $\om$ such that $\pi(A)=\{\hat{\pi}(n):n\in A\}$. \item Not every bijection $\pi:\om\to\om$ induces an automorphism of $\lattice$. \item There are continuum many bijections $\pi:\om\to\om$ which induce an automorphism of $\lattice$. \end{enumerate} \end{prop} \proof (1) It is easy to see that the set of singletons $$\{\{n\}:n\in\om\}\sq \lattice$$ is definable in $\lattice$. Hence any automorphism $\pi:\lattice\to\lattice$ must permute the singletons. Define $\hat{\pi}(n)$ so that $\pi(\{n\})=\{\hat{\pi}(n)\}$. But now for every $n\in\om$ $$n\in A \rmiff \{n\}\sq A \rmiff \pi(\{n\})\sq \pi(A) \rmiff \hat{\pi}(n)\in \pi(A)$$ Hence $\pi(A)=\{\hat{\pi}(n):n\in A\}$. (2) Take any bijection which maps the even integers to some non \rec infinite coinfinite set. (3) Let $M$ be a maximal set. Let $\pi:\om\to\om$ be any bijection such that $\pi\res M=id$. There are continuum many such bijections, one for each permutation of $\comp(M)$. But for any $A\in \lattice$ we have that $A\cap\comp(M)$ is finite or $A\cap\comp(M)=^*\comp(M)$. But this gives us that $\pi(A)=^*A$. Similarly $\pi^{-1}(A)=^*A$. \qed The following theorem shows that the family of hyperhypersimple sets is definable in $\lattice$. \begin{theorem} (Lachlan) $A$ is hyperhypersimple iff $A$ is \re, $\comp(A)$ is infinite, and $$\lattice\models \forall B\supseteq A\;\;\exists C\supseteq A \;\; B\cap C = A \rmand B\cup C=\om$$ \end{theorem} \proof Suppose $A$ is not hyperhypersimple and $V$ is a weak array such that $V_e\cap \comp(A)\neq \emp$ for all $e$. Define $$B=A\cup\bigcup_{e\in\om}(V_e\cap W_e)$$ Suppose for contradiction that $C$ satisfies $B\cap C = A$ and $B\cup C=\om$. Then for some $e$ we have that $C=W_e$. Let $x\in V_e\cap\comp(A)$. If $x\in W_e$ then $x\in C\cap B$ but this contradicts $B\cap C = A$. If $x\notin W_e$ then $x\notin C$ and $x\notin B$ but this contradicts $B\cup C=\om$. Conversely suppose there exists $B$ as above for which there is no $C$. We must show there is a weak array $V$ such that $V_e\cap\comp(A)\neq \emp$ for all $e$. So let $B=\{b_s:s\in\om\}$ be a 1-1 \rec enumeration of $B$ and put $B_s=\{b_t: ts_0$ we have that $g(\hat{e},s)=g(\hat{e})$ and $$b_s> \max\{g(\hat{e}):\hat{e} g(\hat{e})$ for all $\hat{e}2x_s$. Since each $x_s$ is distinct the Claim follows. \qed As we have seen before this implies that $B$ is not hypersimple. (Proposition \ref{posthsimple}). \bigskip\noindent {\bf Claim (2)} $\lim_{s\to\infty}\pi_s(u)=\pi(u)<\infty$ for every $u$. \proof Fix $s_0$ so that $A\cap [0,u]=A_{s_0}\cap [0,u]$. Now the only way that $\pi_{s+1}(u)\neq \pi_s(u)$ for some $s>s_0$ is if $u=x_s$ or $u=y_s$. But in either case since $x_ss_0\;\;\; e_s>e$ \proof This is proved by induction on $e$. (a) We may suppose by induction that there exists $s_0$ such that $e_s\geq e$ for all $s>s_0$. Suppose $R_e$ is not met. Then $W_e^*$ is infinite and for all $n\in W_e^*$ we have that $D_n\cap \comp(A)\neq\emp$. For each $n\in W_e^*$ define $$u_n=\min(D_n\cap \comp(A))$$ Since the $D_n$ are pairwise disjoint all of the $u_n$ are distinct. Note there exist $\si,\tau\in 2^e$ such that $\exists^\infty n\in W_e^*\;\;\; \si = $ final $e$-state of $u_n$ and $\tau =$ final $e$-state of $\pi(u_n)$. Choose $u_n$ and $u_m$ such that \begin{enumerate} \item $n,m\in W_e^*$ \item $es_0$ \item $\si$ is the $e$-state of $u_n$ and $u_m$ at stage $s_0$, \item $\tau$ is the $e$-state of $\pi(u_n)$ and $\pi(u_m)$ at stage $s_0$ and \item $A_{s_0}\cap [0,u_m]=A\cap [0,u_m]$ \end{enumerate} Recall that we chose $u_n,u_m\in\comp(A)$. It is easy to check that $e$ requires attention at stage $s_0$ and $u_n$ and $u_m$ witness this fact. But this means that $u_n$ or some smaller $u$ enters $A$. But this contradicts the condition that $A$ does not change below $u_m$. (b) Suppose that $e_s\geq e$ for all $s>s_0$ and $R_e$ is met. If $W_e^*$ is infinite, then for some $n\in W_e^*$ we have that $D_n\sq A$. But this will be seen at some stage and so $e$ will not require attention after that. If $W_e^*$ is finite, then suppose that $$\cup\{D_n\st n\in W_e^*\}\sq [0,N].$$ After we reach a stage $s>s_0$ where $A_s\cap [0,N]=A\cap [0,N]$, then $e$ will never again require attention because then $A$ would change beneath $N$. \qed \bigskip\noindent {\bf Claim (4)} $\pi$ is onto. \proof Given $z$ choose $s_0$ so that $e_s>z$ for all $s\geq s_0$. If $\pi_{s_0}(u)=z$, then $u$ will never be either $x_s$ or $y_s$ for any $s\geq s_0$. This is because we required (2c) that $\pi_s(x_s),\pi_s(y_s)>e_s$. Hence $\pi(u)=z$. \qed \bigskip\noindent {\bf Claim (5)} \par (a) $\forall C\in\lattice\;\;\; \pi(C)\in\lattice$ \par (b) $\forall C\in\lattice\;\;\; \pi^{-1}(C)\in\lattice$ \proof (a) Fix $s_0$ so that for all $s>s_0$ we have that $e_s>e$. Then we show that $$\pi(W_e)=\bigcup_{s>s_0}\pi_s(W_{e,s})$$ To see this first suppose $y\in \pi(W_e)$. Then there exists $x\in W_e$ with $\pi(x)=y$ but for all sufficiently large $s$ we have that $x\in W_{e,s}$ and $\pi_s(x)=\pi(x)$ and thus $y\in\pi_s(W_{e,s})$. To see the other inclusion, suppose that $y\in\pi_s(W_{e,s})$ for some $s>s_0$. We claim that for every $t>s$ that $y\in \pi_t(W_{e,t})$. This is proved by induction on $t$. Suppose that $\pi_t(u)=y$ for some $u\in W_{e,t}$. Then $\pi_{t+1}(u)=\pi_t(u)$ unless $u=x_t$ or $u=y_t$ and then $\pi_{t+1}(x_t)=\pi_t(y_t)$ and $\pi_{t+1}(y_t)=\pi_t(x_t)$. But since $x_t$ and $y_t$ have the same $e_t$-state and $e_t>e$, if one is in $W_{e,t}$ so is the other. In either case we have that there exists $v\in W_{e,t+1}$ with $\pi_{t+1}(v)=y$. Now to see that $y\in\pi(W_e)$ suppose that $\pi(u)=y$ and choose sufficiently large $t>s_0$ such that $\pi_t(u)=\pi(u)=y$. Since $\pi_t$ is a bijection and $y\in \pi_t(W_{e,t})$, it must be that $u\in W_{e,t}$ and hence $u\in W_e$. (b) This is similar, except we use that $\pi_t(x_t)$ and $\pi_t(y_t)$ have the same $e_t$-state. \qed \hmwk{30}{Wed 11-24} Prove that there exists a bijection $\pi:\om\to\om$ such that $\pi(A)\in\lattice$ for all $A\in\lattice$ but $\pi\notin aut(\lattice)$. (Hint: use a maximal set.) \exer For each $n\geq 2$ prove there is a sequence of maximal sets $A_1,\ldots,A_n$ such that $A_i\neq^*A_j$ for distinct $i$ and $j$. Prove that for any such sequence that ${\mathcal E}^*(A_1\cap A_2\cap\cdots \cap A_n)$ is isomorphic to $(\pow(\{1,\ldots,n\}),\su)$. The structure ${\mathcal E}^*(A)$ is the set of \re supersets of $A$ modulo the finite sets and ordered by $\su^*$. \section{Arithmetic hierarchy} \begin{define} For $A$ and $B$ predicates over subsets of $\om$ or finite products of $\om$ we define: $\Pi_0^0=\Sigma_0^0=$ the \rec predicates. $A$ is $\Sigma^0_{n+1}$ iff there exists $B$ which is $\Pi^0_{n}$ and $A(x)\equiv \exists y\;\; B(x,y)$. $A$ is $\Pi^0_{n+1}$ iff there exists $B$ which is $\Sigma^0_{n}$ and $A(x)\equiv \forall y\;\; B(x,y)$. $A$ is $\Delta_n^0$ iff $A$ is $\Sigma^0_{n}$ and $A$ is $\Pi^0_{n}$. \end{define} Note that by DeMorgan's Laws $$\Pi_n^0=\{\neg A: A\in \Sigma_n^0\} \rmand \Sigma_n^0= \{\neg A: A\in \Pi_n^0\}$$ and hence $$\Delta_n^0=\{\neg A: A\in \Delta_n^0\}.$$ \begin{prop} Suppose $\Gamma$ is $\Sigma_n^0$, $\Pi_n^0$, or $\Delta^0_n$. Then $\Gamma$ is closed under $\leq_m$, i.e., $A\leq_m B\in\Gamma$ implies $A\in\Gamma$. This implies that if the predicate $B(x,y)$ is in $\Gamma$ and $f$ is a \rec function, then $A(x,y)\equiv B(x,f(x))$ is in $\Gamma$. \end{prop} \begin{prop} If $B(x,y)$ in $\Sigma_n^0$, then $A(x)\equiv \exists y\;\; B(x,y)$ is in $\Sigma_n^0$. If $B(x,y)$ in $\Pi_n^0$, then $A(x)\equiv \forall y\;\; B(x,y)$ is in $\Pi_n^0$. \end{prop} \begin{prop} Suppose $\Gamma$ is $\Sigma_n^0$, $\Pi_n^0$, or $\Delta^0_n$. If $A,B\in\Gamma$, then $A\conj B$ and $A\disj B$ are both in $\Gamma$. Also, $\Gamma$ predicates are closed under bounded quantification, e.g., $\exists u0$ there is a universal $\Sigma_n^0$ set. \end{prop} \begin{prop} For each $n>0$ we have $Red(\Sigma_n^0)$, $Sep(\Pi^0_n)$, $\neg Sep(\Sigma_n^0)$, and $\neg Red(\Pi^0_n)$. \end{prop} \proof See definitions \ref{reduction}. We first show $Red(\Sigma_n^0)$. Let $$A(x)\equiv \exists y \; R(x,y)\;\;\;\rmand \;\;\; B(x)\equiv \exists y \; S(x,y)$$ where $R$ and $S$ are $\Delta_n^0$. Reduce $A$ and $B$ by $$A_0(x)\equiv \exists y \; ( R(x,y)\conj \forall zsep}, it follows that $Sep(\Pi^0_n)$ holds. To see $\neg Sep(\Sigma_n^0)$, first construct a doubly universal pair $A$ and $B$. These are $\Sigma_n^0$ sets such that for every pair $C$ and $D$ of $\Sigma_n^0$ sets there exists a $u$ with $C=A_u$ and $D=B_u$. To get $A$ and $B$ let $U$ be a universal $\Sigma_n^0$ set. Then define $$A=\{(\pair(x,y),z)\st \pair(x,z)\in U\}$$ and $$B=\{(\pair(x,y),z)\st \pair(y,z)\in U\}$$ then $u=\pair(x,y)$ codes the pair $U_x$ and $U_y$. Now applying reduction to $A$ and $B$ we get $A^0\sq A$ and $B^0\sq B$. Note that this simultaneously reduces all cross sections $A_u$ and $B_u$. Assuming for contradiction that separation holds, let $C$ be $\Delta_n^0$ such that $A^0\sq C$ and $B^0\sq\comp(C)$. We get a contradiction since, then $C$ would be a universal $\Delta_n^0$ set. This is because if $P$ is $\Delta_n^0$ then there exists $u$ with $A_u=P$ and $B_u=\comp(P)$. But the reduction followed by separation can't effect the $u$ cross section, so $C_u=P$. \qed \hmwk{31}{Mon 11-29} Prove there does not exist a universal $\Delta_n^0$ set. \section{Post: $\Delta_2^0$ same as \rec in $\jump(0)$} \begin{lemma}\label{infty} $A\sq\om$ is $\Pi_2^0$ iff there exists $P$ \rec such that $$A(x)\rmiff \exists^\infty s\;\;P(s,x)$$ \end{lemma} \proof ($\leftarrow$) $\exists^\infty s\;\;P(s,x)$ iff $\forall t\; \exists s>t\;P(s,x)$ \noindent ($\rightarrow$) Suppose $$A(x)\rmiff \forall n\;\exists m\; R(n,m,x)$$ where $R$ is $\Delta_1^0$. Define $P\sq \om^{<\om}\times \om$ by $$P(\si,x)\rmiff \forall i<|\si|\;\; [ R(i,\si(i),x)\rmand \forall j2$ are analogous. \qed \hmwk{32}{Wed 12-1} Prove there does not exist $A$ which is $m$-complete for $\Delta^0_2$. \exer (Enderton, Putnam) Prove that if $0^{(n)}\leq_T A$ for every $n$, then $0^{(\om)}\leq_T A^{\pr\pr}$. \par\noindent Hint: Show that $$P(e_1,e_2)\equiv \exists B,C\;\;\; B=\{e_1\}^A\wedge C=\{e_2\}^A\wedge C=\jump(B)$$ is $\Pi^0_2(A)$. \section{EMP, TOT, FIN, and REC} \begin{prop} $EMP=^{def}\{e\st W_e=\emp\}$ is $\Pi^0_1$-m-complete. \end{prop} \proof $$e\in EMP\rmiff \forall x,s\;\; x\notin W_{e,s}$$ so $EMP$ is $\Pi^0_1$. Let $A$ be $\Pi_1^0$, then there is $R$ \rec so that $$A(x)\rmiff \forall y\;\; R(x,y).$$ Using S-n-m Theorem get $f$ \rec so that for every $x$ $$W_{f(x)}=\{y\st \neg R(x,y)\}$$ Then $A(x)$ iff $f(x)\in EMP$. \qed \begin{prop}\label{tot} \par $TOT=^{def}\{e\st W_e=\om\}$ is m-complete for $\Pi^0_2$. \par $FIN=^{def}\{e\st W_e$ is finite$\}$ is m-complete for $\Sigma^0_2$. \end{prop} \proof $$e\in TOT \rmiff \forall x \;\exists s\; x\in W_{e,s}$$ $$e\in FIN \rmiff \exists x \;\forall y,s\; (y\in W_{e,s}\implies yt \;\; P(s,x)\}$$ Hence $A(x)\implies W_{f(x)}=\om$ while $\neg A(x)\implies W_{f(x)}$ is finite. \qed \begin{prop} $COF=^{def}\{e\st \comp(W_e)$ is finite $\}$ is $\Sigma_3^0$-m-complete. \end{prop} \proof $$e\in COF\rmiff \exists n\;\forall m>n\;\exists s\;\; m\in W_{e,s}$$ Now suppose that $A$ is $\Sigma_3^0$. Then there exists $P$ which is $\Delta_1^0$ such that $$A(x)\rmiff \exists n\;\;\exists^\infty m\;\; P(n,m,x)$$ Input $x$ and describe the \re set $B_x$ by using a moving marker construction similar to the construction of a maximal set but simpler. At any stage $s$ we have that $$\comp(B_{x,s})=\{p_{0,s}1$ then since $C$ is $\Sigma_k^0$ we have by induction a $\Pi^0_{k-1}$ predicate $D$ so that $$C(x,y)\rmiff \exists u\; D(x,y,u)\rmiff\exists ! u\; D(x,y,u)$$ Hence $$A(x)\rmiff \exists y\;\exists u\;\;(P(x,y)\conj D(x,y,u))\rmiff \exists! y\;\exists! u\;\;(P(x,y)\conj D(x,y,u))$$ so taking $B(x,\pair(y,u)) \equiv P(x,y)\conj D(x,y,u)$ does the trick. \qed \begin{prop} (a) $A$ is $\Pi^0_3$ iff there exists $B$ which is $\Delta_1^0$ such that $$A(u)\equiv \exists^\infty s\;\forall n \; B(s,n,u)$$ \par (b) $A$ is $\Pi^0_4$ iff there exists $B$ which is $\Delta_1^0$ such that $$A(x)\equiv \exists^\infty s\;\exists^\infty t \; B(s,t,x)$$ \end{prop} \proof (a) Suppose $$A(u)\equiv \forall x \;\exists y \;\forall z\; R(x,y,z,u)$$ where $R$ is $\Delta_1^0$. Define $$Q(x,u)\equiv \exists y \;\forall z\; R(x,y,z,u)$$ Then by Lemma \ref{unique} there is a $C$ which is $\Pi_1^0$ and $$Q(x,u)\equiv \exists y\;\; C(x,y,u) \equiv \exists ! y\;\; C(x,y,u)$$ Hence $$A(u)\equiv \forall x\exists ! y \;\;C(x,y,u)$$ $$A(u)\equiv \exists^{\infty}\si\in \om^{<\om}\;\; \forall i<|\si|\;\; C(i,\si(i),u)$$ Note that $\forall i<|\si|\;\; C(i,\si(i),u)$ is $\Pi_1^0$ and so there is $B$ \rec so that $$\forall n \;B(\si,n,u) \equiv \forall i<|\si|\;\; C(i,\si(i),u)$$ \medskip \noindent (b) Suppose $$A(u)\equiv \forall x \;\exists y \; R(x,y,u)$$ where $R$ is $\Pi^0_2$. By Lemma \ref{unique} applied to $\exists y \;\; R(x,y,u)$ we may assume that $$A(u)\equiv \forall x\;\exists ! y\; R(x,y,u)$$ Hence $$A(u)\equiv \exists^{\infty}\si\;\forall i<|\si|\;\; R(i,\si(i),u)$$ but the predicate $$ Q(\si,u)\equiv\forall i<|\si| \;\;R(i,\si(i),u)$$ is $\Pi_2^0$ so there exists a \rec $B$ so that $$Q(\si,u)\equiv \exists^{<\infty}\tau\;\; B(\si,\tau,u)$$ Hence $$A(u)\equiv \exists^\infty \si\;\exists^\infty\tau\;\; B(\si,\tau,u)$$ \qed \exer For the correct class $\Gamma$, show that INF, EQ, EQ* are m-complete $\Gamma$ sets where $$\mbox{INF}=\{e\st W_e \mbox{ is infinite}\}$$ $$\mbox{EQ}=\{\la e_1,e_2\ra\st W_{e_1}=W_{e_2}\}$$ and $$\mbox{EQ}^*=\{\la e_1,e_2\ra\st W_{e_1}=^*W_{e_2}\}.$$ \hmwk{34}{Mon 12-6} \par Let $PTIME=\{e\st \psi_e $ runs in polynomial time $\}$, i.e., there exists a polynomial $p(x)$ such that $\psi_e(x)$ halts in less than $p(x)$ steps for every $x$. Prove that $PTIME$ is $\Sigma^0_2$-m-complete. \hmwk{35}{Wed 12-8} For each $e$ let $Q_e=\{{n\over m+1}\st \pair(n,m)\in W_e\}\sq\rationals.$ Define \par $\Omega=\{ e\st Q_e$ is order isomorphic to $\om\}$. \par\noindent Prove that $\Omega$ is $\Pi^0_3$-m-complete. \exer Show that if $Q=\{e\st W_e\in\vv\}$ is not $\Sigma^0_3$ then $\vv$ cannot be \anre class. See Definition \ref{defreclass}. \exer Prove that the family of coinfinite \re sets is not \anre class. \exer Prove that SIMP=$\{e\st W_e$ is simple $\}$ is m-complete $\Pi^0_3$. Hint: Like the proof for COF but also let $W_e$ kick the $e^{th}$ marker at most once to make $A$ meet $W_e$ if $W_e$ infinite. % 2001 #21 \exer Prove that the family of simple sets is not \anre class. % 2001 #20 \exer Prove of disprove: \par (a) there exists a total $f\leq_T 0^{((2)}$ such that for all $e$, if $W_e$ is \rec, then $W_{f(e)}=\overline{W_e}$. \par (b) there exists a total $f\leq_T 0^{(3)}$ such that for all $e$, if $W_e$ is \rec, then $W_{f(e)}=\overline{W_e}$. \section{Domination and high degrees} \begin{theorem}\label{martindom} (Martin) For any set $A\su\om$ the following are equivalent: \begin{enumerate} \item $0^{\pr\pr}\leq_T \jump(A)$ and \item there exists $g\leq_T A$ such that $\forall^\infty n \;\;f(n)\leq g(n)$ for every \rec $f$. \end{enumerate} \end{theorem} \proof $(1)\to (2)$ Since TOT is Turing equivalent to $0^{\pr\pr}$ (\ref{tot}), by the limit lemma (\ref{limitlemma}) there is a total $h\leq_T A$ so that for every $e\in\om$ $${\mbox{T0T}}(e)=\lim_{s\to\infty} h(e,s).$$ Define $h_e(x)=h(e,x)$ and define $g(x)$ to be the maximum of the set: $$\{ \{e\}(x)\st e_T 0$ and $J_{e_0}(A)\equiv_T \jump(0)$.} \end{lemma} \proof Let $\jump(0)=\{e_s:s<\om\}$ be a one-to-one \rec enumeration of $\jump(0)=K$. \begin{center} Requirements and strategies \end{center} \noindent Our requirements can be described as follows: \medskip $P_{2e}\;\;\;\;\;\;\; \comp(A)\neq W_e$ \medskip \noindent Our strategy will be to put its follower $v_{2e}$ into $A$ if it ever turns up in $W_e$. \medskip $P_{2e+1}\;\;\;\;$ Code $e$ into $A$ if e every turns up in $\jump(0)$. \medskip \noindent Our strategy will put its follower $v_{2e+1}$ into $A_{s+1}$ if $e=e_s$. We will show that $v_{2e+1}$ can be computed from $J_{e_0}(A)$ and so $\jump(0)\leq_T J_{e_0}(A)$. \medskip $N_n\;\;\;\;\;\;\;\; (\exists^\infty s\;\; \{e_0\}_s^{A_s}(n)\downarrow) \to \{e_0\}^{A}(n)\downarrow$ \medskip \noindent This is to insure that $W_{e_0}^A\leq_T \jump(0)$. We use the usual low simple set strategy of restraining the computation. \begin{center} Construction \end{center} For each negative requirement $N_n$ define the restraint function $r(n,s)$ to be the use of the computation $\{e_0\}_s^{A_s}(n)$ (recall that this is zero if the computation does not converge). For each positive requirement $P_n$ its set of potential followers is $$F_n=\{\la n,m\ra:m<\om\}$$ and its follower $v_n^s$ at stage $s$ is: $$v_n^s=\min\{v\in F_n\st v>\max(r(m,s):m\leq n)\}.$$ We say that $P_n$ requires attention at stage $s$ iff \begin{enumerate} \item ($n=2e+1$ and $e=e_s$) or \item $n=2e_T 0$. It remains only to see the following: \medskip {\bf Claim.} $\jump(0)\leq_T A\join W_{e_0}^A$. \medskip Define $$f(n)=\left\{ \begin{array}{ll} 1 & \mbox{ if $P_n$ ever acts}\\ 0 & \mbox{ otherwise.} \end{array}\right.$$ Obviously $\jump(0)\leq_T f$ since $e\in\jump(0)$ iff $f(2e+1)=1$. So it is enough to see that $$f\leq_T A\join W_{e_0}^A.$$ Assume we have computed $f\res n$ using an oracle for $A\join W_{e_0}^A$ and we show how to compute $f(n)$. Find a stage $s_0$ so that \begin{enumerate} \item $\forall m_T 0$ and $J_e(A)\equiv \jump(0)$. \medskip \noindent The uniformized version says: There exists a \rec $f:\om\to\om$ such that for all $e$ $$W_{f(e)}>_T 0 \rmand J_e(W_{f(e)})\equiv \jump(0).$$ \medskip \noindent Or using the psuedojump we could equivalently prove: There exists a \rec $f:\om\to\om$ such that for all $e$ $$J_{f(e)}(0)>_T 0 \rmand J_e(J_{f(e)}(0))\equiv \jump(0).$$ \medskip \noindent The same proof will work for every oracle $B$. So finally we get the relativized and uniformitized version: \begin{lemma}\label{psuedo} There exists a \rec $f:\om\to\om$ such that for all $e$ and for all $B\su\om$: $$J_{f(e)}(B)>_T B \rmand J_e(J_{f(e)}(B))\equiv \jump(B).$$ \end{lemma} \bigskip Fix $f$ from Lemma \ref{psuedo} and consider any $n>0$ and $e$. \begin{prop}\label{prophigh} Suppose $$\forall B \;\; (J_e(B))^{(n)}\equiv_T B^{(n)}\rmand (J_e(B))^{(n-1)}\not\equiv_T B^{(n-1)}$$ Then $$\forall B \;\; (J_{f(e)}(B))^{(n)}\equiv_T B^{(n+1)}\rmand (J_{f(e)}(B))^{(n-1)}\not\equiv_T B^{(n)}.$$ \end{prop} \proof Note that $$(J_{f(e)}(B))^{(n)}\equiv_T (J_e(J_{f(e)}(B)))^{(n)}$$ by substituting $J_{f(e)}(B)$ for $B$ in the hypothesis. We also have that $$(J_e(J_{f(e)}(B)))^{(n)}\equiv_T B^{(n+1)}$$ because $J_e(J_{f(e)}(B))\equiv_T \jump(B)$ and hence $$(J_{f(e)}(B))^{(n)}\equiv_T B^{(n+1)}.$$ Similarly by substituting $J_{f(e)}(B)$ for $B$ in the hypothesis $$(J_{f(e)}(B))^{(n-1)}\not\equiv_T (J_e(J_{f(e)}(B)))^{(n-1)}\equiv_T B^{(n)}$$ and so $$(J_{f(e)}(B))^{(n-1)}\not\equiv_T B^{(n)}.$$ \qed We are using the terminology $B^{(0)}=B$. \bigskip By a similar proof we have \begin{prop}\label{proplow} Suppose $$\forall B \;\; (J_e(B))^{(n)}\equiv_T B^{(n+1)}\rmand (J_e(B))^{(n-1)}\not\equiv_T B^{(n)}.$$ Then $$\forall B \;\; (J_{f(e)}(B))^{(n+1)}\equiv_T B^{(n+1)}\rmand (J_{f(e)}(B))^{(n)}\not\equiv_T B^{(n)}.$$ \end{prop} \bigskip Define the high low hierarchy of \re degrees as follows \begin{enumerate} \item $H_0=\{\jump(o)\}$ \item $L_0=\{o\}$ \item $L_n=\{a\in\redegrees\st a^{(n)}=o^{(n)}\}$ \item $H_n=\{a\in\redegrees\st a^{(n)}=o^{(n+1)}\}$ \end{enumerate} Choose $e_0$ so that for every $B$, $\jump(B)\equiv_T J_{e_0}(B)$. Let $e_{n+1}=f(e_n)$. And let ${\bf a}_n$ be the Turing degree of $J_{e_n}(0)$. \begin{prop} For every $n$ $${\bf a}_{2n}\in H_n\sm H_{n-1}\rmand {\bf a}_{2n+1}\in L_{n+1}\sm L_n.$$ \end{prop} \proof Note that $$\forall B\;\; (J_{f(e_0)}(B))^{(1)}\equiv J_{e_0}(J_{f(e_0)}(B))\equiv B^{(1)}$$ but $$(J_{f(e_0)}(B))^{(0)}\not\equiv B^{(0)}.$$ So applying the Propositions \ref{prophigh} and \ref{proplow} alternatingly, the result follows. \qed Note that in particular, ${\bf a}_2$ is a nontrivial high degree and this proves Theorem \ref{high}. \begin{theorem} (Martin, Lachlan, Sacks) There exist a \re degree ${\bf a}$ such that $${\bf a}\notin \bigcup_{n<\om}(L_n\cup H_n).$$ \end{theorem} \proof In Lemma \ref{psuedo} take $e_0$ to be fixed point for $f$ and hence $J_{e_0}(B)=J_{f(e_0)}(B)$ for every set $B$. Define $H(B)=J_{e_0}(B)$ where $H$ is short for the Hop of $B$. Then for every $A$ we have $$B<_TH(B)<_T H^2(B)\equiv_T \jump(B)$$ i.e., two hops make a jump. Hence if $A=H(0)$, then for every $n$ we have that $A^{(n)}=H^{2n+1}(0)$ and so $$0^{(n)}\equiv_T H^{2n}(0)0$: $$ \bigwedge_{k < n} \rho_{k} \mbox{ does not imply } \bigwedge_{k < f(n)} \rho_{k}. $$ \end{lemma} \begin{example}(Kreisel) There is a \recly axiomatizable theory $T$ which cannot be axiomatized by a \recenum independent set of sentences. \end{example} \proof Robinson's theory $Q$ is a finite subset of Peano Arithmetic PA which is in turn a subtheory of true arithmetic $(\om,+,\cdot,S,0)$, i.e., $$Q\su PA \su Th(\om,+,\cdot,S,0).$$ Every \re set is weakly represented in $Q$. Let $H\su\om$ be any hypersimple set and suppose $\theta(v)$ is a formula such that $$\forall n\;\;\; (n\in H\rmiff Q\proves \theta(\underline{n})).$$ Let $T$ be the theory in the language of arithmetic plus one new unary predicate symbol $R$ with the following set of axioms: \begin{enumerate} \item $\bigwedge Q$, \item $\forall v \;\; (\theta(v)\to R(v))$, and \item infinitely many axioms: $$R(\underline{n})$$ for each $n<\om$. \end{enumerate} The symbol $\underline{n}$ is shorthand for $S(S(\cdots S(0))\cdots)$ with $n$ many $S$'s. Let $f$ be the \rec function from Lemma \ref{klemma}. Since $H$ is hypersimple there exists $n$ such that $[n,f(n))\su H$. But then for all k in $[n,f(n))$ $$Q\proves \theta(\underline{n}).$$ Hence $$[\bigwedge Q \;\;\wedge\;\;\forall v \;\; \theta(v)\to R(v)] \;\;\;\proves\;\;\; \bigwedge_{n\leq ke$. If there is no such $e$ we do not change any followers. In either case, we put $s$ into the ordering $\less \res ( s\times s)$ in the first gap above all the $l_e$ for $e\in F_{s+1}$ (and therefore, below all the $r_e$ for $e\in F_{s+1}$.) \bigskip \noindent {\bf Claim.} For each $e$ if $W_e$ is infinite, then $R_e$ obtains permanent followers $l_e$ and $r_e$ and is met. \proof Suppose the Claim is true for all $e^\prs_0$ are put between $l_{e_0}$ and $r_{e_0}$ and $W_e$ is infinite, it must be that some followers are appointed to $R_e$ if it doesn't already have them. These followers are permanent. \qed Since infinitely many $W_e$ are infinite and hence acquire permanent followers, it must be that $L$ and $R$ are infinite and therefore the order type we construct is $\om+\om^*$. \qed \begin{cor}\label{jock} (Jockusch) There exists a \rec function $f:[\om]^2\to 2$ such that there is no infinite \rec $H\in[\om]^\om$ such that $f\res[H]^2$ is constant. \end{cor} \proof Define $$f({x,y})=\left\{ \begin{array}{ll} 1 & \mbox{ if } x0$ $$H(c,\si)=\cap_{n, \si n\in T} H(c,\si n)$$ \medskip $A\sq \xx$ is hyperarithmetic (HYP) iff there exists a hypcode $c$ and $$A=H(c)=^{def}H(c,\la\ra).$$ \end{define} \begin{prop} HYP $\sq \Delta_1^1$. \end{prop} \proof $x\in H(c)$ iff there exists $f:T\to \{0,1\}$ such that \begin{enumerate} \item $\forall \si\in T_0$ $$f(\si)=1 \rmiff x\in U_{c(\si)}$$ \item $\forall \si\in T\sm T_0$ if $c(\si)=0$ then $$f(\si)=1\rmiff \exists n\;\; (\si n\in T\;\; \conj\;\; f(\si n) =1)$$ \item $\forall \si\in T\sm T_0$ if $c(\si)>0$ then $$f(\si)=1\rmiff \forall n\;\; (\si n\in T\implies f(\si n) =1)$$ \item $f(\la\ra)=1$ \end{enumerate} It is easy to check that $1-4$ are all arithmetic predicates and so $H(c)$ is $\Sigma^1_1$. To see that the complement of $H(c)$ is also $\Sigma^1_1$ just note that \noindent $x\notin H(c)$ iff there exists $f:T\to \{0,1\}$ such that 1,2,3, and $4^\pr$. $f(\la\ra)=0$. \qed \begin{theorem} (Kleene-Souslin) Suppose $A$ and $B$ are disjoint $\Sigma_1^1$ sets. Then they can be separated by a hyperarithmetic set $C$. Hence HYP $= \Delta_1^1$. \end{theorem} \proof To simplify the notation we assume that $A,B\sq \om^\om$ although essentially the same proof will work for $A,B\sq \om$ or any $\xx$. Since $A,B$ are $\Sigma^1_1$ there are \rec trees $$T^A,T^B\sq \cup_{n<\om}\om^n\times \om^n$$ such that $$x\in A \rmiff \exists y\;\; \forall n \;\; (x\res n,y\res n)\in T^A$$ $$x\in B \rmiff \exists z\;\; \forall n \;\; (x\res n,z\res n)\in T^B$$ The fact that $A$ and $B$ are disjoint implies that it is impossible to find $(x,y,z)$ such that $(x\res n,y\res n)\in T^A$ and $(x\res n,z\res n)\in T^B$ for all $n$. This tells us how to find our \rec well-founded tree $T$. Given $\rho\in \om^{<\om}$ we determine a triple $trip(\rho)= (\si,\tau_1,\tau_2)$ by the rule that $\si(i)=\rho(3i)$, $\tau_1(i)=\rho(3i+1)$, and $\tau_2(i)=\rho(3i+2)$. We take the natural length functions, namely \begin{itemize} \item $|\si|=|\tau_1|=|\tau_2|=n$ if $|\rho|=3n$, \item $|\si|=n+1,\;\; |\tau_1|=|\tau_2|=n$ if $|\rho|=3n+1$, and \item $|\si|=|\tau_1|=n+1,\;\;|\tau_2|=n$ if $|\rho|=3n+2$. \end{itemize} Now we define the \rec well-founded tree $T\sq\om^{<\om}$ and hypcode $c:T\to\om$ as follows: \begin{enumerate} \item for $\rho\in \om^{<\om}$ with length $|\rho|=3n+2$ and $trip(\rho)=(\si,\tau_1,\tau_2)$ if \begin{enumerate} \item $(\si\res n,\tau_1\res n)\in T^A$, \item $(\si\res n,\tau_2)\in T^B$, and \item $(\si,\tau_1)\notin T^A$, \end{enumerate} then $\rho$ is a terminal node of $T$ and put $c(\rho)=n_0$ where $$U_{n_0}=\emp.$$ \item for $\rho\in \om^{<\om}$ with length $|\rho|=3(n+1)$ and $trip(\rho)=(\si,\tau_1,\tau_2)$ if \begin{enumerate} \item $(\si,\tau_1)\in T^A$, \item $(\si\res n,\tau_2\res n)\in T^B$, and \item $(\si,\tau_2)\notin T^B$, \end{enumerate} then $\rho$ is a terminal node of $T$ and put $c(\rho)=n_1$ where $$U_{n_1}=[\si]=^{def}\{x\in \om^\om\st \si\sq x\}.$$ \item For any other $\rho$ we put $\rho$ into $T$ iff it is a proper subset of a terminal node of $T$. For these $\rho$ we put $c(\rho)=0$ if $|\rho|=3n$ or $|\rho|=3n+1$ and put $c(\rho)=1$ if $|\rho|=3n+2$. \end{enumerate} Now given $trip(\rho)=(\si,\tau_1,\tau_2)$ define the following sets: $$A_{\rho}=\{x\in [\si]\st \exists y\supseteq \tau_1\;\; \forall n \;\; (x\res n,y\res n)\in T^A\}$$ $$B_{\rho}=\{x\in [\si]\st \exists z\supseteq \tau_2\;\; \forall n \;\; (x\res n,z\res n)\in T^B\}$$ To finish the proof we verify the following: \bigskip \noindent {\bf Claim.} For each $\rho\in T$ let $trip(\rho)=(\si,\tau_1,\tau_2)$ then $$A_{\rho}\sq H(c,\rho)\sq [\si]$$ and $$B_{\rho}\sq [\si]\sm H(c,\rho)$$ \proof \bigskip Case $\rho$ a terminal node of $T$. \noindent Note that in case 1 of the definition of $T$, we have that $A_\rho$ is the empty set and $c(\si)$ is a code for the empty set and so its OK. In case 2 of the definition of $T$, we have that $B_\rho$ is the empty set and $c(\si)$ is a code for $[\si]$ and so its OK. \bigskip Case $|\rho|=3n$ and $\rho$ not terminal. \noindent Note that for nonterminal nodes $\rho$ we have that for every $k$ that $\rho k\in T$. In this case $trip(\rho k)=(\si k, \tau_1,\tau_2)$. $$A_{\rho k}=[\si k]\cap A_\rho$$ $$B_{\rho k}=[\si k]\cap B_\rho$$ and by induction $$A_\rho=\cup_{k<\om} A_{\rho k} \sq \cup_{k<\om}H(c,\rho k)=^{def}H(c,\rho)\sq [\si]$$ ($c(\rho)=0$, so we take unions) $$B_\rho=\cup_{k<\om} B_{\rho k} \sq \cup_{k<\om}([\si k]\sm H(c,\rho k))= [\si]\sm H(c,\rho)$$ The last equality holds because each $H(c,\rho k)\sq [\si k]$ and $([\si k]:k<\om)$ is a partition of $[\si]$. \bigskip Case $|\rho|=3n+1$ and $\rho$ not terminal. \noindent In this case $trip(\rho k)=(\si , \tau_1 k,\tau_2)$, and also $c(\rho)=0$, i.e., we take unions. Note that for every $k$ that $B_{\rho k}=B_\rho$ since neither $\si$ nor $\tau_2$ change. Also, by the definition of $A_\rho$ note that $$A_\rho=\cup_{k<\om}A_{\rho k}.$$ Now by inductive hypothesis we have that $$A_\rho=\cup_{k<\om}A_{\rho k}\sq \cup_{k<\om}H(c,\rho k)=^{def}H(c,\rho)$$ $$B_\rho\sq [\si]\sm H(c,\rho k)$$ for every $k$ so $$B_\rho\sq [\si]\sm H(c,\rho)$$ as was to be proved. \bigskip Case $|\rho|=3n+2$ and $\rho$ not terminal. \noindent In this case $trip(\rho k)=(\si , \tau_1 ,\tau_2 k)$, and $c(\rho)=1$, i.e., take intersections. Note that for every $k$ that $A_{\rho k}=A_\rho$ since neither $\si$ nor $\tau_1$ change. Now by inductive hypothesis we have that $$A_\rho\sq \cap_{k<\om}H(c,\rho k)=^{def}H(c,\rho)$$ $$B_\rho=\cup_{k<\om} B_{\rho k} \sq \cup_{k<\om} [\si]\sm H(c,\rho k) =[\si]\sm H(c,\rho)$$ as was to be proved. This proves the Claim. However since $A_{\la \ra}=A$ and $B_{\la \ra}=B$ the Theorem follows. \qed \newpage \addtocontents{toc}{\par\bigskip {\bf Appendix }\par} \begin{center} Appendix \end{center} \section{Turing machines\label{tur}} In this section we define the notion of Turing computable function and include Turing's analysis of why every effectively calculable function should be Turing computable. We also sketch the proof of a universal Turing machine. A \dex{Turing machine} is a function $m$ such that for some finite sets $A$ and $S$ the domain of $m$ is a subset of $S \times A$ and range of $m$ is a subset of $S \times A \times \{l,r\}$. We call $A$ the alphabet and $S$ the states.\footnote{This section is taken from my book: \par http://www.math.wisc.edu/$\sim$miller/res/index.html \par see \par Introduction to Mathematical Logic - Moore style} For example, suppose $S$ is the set of letters $\{a,b,c,\ldots,z\}$ and $A$ is the set of all integers less than seventeen, then $m(a,4)=(b,6,l)$ would mean that when the machine $m$ is in state $a$ reading the symbol $4$ it will go into state $b$, erase the symbol $4$ and write the symbol $6$ on the tape square where $4$ was, and then move left one square. \bigskip \noindent \unitlength=1.00mm \special{em:linewidth 0.4pt} \linethickness{0.4pt} \begin{picture}(69.00,30.00) %\put(0,0){\framebox(69,30)[cc]{}} \put(10.00,20.00){\framebox(10.00,10.00)[cc]{$\blank$}} \put(20.00,20.00){\framebox(10.00,10.00)[cc]{$0$}} \put(30.00,20.00){\framebox(10.00,10.00)[cc]{$3$}} \put(40.00,20.00){\framebox(10.00,10.00)[cc]{$4$}} \put(50.00,20.00){\framebox(10.00,10.00)[cc]{$\blank$}} \put(40.00,0.00){\framebox(10.00,10.00)[cc]{}} \put(45.00,2.00){\makebox(0,0)[cc]{head}} \put(45.00,7.00){\makebox(0,0)[cc]{read}} \put(45.00,10.00){\vector(0,1){10.00}} \put(24.00,11.00){\makebox(0,0)[cc]{machine $m$}} \put(24.00,4.00){\makebox(0,0)[cc]{in state $a$}} \put(5.00,20.00){\line(1,0){5.00}} \put(5.00,30.00){\line(1,0){5.00}} \put(60.00,30.00){\line(1,0){5.00}} \put(60.00,20.00){\line(1,0){5.00}} \end{picture} \bigskip \unitlength=1.00mm \special{em:linewidth 0.4pt} \linethickness{0.4pt} \begin{picture}(69.00,30.00) %\put(0,0){\framebox(69,30)[cc]{}} \put(10.00,20.00){\framebox(10.00,10.00)[cc]{$\blank$}} \put(20.00,20.00){\framebox(10.00,10.00)[cc]{$\blank$}} \put(30.00,20.00){\framebox(10.00,10.00)[cc]{$0$}} \put(40.00,20.00){\framebox(10.00,10.00)[cc]{$3$}} \put(50.00,20.00){\framebox(10.00,10.00)[cc]{$6$}} \put(60.00,20.00){\framebox(10.00,10.00)[cc]{$\blank$}} \put(40.00,0.00){\framebox(10.00,10.00)[cc]{}} \put(45.00,2.00){\makebox(0,0)[cc]{head}} \put(45.00,7.00){\makebox(0,0)[cc]{read}} \put(45.00,10.00){\vector(0,1){10.00}} \put(24.00,11.00){\makebox(0,0)[cc]{machine $m$}} \put(24.00,4.00){\makebox(0,0)[cc]{in state $b$}} \put(5.00,20.00){\line(1,0){5.00}} \put(5.00,30.00){\line(1,0){5.00}} \end{picture} \bigskip If $(a,4)$ is not in the domain of $m$, then the machine halts. This is the only way of stopping a calculation. Let $A^{<\omega}$ be the set of all finite strings from the alphabet A. The Turing machine $m$ gives rise to a partial function $M$ from $A^{<\omega}$ to $A^{<\omega}$ as follows. We suppose that $A$ always contains the blank space symbol $\blank$; and $S$ contains the starting state $a$. Given any word $w$ from $A^{<\omega}$ we imagine a tape with $w$ written on it and blank symbols everywhere else. We start the machine in state $a$ and reading the leftmost symbol of $w$. A configuration consists of what is written on the tape, which square of tape is being read, and the state the machine is in. Successive configurations are obtained according to rules determined by $m$, namely if the machine is in state $q$ reading symbol $s$ and $m(q,s)=(q^\prime,s^\prime,d)$ then the next configuration has the same tape except the square we were reading now has the symbol $s^\prime$ on it, the new state is $q^\prime$, and the square being read is one to the left if $d=l$ and one to the right if $d=r$. If $(q,s)$ is not in the domain of $m$, then the computation halts and $M(w)=v$ where $v$ is what is written on the tape when the machine halts. Suppose $B$ is a finite alphabet that does not contain the blank space symbol $\blank $ then a function $f:B^{<\omega}\to B^{<\omega}$ is a \dex{partial Turing computable function} iff there is a Turing machine $m$ with an alphabet $A\supseteq B$ such that $f = M\res B^{<\omega}$. A partial Turing computable function is \dex{Turing computable} iff it is total. A function $f:\omega \to \omega$ is Turing computable if it is Turing computable when considered as a map from $B^{<\omega}$ to $B^{<\omega}$ where $B=\{1\}$. Words in $B$ can be regarded as numbers written in base one, hence we identify the number $x$ with $x$ ones written on the tape. For example, the identity function is Turing computable, since it is computed by the empty machine. The successor function is Turing computable since it is computed by the machine in Figure \ref{succfig}. \begin{figure} \unitlength=1.00mm \special{em:linewidth 0.4pt} \linethickness{0.4pt} \begin{picture}(100.00,25.00) %\put(0.00,0.00){\framebox(64.00,24.00)[cc]{}} \put(20.00,7.00){\vector(1,0){30.00}} \put(15.00,17.00){\vector(0,-1){4.00}} \put(10.00,7.00){\line(-1,0){6.00}} \put(4.00,7.00){\line(0,1){10.00}} \put(4.00,17.00){\line(1,0){11.00}} \put(18.00,19.00){\makebox(0,0)[cc]{1}} \put(3.00,3.00){\makebox(0,0)[cc]{(1,r)}} \put(24.00,10.00){\makebox(0,0)[cc]{$\;\tilde{}\;$}} \put(44.00,10.00){\makebox(0,0)[cc]{(1,r)}} \put(15.00,7.00){\circle{12.00}} \put(55.00,7.00){\circle{12.00}} \put(15.00,7.00){\makebox(0,0)[cc]{$a$}} \put(55.00,7.00){\makebox(0,0)[cc]{$b$}} \put(70,10){\shortstack[l]{ $m(a,1)=(a,1,r)$\\ $m(a,\blank)=(b,1,r)$}} \end{picture} \caption{Successor function \label{succfig}} \end{figure} In the diagram on the left, states are represented by little circles. The arrows represent the \dex{state transition function} $m$. For example, the horizontal arrow represents the fact that when $m$ is in state $a$ and reads $\blank$ then it writes $1$, moves right, and goes into state $b$. The set of strings of zeros and ones with an even number of ones is Turing computable. Its characteristic function (parity checker) can be computed by the machine in Figure \ref{parityfig}. \begin{figure} \unitlength=1.00mm \special{em:linewidth 0.4pt} \linethickness{0.4pt} \begin{picture}(130.00,40.00) %\put(00.00,000.00){\framebox(69.00,40.00)[cc]{}} \put(15.00,025.00){\circle{10.00}} \put(55.00,025.00){\circle{10.00}} \put(35.00,009.00){\circle{10.00}} \put(15.00,025.00){\makebox(0,0)[cc]{$a$}} \put(55.00,025.00){\makebox(0,0)[cc]{$b$}} \put(35.00,009.00){\makebox(0,0)[cc]{$c$}} \put(20.00,028.00){\vector(1,0){30.00}} \put(50.00,023.00){\vector(-1,0){30.00}} \put(15.00,020.00){\vector(4,-3){15.00}} \put(55.00,020.00){\vector(-4,-3){14.00}} \put(15.00,030.00){\line(0,1){4.00}} \put(15.00,034.00){\line(-1,0){10.00}} \put(05.00,034.00){\line(0,-1){9.00}} \put(05.00,025.00){\vector(1,0){5.00}} \put(60.00,025.00){\line(1,0){6.00}} \put(66.00,025.00){\line(0,1){9.00}} \put(66.00,034.00){\line(-1,0){11.00}} \put(55.00,034.00){\vector(0,-1){4.00}} \put(18.00,035.00){\makebox(0,0)[cc]{$0$}} \put(05.00,022.00){\makebox(0,0)[cc]{$(\blank,r)$}} \put(24.00,031.00){\makebox(0,0)[cc]{$1$}} \put(45.00,031.00){\makebox(0,0)[cc]{$(\blank,r)$}} \put(45.00,021.00){\makebox(0,0)[cc]{$1$}} \put(25.00,021.00){\makebox(0,0)[cc]{$(\blank,r)$}} \put(13.00,015.00){\makebox(0,0)[cc]{$\blank$}} \put(22.00,009.00){\makebox(0,0)[cc]{$(1,r)$}} \put(47.00,009.00){\makebox(0,0)[cc]{$(\blank,r)$}} \put(56.00,017.00){\makebox(0,0)[cc]{$\blank$}} \put(63.00,022.00){\makebox(0,0)[cc]{$0$}} \put(57.00,037.00){\makebox(0,0)[cc]{$(\blank,r)$}} \put(80,10){\shortstack[l]{ $ m(a,0)=(a,\blank ,r)$ \\ $ m(a,1)=(b,\blank ,r)$ \\ $ m(b,0)=(b,\blank ,r)$ \\ $ m(b,1)=(a,\blank ,r)$ \\ $ m(a,\blank)=(c,1,r)$ \\ $ m(b,\blank)=(c,\blank,r)$ }} \end{picture} \caption{Parity checker \label{parityfig}} \end{figure} The following problems are concerned with Turing computable functions and predicates on $\omega$. \bigskip \prob Show that any constant function is Turing computable. \prob A binary function $f:\omega\times\omega\to\omega$ is Turing computable iff there is a machine such that for any $x,y\in\omega$ inputing $x$ ones and $y$ ones separated by ``,'' the machine eventually halts with $f(x,y)$ ones on the tape. Show that $f(x,y) = x+y$ is Turing computable. \prob Show that $g(x,y) = x y$ is Turing computable. \prob Let $ x \dotminus y = max\{ 0,x-y \}.$ Show that $p(x)= x \dotminus 1$ is Turing computable. Show that $ q(x,y)= x\dotminus y $ is Turing computable. \prob Suppose $f(x)$ and $g(x)$ are Turing computable. Show that $f(g(x))$ is Turing computable. \prob Formalize a notion of multitape Turing machine. Show that we get the same set of Turing computable functions. \prob Show that we get the same set of Turing computable functions even if we restrict our notion of computation to allow only tapes that are infinite in one direction. \prob Show that the family of Turing computable functions is closed under arbitrary compositions, for example $f(g(x,y),h(x,z),z)$. More generally, if $f(y_1,\ldots,y_m)$, $g_1(x_1,\ldots,x_n),\ldots$, and $g_m(x_1,\ldots,x_n)$ are all Turing computable, then so is $$f(g_1(x_1,\ldots,x_n),\ldots,g_m(x_1,\ldots,x_n)).$$ \prob A set is Turing computable iff its characteristic function is. Show that the binary relation $x=y$ is Turing computable. Show that the binary relation $ x\leq y $ is Turing computable. \prob Define $$ sgn(n) = \left\{ \begin{array}{ll} 0 & \mbox{ if } n=0 \\ 1 & \mbox{ otherwise} \end{array} \right.$$ Show it is Turing computable. \prob Show that if $A \subseteq \omega$ is Turing computable then so is $ \omega \setminus A.$ Show that if $A$ and $B$ are Turing computable so is $ A \cap B$ and $ A \cup B$. \prob Suppose g(x) and h(x) are Turing computable and A is a Turing computable set. Show that f is Turing computable where: $$ f(x) = \left\{ \begin{array}{ll} g(x) & \mbox{ if } x \in A \\ h(x) & \mbox{ if } x \notin A \end{array} \right.$$ \prob Show that the set of even numbers is Turing computable. Show that the set of primes is Turing computable. \prob Show that $e(x,y)=x^y$ is Turing computable. Show that $f(x)=x!$ is Turing computable. \prob Suppose that $h(z)$ and $g(x,y,z)$ are Turing computable. Define $f$ by recursion, $f(0,z)=h(z)$ and $f(n+1,z) = g( n,z, f(n,z) )$. Show that $f$ is Turing computable. \prob Prove that the set of partial Turing computable functions is the same as the set of partial recursive functions. \prob Prove that the halting problem for nonwritting Turing machines is decidable. A Turing machine m is nonwritting iff whenever $m(s,a)=(s',a',d)$ then $a=a'$. It is decidable whether or not $m$ halts when given input $x=\in A^n$ started on $x_1$ in state $s_0$. \begin{center} Church-Turing Thesis \end{center} Here is an excerpt in support of Church's Thesis from Alan M. Turing\footnote{ ``On computable numbers, with an application to the Entscheidungsproblem'', Proceedings of the London Mathematical Society, 2-32(1936), 230-265.}. Note that Turing uses the word computer for the person that is performing some effective procedure. `` Computing is normally done writing certain symbols on paper. We may suppose this is divided into squares like a child's arithmetic book. In elementary arithmetic the two-dimensional character of the paper is sometimes used. But such a use is always avoidable, and I think that it will be agreed that the two-dimensional character of paper is no essential of computation. I assume then that the computation is carried out on one-dimensional paper, i.e. on a tape divided into squares. I shall also suppose that the number of symbols which may be printed is finite. If we were to allow an infinity of symbols, then there would be symbols differing to an arbitrarily small extent. The effect of this restriction of the number of symbols is not very serious. It is always possible to use sequences of symbols in the place of single symbols. Thus an Arabic numeral 17 or 9999999999999999999 is normally treated as a single symbol. Similarly in any European language words are treated as single symbols (Chinese, however, attempts to have an infinity of symbols). The differences from our point of view between the single and compound symbols is that the compound symbols, if they are too lengthy, cannot be observed at one glance. This is in accordance with experience. We cannot tell at one glance whether 9999999999999999999999999 and 99999999999999999999999999 are the same. `` The behavior of the computer at any moment is determined by the symbols which he is observing, and his `state of mine' at that moment. We may suppose that there is a bound $B$ to the number of symbols or squares which the computer can observe at one moment. If he wishes to observe more, he must use successive observations. We will also suppose that the number of states of mind which need be taken into account is finite. The reasons for this are of the same character as those which restrict the number of symbols. If we admitted an infinity of states of mind, some of them will be `arbitrarily close' and will be confused. Again, the restriction is not one which seriously affects computation, since the use of more complicated states of mind can be avoided by writing more symbols on the tape. `` Let us imagine the operations performed by the computer to be split up into `simple operations' which are so elementary that it is not easy to imagine them further divided. Every such operation consists of some change of the physical system consisting of the computer and his tape. We know the state of the system if we know the sequence of symbols on the tape, which of these are observed by the computer (possibly with a special order), and the state of mind of the computer. We may suppose that in a simple operation not more than one symbol is altered. Any other changes can be split up into simple changes of this kind. The situation in regard to squares whose symbols may be altered in this way is the same as in regard to the observed squares. We may, therefore, without loss of generality, assume that the squares whose symbols are changed are always `observed' squares. `` Besides these changes of symbols, the simple operations must include changes of distribution of observed squares. The new observed squares must be immediately recognizable by the computer. I think it is reasonable to suppose that they can only be squares whose distance from the closest of the immediately previously observed squares does not exceed a certain fixed amount.... `` The operation actually performed is determined, as has been suggested above, by the state of mind of the computer and the observed symbols. In particular, they determine the state of mind of the computer after the operation. '' \begin{center} {\bf Universal Turing Machine} \end{center} In his paper Turing also proved the following remarkable theorem. \begin{theorem} There is a partial Turing computable function $f(n,m)$ such that for every partial Turing computable function $g(m)$ there is an $n$ such that for every $m$, $f(n,m)=g(m)$. Equality here means either both sides are defined and equal or both sides are undefined. \end{theorem} \proof Given the integer $n$ we first decode it as a sequence of integers by taking its prime factorization, $n=2^{k_1}3^{k_2}\cdots p_m^{k_m}$ ($p_m$ is the $m^{th}$ prime number). Then we regard each integer $k_j$ as some character on the typewriter (if $k_j$ too big we ignore it). If the message coded by $n$ is a straight forward description of a Turing machine, then we carry out the computation this machine would do when presented with input $m$. If this simulated computation halts with output $k$, then we halt with output $k$. If it doesn't halt, then neither does our simulation. If $n$ does not in a straight forward way code the description of a Turing machine, then we pretend its coding the empty function, i.e. we just never halt. \qed \section{Trees, Konig's Lemma, Low basis} \begin{define} Recall: \begin{enumerate} \item A nonempty $T\sq 2^{<\om}$ is a tree iff $\si\su\tau\in T$ implies $\si\in T$. \item For $T\sq 2^{<\om}$ a tree, define: $$[T]=\{b\in 2^\om: \forall n\;\; b\res n \in T\}$$ the infinite branches of $T$. \item For $\si\in T$ define: $$T(\si)=\{\rho\in T:\rho\su\si \rmor \si\su\rho\}.$$ \end{enumerate} \end{define} \begin{lemma} (Konig's Lemma) If $T\su 2^{<\om}$ is an infinite tree, then $[T]$ is nonempty. \end{lemma} \proof Construct $b\res n$ by induction so that $T(b\res n )$ is infinite. \qed \begin{example} There exists an infinite \rec tree $T\su 2^{<\om}$ with no \rec branch. \end{example} \proof Let $K_0$ and $K_1$ be disjoint \recly inseparable sets. Put $\si\in T$ iff for all $n<|\si|$ and $i=0,1$ if $n\in K_{i,|\si|}$ then $\si(n)=i$. Then the infinite branches of $T$ are the characteristic functions of separating sets. \qed \begin{prop} Suppose $T\su 2^{<\om}$ is a \rec tree, and $[T]$ is countable, then there exists a \rec $b$ in $[T]$. \end{prop} \proof There must be a $\si\in T$ such that $[T(\si)]$ has exactly one element, otherwise $T$ contains a perfect tree. This one element $b$ must be \rec. To see this, note that if $\si\su\tau$ and $\tau\not\su b$, then the tree $T(\tau)$ is finite. Hence to determine $b\res n$ for any $n>|si|$ we search for an $m>n$ such that exactly one $\tau\in 2^n\cap T(\si)$ has an extension at level $m$. \qed \begin{prop} (Low basis, Jocusch and Soare) If $T\su 2^{<\om}$ is an infinite \rec tree, then there exists $b\in [T]$ with $b^\pr\equiv_T 0^\pr$. \end{prop} \proof Inductively construct \rec trees $T_e$ with $T_0=T$ as follows: Given $T_e$ define the tree: $$\hat{T}_e=\{\si\in T_e: \{e\}_{|\si|}^\si(e)\uparrow\}.$$ Case 1. $\hat{T}_e$ is infinite. Put $T_{e+1}=\hat{T}_e$. Case 2. $\hat{T}_e$ is finite. Put $T_{e+1}={T}_e$. Since $T_{e+1}\su T_e$ are all infinite trees, the set $\bigcap_eT_e$ is an infinite tree. This is because the intersection of trees is always a tree. It is infinite because for any $n<\om$ there must be $\si\in 2^n$ which is in infinitely many $T_e$ and hence all. By Konig's Lemma there exists $b\in \bigcap_e[T_e]$. To see, that $b^\pr=0^\pr$, note that $e\in b^\pr$ iff Case 2 occurred at step $e$ in the construction. But this can be answered uniformly by $0^\pr$. \qed \exer Find a \rec tree $T\su\om^{<\om}$ which is binary branching, and such that $[T]=\{b\}$ where $b\equiv_T 0^\pr$. Binary bran \exer % qual 2005-1 Prove there exists an infinite \rec subtree $T\su \om^{<\om}$ such that $T$ does not contain an infinite \rec chain or an infinite \rec antichain. $T$ is a subtree of $\om^{<\om}$ means that $\si \su \tau\in T$ implies $\si\in T$ for every $\si,\tau\in \om^{<\om}$. $C\su T$ is a chain iff $\si\su \tau$ or $\tau\su \si$ for every $\si,\tau\in C$. $A\su T$ is an antichain iff $\si\su \tau$ for $\si,\tau\in T$ just in case $\si=\tau$. \end{document}