% LaTeX Article Template - using defaults \documentclass{article} \usepackage{amssymb} \usepackage{latexsym} \usepackage{amssymb} \usepackage{latexsym} % Set left margin - The default is 1 inch, so the following % command sets a 1.25-inch left margin. \setlength{\oddsidemargin}{-0.15in} % Set width of the text - What is left will be the right margin. % In this case, right margin is 8.5in - 1.25in - 6in = 1.25in. \setlength{\textwidth}{6.5in} % Set top margin - The default is 1 inch, so the following % command sets a 0.75-inch top margin. \setlength{\topmargin}{-0.1in} % Set height of the header \setlength{\headheight}{0.3in} % Set height of the text \setlength{\textheight}{8.1in} % Set vertical distance between the text and the % bottom of footer \setlength{\footskip}{0.8in} % Set the beginning of a LaTeX document \begin{document} \title{\huge An argument due to Leo Harrington} \author{Greg Hjorth} % Enter your name between curly braces \date{\today} % Enter your date or \today between curly braces \maketitle \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{claim}[theorem]{Claim} \newenvironment{proof}[1][Proof]{\begin{trivlist} \item[\hskip \labelsep {\bfseries #1}]}{\hfill$\Box$\end{trivlist}} \newenvironment{definition}[1][Definition]{\begin{trivlist} \item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}} \newenvironment{example}[1][Example]{\begin{trivlist} \item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}} \newenvironment{remark}[1][Remark]{\begin{trivlist} \item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}} \newenvironment{notation}[1][Notation]{\begin{trivlist} \item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}} \newenvironment{question}[1][Question]{\begin{trivlist} \item[\hskip \labelsep {\bfseries #1}]}{\end{trivlist}} \def\Ubf#1{{\baselineskip=0pt\vtop{\hbox{$#1$}\hbox{$\sim$}}}{}} \def\ubf#1{{\baselineskip=0pt\vtop{\hbox{$#1$}\hbox{$\scriptscriptstyle\sim$}}}{}} \def\R{{\mathbb R}} \def\C{{\mathbb C}} \def\V{{\mathbb V}} \def\N{{\mathbb N}} \def\Z{{\mathbb Z}} \def\K{{\mathbb K}} \def\B{{\mathbb B}} \def\o{{\omega}} \def\oo{{\omega^{\omega}}} \def\lo{{\omega^{<\omega}}} \def\d{{\dot{\bigcup}}} \def\h{{\cal H}} \def\no{\noindent} \def\a{{\mathcal A}} \def\b{{\mathcal B}} \def\l{{\mathcal L}} \def\n{{\mathcal N}} \def\m{{\mathcal M}} \def\p{{\mathcal P}} \def\h{{\mathcal H}} \def\ht{{\hat{\mathcal T}}} \def\co{{\mathcal O}} \def\t{{\mathcal T}} \def\c{{\mathcal C}} %\tableofcontents \section{Introduction} \label{introduction} We present a detailed account of the method sketched in \cite{harrington} and \cite{harrington1}. We also present Harrington's solution to question 57* from the end notes of Harvey Friedman's \cite{friedman}. \section{Notation} \begin{notation} $(\varphi_e)_{e\in\omega}$ refers to some standard enumeration of the partial recursive functions $\varphi:\omega\rightarrow\omega$. If $\psi$ is a partial function, then \[\psi\downarrow(e)\] is used to indicate that $e$ is in the domain on which $\psi(e)$ is defined. For $x\in \oo$ we let $(\Phi_e(x))_{e\in\omega}$ be some reasonably effective enumeration of the partial recursive in $x$ functions $\Phi:\omega\rightarrow\omega$. For $s\in\lo$ we write \[\Phi_e(s)(m)=n\] if for any $x\supset s$ we have $\Phi_e(x)\downarrow (n)$ with value $m$ and just using the part of $x$ already in $s$. Similarly we use $(\Phi_e(x,y))_{e\in\omega}$ to enumerate the functions recursively enumerable in $x$ and $y$, and there on we adopt the parallel notation of $\Phi_e(s, t)$ for $s, t\in\lo$. \end{notation} \begin{notation} $\subset$ refers to not necessarily strict inclusion. \end{notation} \begin{notation} $T\subset\lo\times\lo$ is said to be {\it closed downward} if whenever $(s, t)\in T$ and $s'\subset s$, $t'\subset t$ we have $(s', t')\in T$. For such a $T$ we then let $[T]$ be the set of all $(x, y)\in \oo\times\oo$ which have $(x|_n, y|_n)\in T$ at every $n$. We informally say that $(s, t)$ is {\it included in } $(u, v)$ if $s\subset u$ and $t\subset v$ both hold. We say that $(s, t)$ is {\it incompatible} with $(u, v)$, written $(s, t)\perp (u,v)$, if $(s, t)$ is not included in $(u, v)$ and $(u, v)$ is not included in $(s, t)$. We write $s\perp t$, for $s, t\in \lo$ if neither is an initial segment of the other. \end{notation} %\begin{notation} We fix now a recursive enumeration %$(\t (n))_n$ a subset of $\lo$ such that %\leftskip 0.4in %(i) $\t (n)\subset \t (n+1)\subset \lo$; %(ii) $\t (n)$ is closed downward; %(iii) $\t(n)$ has size $n$; %(iv) $\lo=\bigcup \t (n)$. %\leftskip 0in %\noindent Thus in particular $\t (n+1)\setminus \t(n)$ contains a %single element. %\end{notation} \begin{notation} Let $\rho(\cdot, \cdot): \omega\times\omega\rightarrow \omega$ be a recursive bijection. For $j\in \omega$ and $s\in \lo$, let $p_j(s)\in \lo$ be defined so that it has the same length as $s$ and $(p_j(s))(\rho(n, m))=s(\rho( n, m))$ if $n\neq j$ whilst $(p_j(s))(\rho( j, m))=0$ for $\rho ( j, m)$ in the domain of $s$. \end{notation} In other words, $p_j$ is the function which suppresses information on the $j^{\rm th}$ copy of $\omega$. %\begin{notation} For $n, j\in \omega$, let $\t^j(n)=\{p_j(s): s\in \t (n)\}$. %\end{notation} \section{Harrington's method} The mathematical ideas from this section are all due to Leo Harrington. He however cannot be blamed for the cumbersome definitions and the careless errors, which are all due to the author. Because we will later need to apply ideas of boundedness or overspill to his argument, we need at this stage to describe it as a static set theoretical construction, rather than as a dynamic priority argument. \def\tj{{\mathcal T}^j} \begin{definition} Fix $i, j\in \omega$. For $T\subset\lo\times\lo$ closed downward and recursively enumerable, fix some canonical enumeration of increasing finite subsets, $(T^{(n)})_{n\in\omega}$, with the properties that:- \leftskip 0.4in \noindent (i) $T^{(n)}\subset T^{(n+1)}\subset T$; \noindent (ii) each $T^{(n)}$ is closed downwards and has size at most $n$; \noindent (iii) $n\mapsto T^{(n)}$ is recursive; \noindent (iv) $T=\bigcup_n T^{(n)}$. \leftskip 0in We then let $\t(n)=\{s:\exists t((s, t)\in T^{(n)})\}$ be the various respective projections to the first coordinate and let $\tj(n)=\{p_j(s): s\in \t(n)\}$ be the result of discarding the information on the $j^{\rm th}$ copy of $\omega$. Then an {\it $i$-$j$-step down of $T$} consists of recursively enumerable closed downward $U\subset \lo\times\lo$ along with recursive assignments \[((A_{\bar{s}, m}^n)_{\bar{s}\in \tj(n), m\leq n})_{n\in \omega},\] \[(U_n)_{n\in \omega}, \] \[((\pi^n_{\bar{s}})_{\bar{s}\in \tj(n)})_{n\in\omega}, \] satisfying the following 7 conditions:- \medskip (I) If $\bar{s}\in \tj (n)$, then $\pi^n_{\bar{s}}$ is a strictly order preserving function from \[\{(s, t)\in T^{(n)}: lh(s)=lh(t); p_j(s)\subset \bar{s}; s, t\in \t(n)\}\] to $\lo$. For $n'\leq n$ we have \[\pi^{n'}_{\bar{s}}\subset \pi^n_{\bar{s}}.\] \medskip (II) We let $B_{\bar{s}}^n$ be \[\{v: \exists w\in {\rm \: ran}(\pi^n_{\bar{s}}) (v\subset w)\}, \] the downward closure of the range of $\pi_{\bar{s}}^n$. Then we have first of all that $\{A^n_{\bar{s}, m}: m\leq n\}$ partitions $B^n_{\bar{s}}$, with $v\subset v'$ implying that for some $m\leq m'$ we have $v\in A^n_{\bar{s}, m}, v'\in A^n_{\bar{s}, m'}$ -- in other words, sequences in the member of the partition corresponding to larger $m'$ extend sequences in the member of the partition corresponding to smaller $m$. We furthermore have that for $n'\leq n$, $A^{n'}_{\bar{s}, m}\subset A^n_{\bar{s}, m}$. \medskip (III) We demand that the $\pi^n_{\bar{s}}$ split apart incompatible elements of $T$ of length greater than $i$. More precisely: If $\bar{s}\in \tj(n)$, \[(s_1, t_1)\perp (s_2, t_2),\] \[(s_1, t_1), (s_2, t_2)\in\:{\rm dom}(\pi^n_{\bar{s}}),\] \[lh(s_1), lh(s_2)>i,\] then \[\pi_{\bar{s}}^n(s_1, t_1)\perp \pi_{\bar{s}}^n(s_2, t_2).\] \medskip (IV) We demand that $\pi^n_{\bar{s}}$ always chooses new values for $\pi^n_{\bar{s}}(s^\smallfrown p, t^\smallfrown q)$. More precisely: If $\bar{s}^*\subset \bar{s}$ are both in $\tj(n)$, $(s^\smallfrown p_1, t^\smallfrown q_1)\in$ dom$(\pi^n_{\bar{s}^*})$, $(s^\smallfrown p_2, t^\smallfrown q_2)\in$ dom$(\pi^n_{\bar{s}})$, $(p_1, q_1)\neq (p_2, q_2)$, and for some $v$ of length $\ell$, $\ell\geq i$, we have \[v=\pi^n_{\bar{s}^*}(s, t)=\pi^n_{\bar{s}}(s, t),\] then \[(\pi^n_{\bar{s}^*}(s^\smallfrown p_1, t^\smallfrown q_1))(\ell)\neq (\pi^n_{\bar{s}}(s^\smallfrown p_2, t^\smallfrown q_2))(\ell).\] \medskip (V) We also add some minor bookkeeping conditions to ensure that \[U=\bigcup U_n\] at the first $i$ levels it resembles $T$, and that in some natural sense it is generated by the values of the $p_j(s)$ along with the various $\pi^n_{\bar{s}}$ applied to the elements of $T$. %The first of these conditions mimics (IV), in that we just simply %require the new values of the form $\pi^{n+1}_{\bar{s}}(s, t)(\ell)$ are %all outside some given finite set. %(a) If $n\geq i$, $(\bar{s}, u)\in U_{n+1}$, $v|_{k+1}\notin U_n$, then at %all $\ell \geq k, i$ we have $v(\ell)>n$. (a) $\pi^n_{\bar{s}}(s, t)=t$ for all $(s, t)$ in dom$(\pi^n_{\bar{s}})$ with $lh(s)=lh(t)\leq i$. (b) $U=\bigcup U_n$. (c) $U_n=\{(\bar{s}, u): \bar{s}\in \tj(n), \exists (s, t)\in {\rm dom}(\pi^n_{\bar{s}}) (u\subset \pi_{\bar{s}}^n(s, t))\}.$ \medskip (VI) (The ``no injury" case of the construction.) Here we consider some possibly new $\bar{s}^\smallfrown \bar{p}\in \tj(n+1)$ and simply build on top of the previously established values for the $\pi^{n+1}_{\bar{s}}(s, t)$, placing these new values of the form $\pi^{n+1}_{\bar{s}^\smallfrown \bar{p}}(s^\smallfrown p, t^\smallfrown q)$ into the first element of the partition $(A^{n+1}_{\bar{s}^\smallfrown \bar{p}, m})_{m\leq n}$ above all the earlier choices along that branch: More precisely: For all $\bar{s}^\smallfrown\bar{p}\in \tj(n+1)$, $(s, t)\in$ dom$(\pi^{n+1}_{\bar{s}}) \subset$ dom$(\pi^{n+1}_{\bar{s}^\smallfrown \bar{p}})$, with $\pi^{n+1}_{\bar{s}}(s, t)=\pi^{n+1}_{\bar{s}^\smallfrown \bar{p}}(s, t)$, we have for all $m\in \omega$ and for all $u\subset \pi^{n+1}_{\bar{s}}(s, t)$ \[u\in A^{n+1}_{\bar{s}, m}\Leftrightarrow u\in A^{n+1}_{\bar{s}^\smallfrown \bar{p}, m}.\] Moreover under these circumstances, if $(s^\smallfrown p, t^\smallfrown q)\in $ dom$(\pi^{n+1}_{\bar{s}^\smallfrown \bar{p}})\setminus$ dom$(\pi^{n+1}_{\bar{s}})$ and $\pi^{n+1}_{\bar{s}^\smallfrown \bar{p}}(s, t)\in A^{n+1}_{\bar{s}, m_0}$, then \[(s^\smallfrown p, t^\smallfrown q)\in A^{n+1}_{\bar{s}^\smallfrown \bar{p}, m_0+1},\] \[lh(\pi^{n+1}_{\bar{s}^\smallfrown \bar{p}}(s^\smallfrown p, t^\smallfrown q)) = lh(\pi^{n+1}_{\bar{s}}(s, t))+1.\] \medskip (VII) (The ``injury" case of the construction) The injury case of the construction arises because we see a place in $U_n$ where something valuable happens -- either some integer gets placed in the halting set relative to any reals $(\bar{y}, x)$ extending $(\bar{s}, w)$ or we get the chance to make some calculation diagonalize off $\bar{y}'$. In this case we adjust the embedding of $T$ into $U$ so as to make that event happen for a collection of values of the form $\pi^{n+1}_{\bar{s}^\smallfrown \bar{p}}(s, t)$ without damaging any earlier requirements. We do this at some point $(\hat{s}, \hat{t})\in T$ and all nodes below; the old values of $\pi^{n+1}_{\bar{s}}$ for $s\supset \hat{s}, t\supset \hat{t}$ are largely bypassed, and become dead branches on the tree $U$, which by (IV) above can never be revisited. Before describing this case we need an extended sequence of definitions. \begin{notation} $R_1(\bar{s}, w, e)$ is the statement that $\Phi_e(\bar{s}, w)\downarrow(e)$ in $\leq lh(\bar{s})$ steps. \end{notation} \begin{notation} $R_2(\bar{s}, w, e)$ is the statement that there is some $e'\leq lh(\bar{s})$ \[\Phi_e(\bar{s}, w)\downarrow(e')=1\] in $\leq lh(\bar{s})$ steps, and moreover \[\Phi_{e'}(\bar{s})\downarrow (e')\] in $\leq lh(\bar{s})$ steps. \end{notation} \begin{notation} Given \[\bar{s}^\smallfrown \bar{p}\in \tj(n+1)\setminus\tj(n),\] \[v=\pi^{n+1}_{\bar{s}}(\hat{s}, \hat{t})\in A^{n+1}_{\bar{s}, m},\] we let \[Q(\bar{s}^\smallfrown \bar{p}, v, m')\] be the statement that $lh(v)>i$, $lh(\hat{s}, \hat{t})>i$, $lh(\bar{s})>i$, $m'i$ such that at all $\ell > N$ we have \[\pi_{\bar{y}|_\ell}(s, t)=v\subset \hat{x}.\] \medskip \noindent{\bf Claim(2):} If $\ell >N$ and $(s^\smallfrown p, t^\smallfrown q)\in$ dom$(\pi_{\bar{y}|_\ell})$ has \[ \pi_{\bar{y}|_{\ell}}(s^\smallfrown p, t^\smallfrown q)\supset \hat{x}|_{lh(v)+1},\] then \[\pi_{\bar{y}|_{\ell}}(s^\smallfrown p, t^\smallfrown q)\subset \hat{x}.\] \medskip \noindent{\bf Proof of claim:} Since $\pi_{\bar{y}|_{\ell}}(s, t)$ is never injured, the claim follows from (III) in the same manner as claim(1). \hfill ($\square$Claim) \medskip Now one easily defines $(y|_k, x|_k)$ by induction on $k$ so as to guarantee that \[\forall^\infty \ell (\pi_{\bar{y}|_\ell} (y|_k, x|_k)\subset \hat{x}).\] \end{proof} \begin{definition} Given $(y, x)\in [T]$, $\bar{y}=p_j(x)$, and $\hat{x}$ such that \[\forall k\forall^\infty \ell (\pi_{\bar{y}|_\ell }(y|_k, x|_k)\subset \hat{x}),\] as in \ref{corollary1}, we let \[\pi_{\bar{y}}(y, x)=\hat{x}.\] \end{definition} Thus we have shown that \[(y, x)\mapsto (p_j(y), \pi_{p_j(y)}(x, y))\] provides a bijection of $[T]$ with $[U]$. It follows from the structure of the definition that $\pi_{\bar{y}}(y, x)$ is always uniformly recursive in $(\bar{y}', y, x)$. \begin{lemma} \label{3.6} $(\bar{y}, \pi_{\bar{y}}(y, x))'$ is uniformly recursive in $(\bar{y}', y, x)$. \end{lemma} \begin{proof} It follows from the description of the injury step at (VII) for $m'=2^e+i$ and lemma \ref{3.4} that \[\Phi_e(\bar{y}, \pi_{\bar{y}}(y, x))\uparrow(e)\] if and only if there is some $v\subset \pi_{\bar{y}}(y, x)$ such that for all $w\supset v$, $\bar{s}\subset \bar{y}$ with $lh(\bar{s})$ sufficiently large \[\Phi_e(\bar{s}, w)\uparrow(e).\] This provides a $\Sigma^0_1(\bar{y}', \pi_{\bar{y}}(y, x))$ characterization of whether $e$ is in the halting set for $(\bar{y}, \pi_{\bar{y}}(y, x))$. \end{proof} \begin{lemma} \label{3.7} $\bar{y}'$ is never recursive in $(\bar{y}, \pi_{\bar{y}}(y, x))$. \end{lemma} \begin{proof} Otherwise suppose there is $e$ with \[\Phi_{e'}(\bar{y})\uparrow (e')\Leftrightarrow \Phi_e(\bar{y}, \pi_{\bar{y}}(y, x)) \downarrow (e')=1.\] The following the description of the injury case at $m'=3^{e+1}+i$ we have that there is some $v\subset \pi_{\bar{y}}(y, x)$ such that at every $w\supset v$, $\bar{s}\subset \bar{y}$ \[\Phi_e(\bar{s}, w)\downarrow (e')=1\] entails $\Phi_{e'}(\bar{y})\uparrow(e')$. Following on from our supposition at the start of the lemma this gives a $\Sigma^0_1(y)$ definition of $\bar{y}'$, with an absurdity. \end{proof} \begin{definition} A recursive linear ordering $(X, <_X)$ is {\it suitable} if \leftskip 0.4in (a) $X\subset \omega$; (b) the set of limit points is recursive; we denote this set by lim$(X)$; (c) the set of predecessors is recursive, and the successor operation is recursive on this set; (d) the linear ordering comes with a recursive assignment \[{\rm lim}(X) \rightarrow X^\omega\] \[\lambda\mapsto (\alpha_{n, \lambda})_{n\in \omega}\] such that \leftskip 0.6in (i) each $(\alpha_{n, \lambda})_n$ is a strictly increasing sequence converging to $\lambda$; (ii) for all $\beta\in X$ there are only finitely many $\lambda>_X\beta$ which have some \[\alpha_{n, \lambda}<_X\beta,\] and moreover this finite set can be located recursively in $\beta$; (iii) for each $\lambda\in$ lim$(X)$ there are cofinally many $\beta<_X\lambda$ which provide a cut point for the cofinal sequences associated to limits below $\lambda$; that is to say, if a limit $\lambda^*$ has \[\beta<_X\lambda^*<_X \lambda,\] then at every $n$ \[\beta <_X \alpha_{n,\lambda^*}.\] \leftskip 0in \end{definition} It is routine to show that for any $\kappa<\omega_1^{\rm ck}$ there is a suitable recursive linear order of order type $\kappa$. We need to use (iii) later, so it is a good idea now to make clear how it is being used. (iii) says that in particular there is no limit $\lambda$ and increasing convergent sequence of limits, \[\lambda_\ell\rightarrow \lambda,\] and integers $(n_{\ell})_{\ell\in \omega}$ such that at each $\ell$ \[\alpha_{n_{\ell +1}, \lambda_{\ell +1}}\leq_X\lambda_{\ell}.\] In the next definition we need an embellishment on the $p_j(s)$ notation. \begin{definition} If $I\subset \omega$, then we define $p_I(s)=\bar{s}$ by \[\bar{s}(\rho(\ell, m))=0\] if $\ell \in I$; \[\bar{s}(\rho(\ell, m))=s(\rho(\ell, m))\] if $\ell\not\in I$; in other words, $p_I(s)$ suppresses all values of $s$ on the copies\footnote{Recall that $\rho: \omega\times \omega\rightarrow \omega$ is our recursive bijection which serves for pairing.} of $\omega$ indexed in $I$. We are especially interested in this definition in the case that $(X, <_X)$ is a recursive linear ordering, $\beta, \lambda\in X$, and $I$ equals \[(\beta, \lambda ]_X =_{\rm df} \{\alpha\in X: \beta<_X \alpha\leq_X \lambda\}.\] \end{definition} At some points later we will be implicitly using that $p_{I_1}\circ p_{I_2}=p_{I_1 \cup I_2}$. \begin{definition} Let $T\subset\lo\times\lo$ be recursively enumerable and closed downward. Let $\kappa$ be a recursive ordinal. $T$ is said to have a {\it $\kappa$-unraveling} if there is a suitable recursive linear ordering $(X, <_X)$ of order type $\kappa+1$, and corresponding $((\alpha_{n, \lambda})_n)_{\lambda\in {\rm lim}(X)}$ and a recursively enumerable array of trees $(T_j)_{j\in X}$ such that: \leftskip 0.4in (a) for $j_0$ the top most element of $X$ we have $T_{j_0}=T$; (b) if $j\in X$ and $j+$ is its successor in $X$, and we let $n_j$ be the supremum of all $n$ for which there exists \[\lambda>_X j\] with \[\alpha_{n, \lambda}\leq _X j,\] then $T_j$ is the $n_j$-$j+$-step down of $T_{j+}$; (c) if $\lambda$ is a limit and $\alpha_{n, \lambda}\leq_Xj$, then for all $(\bar{s}, t)\in \omega^{\leq n}\times \omega^{\leq n}$ we have \[(\bar{s}, t)\in T_j\] if and only if there exists some $s$ with $p_{(j,\lambda]_X}(s)=\bar{s}$ and \[(s, t)\in T_{\lambda}.\] \end{definition} \begin{lemma} \label{3.8} \label{maintechnical} Any recursively enumerable downward closed $T\subset\lo\times\lo$ has a $\kappa$-unraveling at any recursive ordinal $\kappa$. \end{lemma} \begin{proof} Let $(X, <_X)$ be a suitable linear ordering of order type $\kappa+1$ and top most element $j_0$. For any recursive array $(T_j)_{j\in X}$ having $T_{j_0}=T$ we define a new recursive array $(\hat{T}_j)_{j\in X}$ again having $\hat{T}_{j_0}=T$ and defined by the following complicated recipe: \leftskip 0.4in For $j\in X$ let $j+$ be the $<_X$ successor of $j$. Let $\Lambda(j)$ be the set of limit $\lambda$'s which have $\lambda>_X j$ and at some $n$ \[\alpha_{n, \lambda}\leq_Xj,\] and let $n(j)$ be the supremum of all $n$ for which there exists $\lambda\in \Lambda(j)$ and we have \[\alpha_{n, \lambda}\leq_X j.\] With this granted we can define the new array $(\hat{T}_j)_{j\in X}$: \medskip \noindent (i) We let $\hat{T}_j$ be some recursively enumerable tree with $\hat{T}_j\cap (\omega^{\leq n(j)}\times \omega^{\leq n(j)})$ equal to the set of all \[(p_{(j, \lambda]_X}(s), t),\] with $\lambda\in \Lambda(j)$ and for which there exists $n\in \omega$, with $(s, t)\in T_\lambda\cap(\omega^{\leq n}\times \omega^{\leq n})$ and \[\alpha_{n, \lambda}\leq_X j.\] \medskip \noindent (ii) If some canonical choice of an $n(j)$-$j^+$-step down of $T_{j+}$ intersected with $(\omega^{\leq n(j)}\times \omega^{\leq n(j)})$ equals the description from (i), then we further more insist that $\hat{T}_j$ be that $n(j)$-$j+$-step down of $T_{j+}$. \leftskip 0in \medskip It is routine to see that we can do this in a recursive way, obtain a fixed point \[(\hat{T}_j)_{j\in X}=(T_j)_{j\in X},\] by the recursion theorem. The definitions immediately slot in to show that this fixed point is the unraveling we need once the following claim is verified. \medskip \noindent{\bf Claim:} If $\lambda\in$ lim$(X)$ and $\alpha_{n,\lambda}\leq_X j<_X\lambda$, then at all $(\bar{s}, t)\in \omega^{\leq n}\times \omega^{\leq n}$ we have \[(\bar{s}, t)\in T_j\] if and only if there exists some $s$ with $p_{(j,\lambda]_X}(s)=\bar{s}$ and \[(s, t)\in T_{\lambda}.\] \medskip \noindent {\bf Proof of claim:} We have \[\hat{T}_j\cap (\omega^{\leq n(j)}\times \omega^{\leq n(j)})\] equal to the set \[\{(p_{(j, \lambda]_X}(s), t): \exists \lambda\in \Lambda(j)\exists n\in \omega ((s, t)\in T_\lambda\cap(\omega^{\leq n}\times \omega^{\leq n}), \alpha_{n, \lambda}\leq_X j)\}.\] For a contradiction we consider some $(\bar{s}, t)\in T_j\cap \omega^{\leq n}\times \omega^{\leq n} $ with $\alpha_{n,\lambda}\leq_Xj<_X \lambda$ for which there is no associated $(s, t)\in T_\lambda$ with $p_{(j, \lambda]}(s)=\bar{s}$. Then by the definition of $\hat{T}_j$ we go to some $\lambda_1\in \Lambda(j)$ and $\alpha_{n_1, \lambda}\leq_Xj<_X \lambda_1$, $n_1\leq lh(\bar{s})$ and $s_1$ with $p_{(j, \lambda_1]_X}(s_1, t)=\bar{s}$, $(s_1, t)\in T_{\lambda_1}$. \medskip \noindent {\bf Subclaim:} $\lambda_1<_X\lambda$. \medskip \noindent {\bf Proof of subclaim:} Otherwise we have to have $\lambda\leq_X\lambda_1$, and then in fact $\lambda<_X \lambda_1$ since $(s_1, t)$ cannot be in $T_\lambda=\hat{T}_\lambda$ by assumption at the start of the claim. But then we would have $\lambda_1\in \Lambda(\lambda)$ in light of \[\alpha_{n_1, \lambda}\leq_Xj<_X \lambda<_X\lambda_1,\] and we would have to have $(p_{(\lambda, \lambda_1]_X}(s_1), t)\in \hat{T}_\lambda$, and then \[p_{(j, \lambda]_X}(p_{(\lambda, \lambda_1]_X}(s_1))=p_{(j, \lambda_1]_X}(s_1)=\bar{s}\] after all. \hfill ($\square$Subclaim) \medskip But now we still have $\lambda\in \Lambda(\lambda_1)$ and hence we repeat the process and find some $\lambda_2\in \Lambda(\lambda_1)$ and $\alpha_{n_2, \lambda}\leq_Xj<_X \lambda_2$, $n_2\geq lh(s_2)$, and $s_2$ with $p_{(j, \lambda_2]_X}(s_2, t)=\bar{s}$. The same reasoning as the last subclaim gives $\lambda_2<_X\lambda$, and so on. In the end of all this we have some strictly increasing sequence $(\lambda_k)_{k\in \omega}$ and corresponding $(\alpha_{n_k, \lambda_k})_{k\in \omega}$ with $\alpha_{n_{k+1}, \lambda_{k+1}}<_X\lambda_k$ at each $k$. If we let $\lambda_\infty$ be the limit of these $\lambda_k$'s then we obtain a contradiction to clause (d)(iii) of $(X, <_X)$ being a {\it suitable} linear order. \end{proof} \begin{lemma} \label{bigo} Let $(X, <_X)$ be a suitable recursive well order and let $(T_{\beta})_{\beta\in X}$ an unraveling. Then for all $\alpha\leq_X \beta$ we may find a corresponding bijection \[ [T_\beta]\rightarrow [T_\alpha]\] \[(y, x)\mapsto (\bar{y}, \hat{x}),\] such that: \leftskip 0.4in (i) $\bar{y}$ always equals $p_{(\alpha, \beta]_X}(y)$; (ii) $(\bar{y},\hat{x})$ is uniformly recursive in \[((p_{\beta}(y))', x, y);\] (iii) if $\beta$ is the $<_X$-successor of $\alpha$ then $(\bar{y}, \hat{x})'$ is uniformly recursive in $((\bar{y})', x, y)$. \leftskip 0in \end{lemma} \begin{proof} By induction on $\beta$ we define maps which work at the level of the nodes of the tree, \[\pi_{\bar{s}}^{\alpha, \beta} :\{(s, t)\in T_{\beta}: lh(s)=lh(t)\leq lh(\bar{s})\} \rightarrow \lo\] and in the end let $\hat{x}$ be the union over $k$ of \[{\rm lim}_{\ell\rightarrow \infty} \pi^{\alpha, \beta}_{\bar{y}|_\ell}(x|_k, y|_k).\] At successor steps we simply appeal to the definition of $\beta$ as the $n(\beta)$-$\beta$-step down of $T_{\beta+}$, and define the various $\pi^{\alpha, \beta+}_{\bar{s}}$'s from the corresponding $\pi^{\alpha, \beta}_{\bar{s}}$ and $\pi^{\beta, \beta+}_{\bar{s}'}$ for some appropriate choice of $\bar{s}'$. This will immediately give part (ii) of the lemma in light of \ref{3.6}. The heavy lifting occurs at the limit levels. So if $\lambda\in X$ is a limit and there are $\alpha_{n, \lambda}\rightarrow \lambda$ given by the suitable ordering $(X, <_X)$, then for $n\leq m$ and $(s, t)\in T_{\lambda}\times (\omega^{\leq n}\times \omega^{\leq n})$, and \[\bar{s}=p_{(\alpha, \lambda]_X}(s),\] \[\bar{s}'=p_{(\alpha_{n, \lambda}, \lambda]_X}(s),\] \[\bar{s}''=p_{(\alpha_{m, \lambda}, \lambda]_X}(s),\] and \[\alpha\leq_X \alpha_{n, \lambda} \leq_X\alpha_{m, \lambda}\leq_X\lambda\] we have \[\pi_{\bar{s}}^{\alpha, \alpha_{n,\lambda}}(\bar{s}', t) =\pi_{\bar{s}}^{\alpha, \alpha_{m, \lambda}}(\bar{s}'', t),\] by the inductive assumption and the definition of an unraveling. Thus we obtain a well defined function if we simply go ahead and choose {\it any} such $n$ and let \[\pi_{\bar{s}}^{\alpha, \lambda}(s, t) = \pi_{\bar{s}}^{\alpha, \alpha_{n,\lambda}}(\bar{s}', t).\] This can in fact be carried out in a uniformly recursive way, thereby giving part (i) of the lemma by \ref{3.5} and the comments which follow it. \end{proof} \begin{definition} For $(X, <_X)$ a recursive well order, $\beta\in X$, $y\in \oo$ or $y\subset\omega$, we let \[y^\beta\] be the result of iterating the jump operation relative to $y$ out along the initial segment of all elements in $X$ which are below $\beta$. For any such $X$ we fix a corresponding uniformly recursive in $X$ tree \[S_X\subset \lo\] such that $S_X$ has exactly one infinite branch \[y\in [S_X]\] and on the $\omega^{\rm th}$ copy\footnote{Again, as before, using our recursive pairing function $\rho:\omega\times\omega\rightarrow \omega$.} we have that $y$ equals\footnote{Up to some reasonable definition of the jump operator, as an element of $\oo$ Turing equivalent to one of the standard definitions from say \cite{odifreddi}.} \[0^\beta.\] We can and do additionally assume that this is done so that if $Y$ is an initial segment of $X$ then \[S_Y=\{P_{X\setminus Y}(s): s\in S_X\}.\] \end{definition} \begin{lemma} \label{hugo} Let $(X, <_X)$ be a suitable recursive well order of order type $\kappa +1$ and let $(T_{\beta})_{\beta\in X}$ be an unraveling with top most element $T=T_{j_0}$ having the property that its projection to the first coordinate gives back the tree to find $0^\kappa$ -- namely, \[\{s: \exists t((s,t)\in T) \}=S_X.\] Then for all $\alpha\leq_X \beta$ we may find a corresponding bijection \[ [T_\beta]\rightarrow [T_\alpha]\] \[(y, x)\mapsto (\bar{y}, \hat{x}),\] such that if $\hat{\kappa}$ is the order type of the interval $[\alpha, \beta)_X$ in $X$, then $(\bar{y},\hat{x})^{\hat{\kappa}}$ is uniformly recursive in $(y,x)$. \end{lemma} \begin{proof} By \ref{bigo} and repeated appeals to the definitions. \end{proof} \section{Application} \begin{definition} Let $\kappa<\omega_1^{\rm ck}$ be some recursive well order. A recursively enumerable downward closed $U\subset \lo\times\lo$ is said to admit a {\it $\kappa$-stack} if there is a recursively enumerable $T\subset \lo\times\lo$ such that \leftskip 0.4in \noindent (i) $[T]$ is uncountable; \noindent (ii) there is a $(X, <_X)$ be a suitable recursive well order and let $(T_{\beta})_{\beta\in X}$ be an unraveling with top most element $T=T_{j_0}$ and bottom most element $U$; \noindent (iii) \[\{s: \exists t((s,t)\in T) \}=S_X.\] \leftskip 0in \end{definition} \begin{lemma} \label{4.1} If $\hat{\kappa}<\kappa<\omega_1^{\rm ck}$ and $U$ admits a $\kappa$-stack, then it admits a $\hat{\kappa}$-stack. \end{lemma} \begin{proof} Immediate from the definitions. \end{proof} \begin{lemma} \label{4.2} The set of $U$ admitting a $\kappa$-stack is $\Sigma^1_1$. \end{lemma} \begin{proof} It follows from the perfect set theorem that the collection of trees with uncountably many branches is $\Sigma^1_1$. \end{proof} \begin{lemma} \label{4.3} For any $\kappa<\omega_1^{\rm ck}$ there is a recursively enumerable $U$ admitting a $\kappa$-stack. \end{lemma} \begin{proof} From \ref{3.8}. \end{proof} \begin{corollary} There is a recursively enumerable $U$ which has a $\kappa$-stack for every $\kappa<\omega_1^{\rm ck}$. \end{corollary} \begin{proof} Otherwise we obtain for every recursively enumerable $U$ a corresponding \[\kappa<\omega_1^{\rm ck}\] with the $\Pi^1_1$ property that there is no $\kappa$-stack. Thus by Kriesel uniformization\footnote{Some people also call this $\Pi^1_1$ uniformization for integers.} we can obtain a $\Delta^1_1$ function \[U\mapsto \kappa(U),\] from recursively enumerable downward closed subset of $\lo\times\lo$ to recursive ordinals, such that at each $U$ we have no $\kappa(U)$-stack for $U$. The collection of all such $\kappa(U)$'s is a $\Delta^1_1$ subset of $\omega_1^{\rm ck}$, and hence by boundedness there is some $\kappa_0$ such that at every $U$ \[\kappa(U)<\kappa_0.\] Thus by \ref{4.1} no recursively enumerable $U$ has a $\kappa_0$ stack, with a contradiction to \ref{4.2}. \end{proof} So let take such a $U$ which has arbitrarily long stacks and consider some arbitrary $(\bar{y}, \hat{x})\in [U]$. It follows from the definitions that $\bar{y}$ is recursive and at each $\kappa<\omega_1^{\rm ck}$ there is some $\kappa +1$-stack built over $U$, with top most element $T=T_{j_0}$, second top element $T_{j_1}$, which arises as the step down of $T_{j_0}$, and \[(y_0, x_0)\in T_{j_0},\] \[(y_1, x_1)\in T_{j_1},\] \[y_1=p_{j_0}(y_0),\] \[x_1=\pi_{y_1}(y_0, x_0),\] \[y_1\equiv_T 0^\kappa.\] From \ref{hugo} we get \[(\bar{y},\hat{x})^\kappa\leq_T(x_1, y_1).\] From \ref{3.7} we get that \[(y_1)'\equiv_T 0^{\kappa+1}\] is not recursive in $(y_1, x_1)$, and hence the $\kappa$-degree\footnote{Here by $\kappa$-degree I mean the Turing degree of the corresponding $\kappa^{\rm th}$ jump.} of $(\hat{y}, \hat{x})\equiv_T \hat{x}$ is not above $0^{\kappa +1}$. Thus we have found a recursively enumerable downward closed $U\subset\lo\times\lo$ with uncountably many branches, none of them having $\kappa$-degree above $0^{\kappa +1}$. It is then routine to reorganize this to obtain a {\it recursive} tree $\hat{U}$ with exactly the same infinite branches as $U$. To summarize, we have an uncountable $\Pi^0_1$ subset of $\oo$ which does not contain reals of arbitrarily high $\kappa$-degree for any $\kappa<\omega_1^{\rm ck}$, and thus provides a negative answer to 57* \cite{friedman}. \begin{thebibliography}{99} %\bibitem{beckerkechris} {\sc H. \ Becker} and %{\sc A.\ S. \ Kechris}, {\em The descriptive set theory %of Polish group actions}, %London Mathematical Society Lecture %Note Series, 232, Cambridge University Press, Cambridge, 1996. \bibitem{friedman} {\sc H. \ Friedman,} {\em One hundred and two problems in mathematical logic,} {\bf Journal of Symbolic Logic}, vol. 40(1975), pp. 113--129. \bibitem{harrington} {\sc L.A. \ Harrington,} {\em Arithmetically incomparable arithmetical singletons,} mimeographed notes, 1976. \bibitem{harrington1} {\sc L.A. \ Harrington,} {\em McLaughlin's conjecture,} mimeographed notes, 1976. \bibitem{odifreddi} {\sc P.G. Odifreddi}, {\bf Classical Recursion Theory, vol. I,} North-Holland, Amsterdam, 1989. \end{thebibliography} \leftskip 0.5in greg@math.ucla.edu \bigskip MSB 6363 UCLA CA 90095-1555 \leftskip 0in \end{document}