% 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'<m$, and there is $w\in B^{n+1}_{\bar{s}}$ 
with $lh(w)\leq lh(\bar{s}), w\supset v$, such that either: 

\leftskip 0.4in 

(1) $m'=2^e+i$, $R_1(\bar{s}^\smallfrown \bar{p}, w, e)$ holds, but 
$R_1(\bar{s}, v, e)$ fails; 

(2) $m'=3^{e+1}+i$, $R_2(\bar{s}^\smallfrown \bar{p}, w, e)$ holds, but 
$R_2(\bar{s}, v, e)$ fails. 


\leftskip 0in 

\end{notation} 

\smallskip 

This notation established we describe the injury case. 


\smallskip

If $\bar{s}^\smallfrown \bar{p}\in \tj(n+1)\setminus \tj(n)$, 
$(s, t)\in$ dom$(\pi^{n+1}_{\bar{s}})$, $\pi^{n+1}_{\bar{s}^\smallfrown \bar{p}}(s, t)
\neq \pi_{\bar{s}}^{n+1}(s, t)$, 
then there exists $\hat{s}\subset s, \hat{t}\subset t$, 
\[v=\pi^{n+1}_{\bar{s}}(\hat{s}, \hat{t})\in A^{n+1}_{\bar{s}, m}\] 
(some $m$) 
with $\langle \hat{s}, \hat{t}\rangle$ least for which there exists 
$m'$ with 
\[Q(\bar{s}^\smallfrown \bar{p}, v, m');\] 
moreover there is $w\in B^{n+1}_{\bar{s}}$, $w\supset v$, $lh(w)\leq lh(\bar{s})$ as 
above with either 
\[R_1(\bar{s}^\smallfrown \bar{p}, w, e)\] 
or 
\[R_2(\bar{s}^\smallfrown \bar{p}, w, e)\] 
(depending on whether $m'=2^e+i$ or $m'=3^{e+1}+i$), such that 
\[\pi^{n+1}_{\bar{s}^\smallfrown \bar{p}}(s', t')\supset w\] 
all $(s', t')\in$ dom$(\pi^{n+1}_{\bar{s}^\smallfrown \bar{p}})$, 
$s'\supset \hat{s}, t'\supset \hat{t}$, and such that 
\[w'\in A^{n+1}_{\bar{s}^\smallfrown \bar{p}, m'}\] 
all $w'\supset w$, $w'\in B^{n+1}_{\bar{s}^\smallfrown \bar{p}}$. 

\smallskip 

Moreover the conditions above are not only necessary for 
\[\pi^{n+1}_{\bar{s}^\smallfrown \bar{p}}(s, t)
\neq \pi_{\bar{s}}^{n+1}(s, t)\] 
but sufficient, in that if $\pi^{n+1}_{\bar{s}}(\hat{s}, \hat{t})
\subset \pi^{n+1}_{\bar{s}}(s, t)$ with $\langle\hat{s}, \hat{t}\rangle$ 
least such that $Q(\bar{s}^\smallfrown \bar{p}, \pi^{n+1}_{\bar{s}}(\hat{s}, \hat{t}), m')$ 
holding for some $m'$, then 
\[\pi^{n+1}_{\bar{s}^\smallfrown \bar{p}}(s, t)
\neq \pi_{\bar{s}}^{n+1}(s, t)\] 
and we define $\pi^{n+1}_{\bar{s}^\smallfrown \bar{p}}(\hat{s}, \hat{t})$ 
according to the least possible such $m'$. 



\end{definition} 


\begin{lemma} 
\label{3.1} 
For $T, i, j$ as above, an $i$-$j$-step down of $T$ exists. 
\end{lemma} 

\begin{proof} It suffices to show that given any choice of 
\[((A_{\bar{s}, m}^\ell)_{\bar{s}\in \tj(\ell), m\leq \ell})_{\ell\leq n}\] 
\[((\pi^\ell_{\bar{s}})_{\bar{s}\in \tj(\ell)})_{\ell\leq n}, \] 
satisfying (I) to (VII), 
we can extend to find the various $A_{\bar{s}, m}^{n+1}$ and $\pi^{n+1}_{\bar{s}}$ 
again fulfilling these conditions (I)-(VII). That is to say, it suffices to show 
{\it existence}, since by always choosing the first such choice in some canonical enumeration 
we obtain recursiveness for free. 

But to do this we first define these just for $\bar{s}\in \tj(n)$, fixing the 
various $\pi^{n+1}_{\bar{s}}$ according to the non-injury case at (VI) and only after 
we have first defined the $\pi^{n+1}_{\bar{s}^*}$ for all $\bar{s}^*$ which 
form proper initial segments of $\bar{s}$. The conditions at (I) and (II) represent 
minor bookkeeping tasks. (III) and (IV) simply require us to move the values of 
the form $(\pi^{n+1}_{\bar{s}}(s, t))(\ell)$ away from some prohibited finite set, and 
thus can always be achieved.
%\footnote{This is why we define the $\pi^n_{\bar{s}}$'s in the 
%peculiar way we do: They are always finite. We can always move away from values mentioned 
%earlier.} 

All the excitement occurs when we consider some new $\bar{s}^\smallfrown \bar{p}\in \tj(n+1)\setminus 
\tj(n)$. But in this case (VII) tells us exactly when an injury must occur, and if an injury takes 
place then we follow the specifications given there, making sure to avoid values prohibited by 
(III) and (IV). If no injury takes place, then it as in the previous paragraph. 
\end{proof} 

\begin{notation} From now on we let 
\[\pi_{\bar{s}}=\bigcup_{n\in\omega}\pi^n_{\bar{s}},\] 
\[A_{\bar{s}, m}=\bigcup_{n\in\omega} A^n_{\bar{s}, m},\] 
\[B_{\bar{s}, m}=\bigcup_{n\in\omega} B^n_{\bar{s}, m}.\] 
\end{notation}  

\begin{lemma} 
\label{lemma1} 
\label{3.2} 
Suppose 
\[\bar{y}\in \oo, \] 
\[(s, t)\in T,\] 
\[ lh(s)=lh(t), \] 
\[p_j(s)\subset \bar{y}.\] 
Then there is an $m_0\in \omega, v_0\in \lo$ such that for all sufficiently large 
$\ell$ 
\[\pi_{\bar{y}|_\ell}(s, t)=v_0\in A_{\bar{y}|_\ell, m_0}.\] 
\end{lemma} 

\begin{proof} 
By induction on $lh(s)=lh(t)$, with the base case of $lh(s)\leq i$ being handled by 
(V)(a) and the absence of any injury at these first few steps of the process. 

For the inductive step, passing from $(s, t)$ to $(s^\smallfrown p, t^\smallfrown q)$, we 
assume inductively that there is a last $\ell$ at which $\pi_{\bar{y}|_\ell} (s, t)$ is 
injured, and then argue that the same is true for the various $\pi_{\bar{y}|_\ell}
(s^\smallfrown p, t^\smallfrown q)$. The key point here is the upward persistence of 
$\Sigma^0_1$ facts: Once $\pi_{\bar{y}|_\ell}(s^\smallfrown p, t^\smallfrown q)$ has 
been injured because of some $m'$ at (VII), we never again can have 
$Q(\bar{s}, \pi_{\bar{y}|_\ell}(s^\smallfrown p, t^\smallfrown q), m')$ happening at 
any $\bar{s}\supset \pi_{\bar{y}|_\ell}$, and 
any further injury can only come from 
smaller $m''<m'$. Eventually these smaller $m''$ will likewise exhaust themselves, 
and the value of $\pi_{\bar{y}|_\ell}(s^\smallfrown p, t^\smallfrown q)$ dries into 
permanence. 
\end{proof} 

\begin{corollary} 
\label{3.3}  
\label{corollary1} 
If $(y, x)\in [T]$ then there exists $(\bar{y}, \hat{x})\in [U]$ 
with $\bar{y}=p_j(y)$ and for all $k$  and for all but finitely many $\ell$
\[\pi_{\bar{y}|_\ell}(y|_k, x|_k)\subset \hat{x}.\]  
\end{corollary} 

\begin{proof} 
From the lemma and clause (I) of the construction. 
\end{proof} 


\begin{lemma} 
\label{3.4}  
For $(x, y), (\bar{y}, \hat{x})$ as above, there exist arbitrarily large $m$ for 
which there is some $k$ such that 
\[\forall^\infty \ell(\pi_{\bar{y}|_\ell}(x|_k, y|_k)\in A_{\bar{y}|_\ell, m}).\] 
\end{lemma} 

\begin{proof} 
As in the proof of \ref{lemma1}. 
\end{proof} 

\begin{lemma} 
\label{3.5} 
If $(\bar{y}, \hat{x})\in [U]$ then there is $(y, x)\in [T]$ such that 
\[p_j(y)=\bar{y}\] 
and at every $k$ 
\[\forall^\infty \ell (\pi_{\bar{y}|_\ell}(y|_k, x|_k)\subset \hat{x}).\] 
\end{lemma} 

\begin{proof} 

\medskip 

\noindent{\bf Claim(1):} There are $(\hat{s}, \hat{t})\in (\omega^{i+1})^2$ 
such that for all but finitely many $\ell$ 
\[\pi_{\bar{y}|_\ell}(\hat{s}, \hat{t})\subset \hat{x},\] 
\[\forall s', t'(\pi_{\bar{y}|_\ell}(s', t')\supset \hat{x}|_{i+1}
\Rightarrow s'\supset \hat{s}, t'\supset \hat{t}).\] 

\medskip 

\noindent{\bf Proof of Claim:} 
Go to the first $\ell$ for which there is 
$\hat{s}=s^\smallfrown p, \hat{t}=t^\smallfrown q$ with 
\[\pi_{\bar{y}|_\ell}(\hat{s}, \hat{t})|_{i+1}=\hat{x}|_{i+1}.\] 
Since $(s, t)\in (\omega^i)^2$, $\pi_{\bar{y}|_\ell}(s, t)$ is 
never injured, it follows from (III) that we get at any $\ell'\geq \ell$ 
\[\forall s', t'(\pi_{\bar{y}|_{\ell'}}(s', t')\supset \hat{x}|_{i+1}
\Rightarrow s'\supset \hat{s}, t'\supset \hat{t}).\] 
After this $(\bar{y}, \hat{x})\in [U]$ necessitates 
\[\pi_{\bar{y}|_{\ell'}}(\hat{s}, \hat{t})\subset \hat{x}.\] 
\hfill ($\square$Claim) 


\medskip 

Now let us assume inductively that there is some $(s, t)$, $N$, $m$, and $v$, with 
$lh(v)>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}



