 
% LaTeX Article Template - using defaults
\documentclass{article}[12pt]

\usepackage{amssymb}
\usepackage{latexsym}
%\pagestyle{myheadings}
\markright{G. Hjorth}



\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}



\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{fact}

    \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\F{{\mathbb F}} 
\def\Q{{\mathbb Q}}
\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\co{{\mathcal O}}
\def\t{{\mathcal T}}
\def\c{{\mathcal C}}

\author{Greg Hjorth} 

\title{Glimm-Effros for coanalytic equivalence relations} 



\maketitle 

\abstract{Assuming every real has a sharp, 
we prove that for any $\Ubf{\Pi}^1_1$ equivalence relation either Borel reduces 
$E_0$ or in a $\Ubf{\Delta}^1_3$ manner allows the assignment of bounded subsets of 
$\omega_1$ as complete invariants.} 

\section{Summary} 

The study of equivalence relations has become a topical area in descriptive set theory. 

Within this area certain directions have been emphasized ahead of others. Perhaps the majority 
of the papers concern themselves solely with 
Borel equivalence relations, and naturally enough since the study of Borel equivalence relations 
connects with areas of concern entirely outside logic. Here one overwhelming theorem casts its shadow 
across the entire field. 

\begin{theorem} (Harrington-Kechris-Louveau) Let $E$ be a Borel equivalence relation. Then exactly 
one of the following two options hold:  

\leftskip 0.4in 

\noindent (I) $E_0\leq_B E$ -- in other words there is a Borel function $f$ from $2^\N$ to the space on which $E$ is defined such that for all $x, y\in 2^\N$ 
\[\exists N\forall m>N (x(m)=y(m))\Leftrightarrow f(x) E f(y);\] 

\noindent (II) $E\leq_B {\rm id}(\R)$ -- in other words there is a Borel function from the space on 
which $E$ is defined to $\R$ such that 
\[x E y\Leftrightarrow f(x)=f(y).\] 

\leftskip 0in 

\end{theorem} 

This is sometimes known as the {\it Glimm-Effros} dichotomy on account precursors being proved by Glimm and then later Effros. 



Among the study of non-Borel equivalence relations, two dichotomy theorems are especially note worthy: 

\begin{theorem} (Silver) Let $E$ be a $\Ubf{\Pi}^1_1$ equivalence relation. Then either $E$ has countably many equivalence classes or there is a perfect set of $E$-inequivalent points. 

\end{theorem} 

\begin{theorem} (Burgess) Let $E$ be a $\Ubf{\Sigma}^1_1$ equivalence relation. Then either 
$E$ has at most $\aleph_1$ many equivalence classes or there is a perfect set of $E$-inequivalent 
reals. 
\end{theorem} 

As one moves up the projective hierarchy, the analogues of these theorems have been intensively investigated under determinacy assumptions.  Kechris showed that appropriate bound for $\Ubf{\Sigma}^1_2$ equivalence relations is $\aleph_1$, and it follows from \cite{harringtonshelah} 
that for $\Ubf{\Pi}^1_2$ we get the same. The results for the first two levels of the projective 
heirarchy then generalize in line with the periodicity 
theorems of \cite{moschovakis}. This all echoes the computations of the projective ordinals in 
$L(\R)$ , as found in \cite{jackson}, \cite{moschovakis}, and therefore is hardly discordant with the 
concerns of modern set theory. 

Little serious concern has been directed towards the 
appropriate versions of Glimm-Effros at higher levels of the projective hierarchy. 
Even granting the close connections of higher versions of Silver's theorem with the traditional concerns 
of set theorists, this should be viewed as surprising. 

For the purpose of discussion let us assume that AD, the axiom of determinacy, holds inside $L(\R)$. Let us write $|A|_{L(\R)}$ for the {\it ZF-cardinality} of the set $A$ inside $L(\R)$ -- thus $|A|_{L(\R)}
\leq |B|_{L(\R)}$ if there is an injection inside $L(\R)$ from $A$ to $B$. 

Here it turns out that Harrington-Kechris-Louveau provides a theorem about the cardinal structure of 
$L(\R)$. 

\begin{theorem} (Harrington-Kechris-Louveau, in effect; assume $AD^{L(\R)}$) Let $E$ be a Borel equivalence relation on $\R$. Then exactly one of: 

\leftskip 0.4in 

\noindent (I) $|{\cal P}(\N)/ {\rm Fin}|_{L(\R)}\leq |\R/E|_{L(\R)}$; 

\noindent (II) $|\R/E|_{L(\R)}\leq |\R|_{L(\R)}$. 

\leftskip 0in 

\end{theorem} 

There is an analog for the pure cardinal theory of $L(\R)$: 

\begin{theorem}   (Hjorth; assume $AD^{L(\R)}$). 
Let $A\in L(\R)$. Then exactly one of: 

\leftskip 0.4in 

\noindent (I) $|{\cal P}(\N)/ {\rm Fin}|_{L(\R)}\leq |A|_{L(\R)}$; 

\noindent (II) for some ordinal $\alpha$, $|A|_{L(\R)}\leq |{\cal P}(\alpha)|_{L(\R)}$. 

\leftskip 0in 

\end{theorem} 

The purpose of this paper is to take one step towards filling in the gaps between these two extremes. Given a Wadge class $\Gamma$, we would like to know the version of (II) which serves for 
equivalence relations $E\in \Gamma$. The contribution of this paper is towards understanding 
$\Ubf{\Pi}^1_1$. 

\begin{theorem}  \label{pi} Assume every real has a sharp. 
Let $E$ be a $\Ubf{\Pi}^1_1$ equivalence relation. Then either: 

(I) $E_0\leq_B E$; or 

(II) there is a $\Ubf{\Delta}^1_3$ in the codes assignment of bounded subsets of $\omega_1$ as 
complete invariants to the equivalence classes. 

\end{theorem}  




As a key step along the way we prove a general dichotomy theorem using the ideas of 
\cite{harringtonshelah} to adapt the basic argument of 
\cite{hakelo}. This hitherto overlooked results can be used to prove the 
Glimm-Effros dichotomy theorems of \cite{ditzen} and \cite{foreman}. Note that this theorem is 
proved {\it without appeal} to the axiom of choice. 


\def\bt{{\bar T}} 

\begin{theorem} (ZF) \label{hsversion} 
Let $\kappa$ be an infinite cardinal.  Let $T, \bar{T}\subset (\kappa \times \omega\times \omega)^{<\omega}$ be 
trees. Assume: 

\leftskip 0.4in 


\noindent (i) $p[T]=(\omega^\omega\times \omega^\omega)\setminus p[\bt]=E$; 

\noindent (ii) $p[\bt]$ continues to define the complement of an equivalence relation even after we add a Cohen real. 

\leftskip 0in 

\noindent Then either: 

\leftskip 0.4in 

\noindent (I) $E_0\leq_B E$; or, 

\noindent (II) there is 
\[U: \omega^\omega\rightarrow {\cal P}(\kappa)\] 
such that for all $x, y\in \omega^\omega$, 
\[xEy \Leftrightarrow U(x) = U(y).\] 

\leftskip 0in 

\end{theorem} 

It should be mentioned that \cite{hjorthkechrisulm} proves an identical theorem to 
\ref{pi} for $\Ubf{\Sigma}^1_1$ equivalence relations under the assumption of sharps, or 
equivalently, $\Ubf{\Sigma}^1_1$ determinacy. In all honesty I should say that I have more 
cause for sorrow here than triumph, since it seems plausible that a result along these lines 
should be true for $\Ubf{\Delta}^1_2$ equivalence relations under suitable determinacy 
assumptions, and I have no inkling how this could be proved. 

\section{Definitions and background} 

We assume the reader is familiar with the basic set theoretical notions forcing and constructibility, 
as can be found in \cite{jech}, along with some of the touch stones of modern descriptive set theory, 
such as tree,  
as can be found in \cite{moschovakis}. We recall some of the concepts from the descriptive set theory 
of equivalence relations. 
Infinitary logic, admissible sets, and Barwise compactness provide a driving force through much of the arguments;  while 
\cite{keisler} provides an excellent reference, these notions fall slightly outside the traditional purview of 
set theory and are therefore summarized below. 

\subsection{The descriptive set theory of equivalence relations} 

Although this paper is more properly considered a work of higher set theory than 
the classical set theory of say \cite{hjorthkechris}, the notion of 
{\it Borel reducibility} is still salient. 

\begin{definition} Given $E, F$ on Polish spaces $X, Y$, we say that $E$ is {\it Borel 
reducible to} $F$, 
\[E\leq_B F,\] 
if there is a Borel function 
\[f: X\rightarrow Y\] 
such that for all $x_1, x_2\in X$ 
\[x_1 E x_2 \Leftrightarrow f(x_1) F f(x_2).\] 
\end{definition} 

\begin{definition} For $X$ a Polish space we use id$(X)$ to denote the identity 
equivalence relation on $X$ -- $\{(x, x): x\in X\}$. $E_0$ denotes the equivalence relation of 
eventual agreement on infinite binary sequences: 
\[x E_0 y\Leftrightarrow \forall^\infty n (x(n)=y(n)).\] 
\end{definition} 

Here we have id$(2^\omega)<_B E_0$ -- that is to say, there is a Borel reduction from the first to 
the second, but not the other way. 


\begin{definition} For $E$ an equivalence relation on a set $X$ and 
$x\in X$ we use $[x]_E$ to denote the $E$-equivalence class of $x$. We use 
$X/E$ to denote the collection of all $E$-equivalence classes. 
\end{definition} 

\begin{definition} Let $\Gamma$ be a point class, in the sense of \cite{moschovakis}. We say that an 
equivalence relation $E$ on a space $X$ 
admits a $\Gamma$ {\it in the codes assignment of elements of 
$2^{<\omega_1}$ as complete invariants} if there is a function 
\[f: X\rightarrow (2^{\omega\times\omega}, 2^\omega)\] 
in $\Gamma$ along with an injection 
\[\hat{f}: X/E\hookrightarrow 2^{<\omega_1}\] 
such that for all $x\in X$ with $h=\hat{f}([x]_E)\in 2^\alpha$ and $(a, b)=f(x)$ we 
have 
\[(\alpha; \{\beta: h(\beta)=1\}, \in)\cong 
(\omega; \{n: b(n)=1\}, \{(n, m): a(n, m)=1\}   ).\] 
\end{definition} 



\subsection{Infinitary logic} 

The reader should consult \cite{keisler} or \cite{barwise}. This subsection is the 
skeleton sketch. 

\begin{definition} Given a propositional 
language $\l$ we use $\l_{\infty, 0}$ to to denote the result of closing the class of 
propositions under negation as well as conjunctions and disjunctions of arbitrary 
size. 
\end{definition} 

Infinitary logic differs  from traditional first order logic in that the notions 
of proof theoretical and semantical consistency diverge. We clarify the meaning 
that {\it consistency} will take for this paper. 

\begin{definition} A proposition $\psi\in \l_{\infty, 0}$ is 
{\it consistent} if in some generic extension there exists a model for $\psi$. 
\end{definition} 

It is an easy absoluteness argument to see that any two transitive models satisfying a sufficiently 
large fragment of ZFC in 
which $\psi$ is hereditarily countable will agree as to whether it has a model. 
Thus consistency is $\Delta_1$ in the Levy hierarchy. 

For later purposes we need a sharper result: Consistency in our sense is 
uniformly $\Pi_1$ over any admissible structure containing $\psi$. This involves 
a game theoretical explication, where we have in mind the kind of infinite length games 
found in \cite{moschovakis}. 

\begin{definition} For $\psi\in \l_{\infty, 0}$ let $F_\psi\subset \l_{\infty, 0}$ be the fragment 
generated by $\psi$. Let $G_{\psi}$ be the following closed\footnote{Here {\it closed} 
is in the sense of \cite{moschovakis}} game of length 
$\omega$: I and II alternate playing elements of $F_\psi$. II can play 
any element at all of $F_\psi$, but I's moves are tightly constrained, and if I is ever unable to make a 
legal move then II wins. 

\leftskip 0.4in 

\noindent (0) I must begin with the move $\psi$; 

\noindent (i) if II plays $\phi\vee \neg\phi$, then I must at the next turn play $\phi$ or 
$\neg\phi$; 

\noindent (ii) if I has previously played $\bigwedge_{\alpha}\phi_{\alpha}$ and II plays some 
$\phi_{\beta}$, then I must immediately respond with $\phi_\beta$; 

\noindent (iii) if I has previously played $\bigvee_{\alpha}\phi_\alpha$ and II plays 
$\bigvee_\alpha \phi_\alpha$ then I must respond with some $\phi_\beta$; 

\noindent (iv) if I has previously played $\neg \bigwedge_{\alpha}\phi_{\alpha}$ and II plays 
$\neg \bigwedge_{\alpha}\phi_{\alpha}$ then I must respond with 
$\bigvee_\alpha \neg\phi_\alpha$; 

\noindent (v) if I has previously played $\neg \bigvee_{\alpha}\phi_{\alpha}$ and II plays 
$\neg \bigvee_{\alpha}\phi_{\alpha}$ then I must respond with 
$\bigwedge_\alpha \neg\phi_\alpha$; 

\noindent (vi) if I has previously played $\neg\neg \phi$ and II plays $\neg\neg\phi$, then 
I must play $\phi$; 

\noindent (vi) at no stage can two of I's previous moves consist at one move in $\phi$ and 
at another move $\neg \phi$. 

\leftskip 0in 

II wins if I is ever unable to make a next move in accordance with these requirements. I wins 
if the game keeps going for infinitely many turns. 

\end{definition} 

One should think of this game as a interrogation between II and I. I begins by asserting $\psi$, and 
then II steadily asks questions about how I might imagine a model of this proposition to be formed. 
I wins if the story continues indefinitely without contradiction; II wins if I's account is shown at some stage 
to be absurd. 

The next couple of lemmas are well known and standard. 

\begin{lemma} \label{countable} 
Let $\psi, G_\psi$ be as above. Assume $\psi$ is hereditarily countable. 

Then $\psi$ has a model if and only if I wins $G_\psi$. 
\end{lemma} 

\begin{proof} (Sketch) 
First assume that $\psi$ has a model. Then I wins by simply by responding to each of II's ``questions" 
with the answer found in the model. 

Conversely, let I have a winning strategy in $G_\psi$. Our assumptions give that $F_\psi$ is 
countable, and so we can let II make a maximal play which mentions every element of 
$F_\psi$ infinitely often. We take the model which consists of the collection of atomic propositions 
asserted at some stage by I. It is then a routine induction on logical complexity to show that this model 
satisfies some $\phi\in F_\psi$ if and only if I has at some point played $\psi$. 
\end{proof} 


\begin{lemma} \label{rank} 
Let $P_\psi$ be the collection of legal positions in the game 
$G_\psi$. Then I wins if and only if there is no 
\[\pi: P_\psi\rightarrow \gamma\cup\{\infty\},\] 
for some ordinal $\gamma$, such that at each position $p\in P$: 

\leftskip 0.4in 

\noindent (i) if I is to move then $\pi(p)={\rm sup} \{\pi(p^\smallfrown \phi): 
p^\smallfrown \phi \in P_\psi\}$; 

\noindent (ii) if II is to move then $\pi(p)={\rm inf}\{ \pi(p^\smallfrown \phi) +1: 
\phi \in F_\psi\}$; 

\noindent (iii) $\pi(\langle \phi\rangle)\neq \infty$. 

\leftskip 0in 

\end{lemma} 

\begin{proof} (Sketch) First suppose we have such function $\pi: P_\psi\rightarrow \gamma$. 
Note that our assumptions (i) and (ii) give $\pi(p)=0$ if and only if it is I's turn to move and there 
is no legal move to be made. Thus II can fashion a winning strategy by driving the ordinal down 
until it hits zero. 

Conversely, let us just attempt to define by induction $\pi$ with the initial requirement that 
$\pi(p)=0$ if it is I's move and there is no legal response, and then recursively continuing with 
 

\leftskip 0.4in 

\noindent (i) if I is to move then $\pi(p)={\rm sup} \{\pi(p^\smallfrown \phi): 
\p^\smallfrown \phi \in P_\psi\}$ provided all such $\pi(p^\smallfrown \phi)$ have been 
given ordinal values; 

\noindent (ii) if II is to move then $\pi(p)={\rm inf}\{ \pi(p^\smallfrown \phi) +1: 
\phi \in F_\psi\}$ provided at least one such $\pi(p^\smallfrown\phi)$ has been given an 
ordinal value. 

\leftskip 0in 

We spare the reader the details of how one formalizes such a transfinite 
recursion. It is a standard set theoretical construction; at stage $\alpha$ we will have 
defined $\pi^{-1}[\alpha +1]=\{p: \pi(p)\leq \alpha\}$. 

Once this has been continued as far as it will permit, we set $\pi(p)=\infty$ if $p$ has 
not previously been assigned an ordinal value. By assumption, $\pi(\langle \psi \rangle)
=\infty$, and I's winning strategy is to always play to keep $\pi(p)=\infty$. 
\end{proof} 

\begin{lemma} \label{admissible} 
There is a $\Pi_1$ formula $\Phi$ such that for any $\psi\in \l_{\infty, 0}$ and 
admissible $\m$ containing $\psi$, 
\[\m\models \Phi(\psi)\] 
if and only if $\psi$ is consistent. 
\end{lemma} 

\begin{proof} (Sketch) By \ref{countable}, it suffices to see I winning $G_\psi$ is uniformly $\Pi_1$ 
over $\m$, and this in turn follows from the proof of \ref{rank}. Inside the admissible we can 
recursively define 
\[\alpha\mapsto \pi^{-1}[\alpha +1]\] 
using the description from before. 
This will be a $\Delta_1$ recursion, and hence defined by a $\Delta_1$ formula 
over $\m$, and hence total and calculated the same in $\m$ as in $V$. 
It is a routine application of admissibility to see that $\pi(p)=\infty$ if and only 
if there is no $\alpha\in \m$ with $\pi(p)=\alpha$, and this statement itself is $\Pi_1$ over 
$\m$. 
\end{proof} 


\begin{notation} A set is $\Ubf{\Sigma}_1$ over a structure $\m$ if there is some $\Sigma_0$ 
formula $\Psi$ and some $a\in \m$ such that $A$ equals the set of $b\in \m$ such that 
\[\m\models\exists x_1\exists x_2...\exists x_n \Psi(a, b, x_1,...x_n).\] 
\end{notation} 

\begin{lemma} \label{barwise} 
Let $\m$ be admissible and $T\subset \l_{\infty, 0}\cap \m$ be  $\Ubf{\Sigma}_1$ over $\m$. 
Suppose that every $X\in \m$ with $X\subset T$ is consistent. 

Then $T$ is consistent. 
\end{lemma} 

\begin{proof} 
Since our definition of consistency is absolute between generic extensions, we may assume 
$\m$ countable; then the lemma just reduces to the usual statement of Barwise compactness. 

Alternately we can give a direct game theoretic proof, where the strategy of the first player is to 
always maintain that the run of moves so far along with $T$ preserves the property that any 
subset inside $\m$ is consistent in our sense. Using that inconsistency is $\Sigma_1$, the usual 
proof of Barwise carries through without tearing. 
\end{proof} 



\begin{lemma} \label{craig} 
Let $\l, \l', \l''$ be non-empty languages with $\l=\l'\cap \l''$. Let $\phi'\in \l'_{\infty, 0}, 
\phi''\in \l''_{\infty, 0}$ with $\phi'\Rightarrow \phi''$. 
Then there is $\phi\in \l_{\infty, 0}$ with 
\[\phi'\Rightarrow \phi\Rightarrow \phi''\]  
(i.e. $\phi'\wedge \neg\phi$ and $\phi\wedge\neg\phi''$ are both 
inconsistent). 
\end{lemma} 

\begin{proof} (Sketch) 
Suppose instead there is no such interpolant. 

We define a game $G_{\phi', \neg\phi''}$, a variant of $G_\psi$ given earlier. 
At each turn II can plays some $\tau'\in \l'_{\infty,0}$ and some $\tau''\in \l''_{\infty, 0}$. 
I then responds with some $\sigma'\in \l'_{\infty, 0}$ and some $\sigma''\in \l''_{\infty, 0}$. 
Again we stay inside the fragments generated by $\phi', \phi''$. In analogy to before, 
I begins with $\phi', \neg\phi''$. The conditions (i)-(vi) are transplanted in the obvious 
way:- 

\leftskip 0.4in 

\noindent (i') if $\tau'=\phi\vee \neg\phi$, then I must at the next turn play $\phi$ or 
$\neg\phi$; 

\noindent (ii') if I has previously played $\bigwedge_{\alpha}\phi_{\alpha}$ and 
$\tau'=\phi_{\beta}$, then I must immediately respond with $\sigma'=\phi_\beta$; 

\noindent (iii') if I has previously played $\bigvee_{\alpha}\phi_\alpha$ and $\tau'= 
\bigvee_\alpha \phi_\alpha$ then I must respond with some $\phi_\beta=\sigma'$; 

\noindent (iv') if I has previously played $\neg \bigwedge_{\alpha}\phi_{\alpha}$ and$\tau'=\neg \bigwedge_{\alpha}\phi_{\alpha}$ then I must respond with 
$\sigma'=\bigvee_\alpha \neg\phi_\alpha$; 

\noindent (v') if I has previously played $\neg \bigvee_{\alpha}\phi_{\alpha}$ and $\tau'=\neg \bigvee_{\alpha}\phi_{\alpha}$ then I must respond with 
$\sigma' \bigwedge_\alpha \neg\phi_\alpha$; 

\noindent (vi') if I has previously played $\neg\neg \phi$ and II plays $\tau'=\neg\neg\phi$, then 
I must play $\sigma'=\phi$. 

\leftskip 0in 

Similarly there will conditions (i'')-(vi'') which have $\tau''$ for $\tau'$ and 
$\sigma''$ for $\sigma'$. 

(vii) now becomes the requirement that in the union of all the moves played by I, all the $\tau'$'s and 
$\tau''$'s, there is no outright contradiction. 

Here one can adapt the usual proof of the Craig interpolation theorem to show the 
existence of a winning strategy for the first player: I just maintains that 
if $\rho'$ is the conjunction of the propositions in $\l'_{\infty, 0}$ asserted by I and 
$\rho''$ is the conjunction of the propositions in $\l''_{\infty, 0}$ asserted by I, then there is 
no $\rho\in \l_{\infty, 0}$ such that 
\[\rho'\Rightarrow \rho\Rightarrow \neg\rho''.\] 

We then go to a generic extension in which $\phi',\phi''$ are hereditarily countable. We let 
II run the complete play, asking every question in the respective fragments infinitely often. 
We get a model of $\l'\cup\l''$, since there is no disagreement 
on the common parts of the language, by setting $\m\models \psi$, for $\psi$ an atomic 
proposition, if at some point in I's play $\psi$ appears. Following the proof of 
\ref{countable} we get 
\[\m\models \phi', \neg\phi'',\] 
with a contradiction to the hypotheses of the lemma. 
\end{proof} 

Note for future references that the proof of the last lemma actually gives an interpolant 
in any admissible structure $\m$ containing $\phi'$ and $\phi''$: The point is that we can adapt 
(vii) to be the requirement that there be no interpolant {\it in} $\m$. Note moreover from 
\ref{admissible} we have that there is a $\Sigma_1$ formula, $\Psi$, such that 
\[\m\models \Psi(\phi', \phi'', \phi)\] 
if and only if $\phi$ is an interpolant between $\phi'$ and $\phi''$. 

\section{Adapting Harrington-Shelah} 

We adapt the framework of \cite{harringtonshelah} to the combinatorics of 
\cite{hakelo}. 

\begin{definition} We let $\l^x$ be the propositional language consisting of basic propositions 
$\{p_n^x: n\in \omega\}$. For $a\in 2^\omega$ we define the $\l^x$ model $\m_a$ by setting 
\[\m_a\models p_n^x\] 
if and only if $a(n)=1$. The natural extension then is for 
$\varphi \in \l^x_{\infty, 0}$ we set 
\[a\models \varphi\] 
if $\m_a\models \varphi$. 
\end{definition} 

There are similar definitions to come, building on this kind of methodology in a way that is 
initially confusing to describe formally. We can at least pause to state the main result in a way that is 
completely precise, and much more revealing than the statement at \ref{hsversion}: 


\begin{theorem} (ZF) \label{hsprecise} 
Let $\kappa$ be an infinite cardinal.  Let $T, \bar{T}\subset (\omega\times \omega
\times\kappa)^{<\omega}$ be 
trees. Let $\gamma>\kappa$ be such that $L_{\gamma}[T, \bar{T}]$ is 
admissible. Assume: 

\leftskip 0.4in 


\noindent (i) $p[T]=(\omega^\omega\times \omega^\omega)\setminus p[\bt]=E$; 

\noindent (ii) $p[\bt]$ continues to define the complement of an equivalence relation even after we add a Cohen real. 

\leftskip 0in 

\noindent Then either: 

\leftskip 0.4in 

\noindent (I) $E_0\leq_B E$; or, 

\noindent (II) in every generic extension 
and every $a, b\in 2^\omega$ which are $E$-inequivalent there is some 
\[\varphi\in \l^x_{0, \infty} \cap L_\gamma[T, \bar{T}]\] 
such that 
\[a\models \varphi,\] 
\[b\models \neg\varphi,\] 
and in no other generic extension does there exist $c, d\in 2^\omega, f\in \kappa^\omega$ with 
\[c\models \varphi,\] 
\[d\models \neg\varphi,\] 
\[(a, b, f)\in [T].\] 


\leftskip 0in 

\end{theorem} 


In other words, if $E_0$ does not embed into $E$, then we may find find infinitary formulas in the least admissible containing the trees $T$ and $\bt$ which are in some absolute sense $E$-invariant and serve to separate distinct $E$  classes. 

\ref{hsversion} follows \ref{hsprecise} as a corollary: We can take $\gamma$ to have the same size as 
$\kappa$, so that there are only $\kappa$ many infinitary formulas in the admissible. We let 
$(\phi_\alpha)_{\alpha\in \kappa}$ be $\l^x_{\infty, 0}\cap L_\gamma[T, \bt]$. We let $U(a)$ be the set of all $\alpha<\kappa$ such that 
\[a\models \phi_\alpha\] 
and $\{b: b\models \phi_\alpha\}$ is $E$-invariant. 

More definitions. More of the same. We will need other propositional languages to talk about more than one real simultaneously and more than one attempt to witness a pair of reals is in $p[T]$ or 
$p[\bt]$. 



\begin{definition} We let $\l^y, \l^z$ be the propositional languages consisting of basic propositions 
$\{p_n^y: n\in \omega\}$, $\{p_n^z: n\in \omega\}$ respectively. For $a\in 2^\omega$ we define the $\l^y$ model $\m_a^y$ by setting 
\[\m_a\models p_n^y\] 
if and only if $a(n)=1$. The natural extension then is for 
$\varphi \in \l^y_{\infty, 0}$ we set 
\[a\models \varphi\] 
if $\m^y_a\models \varphi$. Similarly for $\m^z_a$ and $\varphi\in \l^z_{\infty, 0}$. 
Given $\varphi\in \l^x_{\infty, 0}$ we define $\varphi(y)$ and $\varphi(z)$ by replacing all 
appearances of $p^x_n$ by $p^y_n$ and $p^z_n$ respectively. We then go on and make the 
same kinds of substitutions for $\varphi\in \l^y_{\infty, 0}$ and 
$\varphi(x)$ and $\varphi(z)$ or $\varphi\in \l^z_{\infty, 0}$ and 
$\varphi(x)$ and $\varphi(y)$. 
\end{definition} 

So much for the reals themselves. We also need to ground a similar notation for witnesses to being in 
$E$ and its complement. From now on fix $T$ $\bt$ as in the statement of the 
\ref{hsprecise}. Let $\gamma>\kappa$ be such that 
\[L_\gamma[T, \bt]\] 
is admissible. 
We can also make a helpful technical assumption on $T$, with the consequence that it 
projects to an equivalence relation in all generic extensions. 

Note first of all that given $T$ there are canonical trees $T^2$ and $rT$ which project to 
the sets $\{(a_1, a_3): \exists a_2 ((a_1, a_2), (a_2, a_3)\in p[T]\}$ and 
$\{(b, a): (a, b)\in p[T]\}$. I will assume that these canonical trees appear as isomorphic copies inside 
$T$. 

First one defines $rT$ to be $\{(u, v, w): (v, u, w)\in T\}$, and then we replace $T$ by the 
disjoint union of 
$T$ and $rT$. 

 Then we define $T^m$ to be the set of 
$(u, v, w)\in 2^n\times 2^n\times \kappa^n$, $n\in\omega$, such that 
\[ (u,  \langle (w)_{0, 0, 0}, (w)_{0,0, 1},..(w)_{0, 0, n-1}\rangle, \langle (w)_{0, 1, 0},...(w)_{0, 1, n-1}
\rangle)\in T,\] 
\[  (\langle (w)_{0, 0, 0}, (w)_{0,0, 1},..(w)_{0, 0, n-1}\rangle, \langle (w)_{1, 0, 0},...(w)_{1, 1, n-1}
\rangle, \langle  (w)_{1, 1, 0},...(w)_{1, 1, n-1}
\rangle) \in T,\] 
\[...\]
\[  (\langle (w)_{m-1, 0, 0},..(w)_{m-1, 0, n-1}\rangle, v, \langle  (w)_{m-1, 1, 0},...v_{m-1, 1, n-1}
\rangle) \in T,\] 
where 
\[(\alpha, i, j, k)\rightarrow (\alpha)_{i, j, k}\] 
\[\kappa\times \omega\times\omega\times \omega\hookrightarrow \kappa\] 
is an injection provided by G\"{o}del coding. 
Then we replace $T$ by the disjoint union of the $T^m$'s. 

We may similarly assume that in all generic extensions $p[\bt]$ is symmetric. We may also 
fold in to $\bt$ suitable concatenations of $T$ and $\bt$ so 
that in any extension if $(a, b)\in p[T]$ and $(b, c)\in p[\bt]$, then $(a, c)\in p[\bt]$. 



\begin{definition} We let $\l^{x, z, r}$ be the propositional language with 
\[\{p_n^x: n\in \omega\}, \{p_n^z: n\in \omega\}, 
\{p_{r(n)=\alpha}: n\in \omega, \alpha\in \kappa\}.\]  For $a, b\in 2^\omega$, 
$f\in \kappa^\omega$ we define 
\[\m_{a, b, f}^{x, z, r}\] 
by setting $p_n^x$ true if $a(n)=1$, $p_n^z$ true if $b(n)=1$, and 
$p_{r(n)=\alpha}$ if $f(n)=\alpha$. As before, 
\[(a, b, f)\models \varphi\] 
if 
\[\m_{a, b, f}^{x, z, r}\models \varphi.\] 


Similarly we let 
$\l^{y, z, s}$ be the propositional language with 
\[\{p_n^y: n\in \omega\}, \{p_n^z: n\in \omega\}, 
\{p_{s(n)=\alpha}: n\in \omega, \alpha\in \kappa\}.\]  For $a, b\in 2^\omega$, 
$f\in \kappa^\omega$ we define 
\[\m_{a, b, f}^{y, z, s}\] 
by setting $p_n^y$ if $a(n)=1$, $p_n^z$  if $b(n)=1$, and 
$p_{s(n)=\alpha}$ if $f(n)=\alpha$. Again, 
\[(a, b, f)\models \varphi\] 
if 
\[\m_{a, b, f}^{y, z, s}\models \varphi.\] 

For $\varphi\in \l^{x, z, r}$ we define $\varphi(y, z, s)$ by replacing appearances of 
$p^x_n$ by $p^y_n$, $p_{r(n)=\alpha}$ by $p_{s(n)=\alpha}$. 
\end{definition} 

The next two lemmas are routine consequences of the definitions. 

\begin{lemma} \label{in} 
There are $\psi_T^r\in \l^{x, z, r}_{\infty, 0}$, 
$\psi_T^s\in \l_{\infty, 0}^{y, z, s}$ such that in all 
generic extensions 
\[(a, b, f)\models \psi_T^r\] 
if and only if 
\[(a, b, f)\models \psi_T^s\] 
if and only if 
\[(a, b, f)\in [T].\] 
\end{lemma} 

\begin{lemma} \label{out} 
There are $\psi_{\bt}^r\in \l^{x, z, r}_{\infty, 0}$, 
$\psi_{\bt}^s\in \l_{\infty, 0}^{y, z, s}$ such that in all generic 
extensions 
\[(a, b, f)\models \psi_{\bt}^r\] 
if and only if 
\[(a, b, f)\models \psi_{\bt}^s\] 
if and only if 
\[(a, b, f)\in [\bt].\] 
\end{lemma} 


\begin{definition}  
Let $S_0$ be the set of all $\theta\in \l^x_{\infty, 0}\cap L_\gamma[T, \bt]$ such that 
\[\theta\wedge \psi_T^r\wedge \neg\theta(z)\] 
is inconsistent. 
\end{definition} 

Since our notion of consistency coincides with the existence of a model for 
sentences in $\l^x_{\omega_1, 0}$,  $S_0$ is  the set of 
$\theta\in \l^x_{\infty, 0}\cap L_\gamma[T, \bt]$ for which in no generic extension do there 
exist $a, b\in 2^\omega$, $f\in \kappa^\omega$ with 
\[a\models \theta,\] 
\[b\models \neg\theta,\] 
\[(a, b, f)\in p[T].\] 
We may therefore think of $S_0$ as the absolutely $E$-invariant propositions. 

\begin{lemma} \label{invariant} 
$S_0$ is $\Sigma_1$ over $L_\gamma[T, \bt]$. 
\end{lemma} 

\begin{proof} 
By \ref{admissible}. 
\end{proof} 




\begin{lemma} \label{interpolant} 
Let $\theta_0, \theta_1\in \l^x_{\infty, 0}\cap L_\gamma [T, \bt] $ and suppose 
\[\theta_0\wedge \psi_T^r \wedge \theta_1(z)\] 
is inconsistent. 

Then there is $\theta\in S_0$ such that 
\[\theta_0\wedge \neg \theta\] 
and 
\[\theta \wedge \theta_1\] 
are both inconsistent. 

(More intuitively, $\theta_0$ implies $\theta$ and $\theta$ implies 
$ \neg\theta_1$; thus $\theta$ is an absolutely $E$-invariant interpolant between these two 
formulas. ) 
\end{lemma} 

\def\lg{L_\gamma [T, \bt]}

\begin{proof}  Applying \ref{admissible} we can find a $\Sigma_0$ formula $\Phi$ such that 
$\phi\in \lg$ is an interpolant between $\psi_0, \psi_1\in \lg$ if and only 
\[\lg\models \exists A\Phi (A, \phi, \psi_0, \psi_1).\] 
Using $T^2$ appearing as an isomorphic copy inside $T$ we have 
\[\theta_0\wedge\psi_T^r \] 
is inconsistent with 
\[\theta_1(y)\wedge\psi_T^s, \]  
and 
applying \ref{craig}  inside the admissible we can certainly find some $A, \phi \in 
\lg \cap \l^z_{\infty, 0}$ with 
\[\lg\models \Phi(A,\phi, \theta_0\wedge\psi_T^r, \psi_T^s \wedge \theta_1(y)).\] 
Let $(A_0, \phi_0)$ be the least pair in the canonical well ordering of $\lg$. 

At this stage, using $T^2$  appearing as an isomorphic copies inside 
$T$, we have $\phi_0(x) \wedge \psi_T$ is inconsistent with $\psi_T \wedge \theta_1(y)$ 
So again we can take $(A_1, \phi_1)$ to be the first pair with $A_1$ witnessing 
$\phi_1$'s role as interpolant. 

Continuing we obtain a function with $\Sigma_0$ graph over $\lg$, 
\[n\mapsto (A_n, \phi_n),\] 
such that 
at each $n>0$ we have 
\[\lg\models \Phi(A_n, \phi_n, \phi_{n-1}(x)\wedge \psi_T^r, \psi_T^s\wedge \theta_1(y).\] 
In particular the $E$-saturations of $\{a: a\models \phi_n(x)\}$ and 
$\{b: b\models \theta_1\}$ are disjoint and the $E$-saturation of 
$\{a: a\models \phi_{n-1}(x)\}$ is included inside 
$\{a: a\models \phi_n(x)\}$. 


The characteristic property of admissible sets is $\Sigma_1$ replacement, so the 
set $\{\phi_n: n\in\omega\}$ exists inside $\lg$. We then take 
\[\theta=\bigvee_{n\in\omega}\phi_n.\] 
\end{proof} 

\def\fm{ \l^x_{\infty,0}\cap\lg} 

\begin{definition} Let $S_1$ be the set of all $\theta\in \l^x_{\infty,0}\cap\lg$ 
such that the theory 
\[\{\theta\}\cup\{\phi\Leftrightarrow \phi(z): \phi\in S_0\}\cup\{\psi_{\bt}^r\}\] 
is inconsistent. 
\end{definition} 

\begin{lemma} 
$S_1$ is $\Sigma_1$ over $\lg$. 
\end{lemma} 

\begin{proof} 
By \ref{barwise}, $\theta$ is in $S_1$ if and only if there exists some $X\in \lg$, 
$X\subset S_0$ with 
\[\{\theta\}\cup X\cup\{\psi_{\bt}^r\}\] 
inconsistent. 
Then the result follows routinely by manipulation of quantifiers. 
\end{proof} 

Now we have a divide, exactly corresponding to the same step in 
\cite{hakelo}. 

\begin{definition} We let $W$ be the set $\{\neg\theta: \theta\in S_1\}$. 
\end{definition} 


Intuitively, $W$ is a theory about a real $x$ for which there is an 
$E$-inequivalent $y$ which cannot be separated by an $E$-invariant formula. 



On the one hand $W$ may be inconsistent. Then in particular every 
$a\in 2^\omega$ satisfies some formula in $S_1$, and it is 
inconsistent for there to be an $E$-inequivalent $b$ which cannot be separated by a formula 
in $S_0$. Thus we have case (II). 

Instead suppose $W$ is consistent. We will work towards a Borel reduction of 
$E_0$. 

\def\p{{\cal P}}


Let $M$ be a countable elementary submodel of $\lg$. 
%Let $\Theta$ be the $\Sigma_1$ formula 
%denoting inconsistency in $\lg$. 

\begin{definition} 

Let $\p$ be the set of 
$V\subset \lg\cap \l^x_{\infty, 0}$ such that: 

\leftskip 0.4in 

\noindent (i) $V$ is $\Ubf{\Sigma}_1$ over $M$; 

\noindent (ii)   $V\supset W$; 

\noindent (iii) $V$ is consistent. 

\leftskip 0in 

We set $V\leq U$ if $V\supset U$. 



Let $\p\times_T \p$ be the set of pairs $(V_1, V_2)\in \p\times\p$ such that 
\[V_1\cup \{\theta(z): \theta\in V_2\}\cup \{\psi_T^r\}\] 
is consistent. (Note: This amounts to the $\Ubf{\Pi_1}$ over $M$ assertion that every 
$X$ included in this $\Ubf{\Sigma}_1$ set satisfies $\bigwedge X$ is consistent.) 
In rough terms, we are asking for it to be consistent that the real described by $V_1$ be 
$E$-equivalent to the real described by $V_2$. 
We set $(V_1, V_2)\leq (U_1, U_2)$ if each $V_i\supset U_i$. 





For $G\subset \p$  a filter we define $a(G)\in 2^\omega$ with 
$a(G)(n)=1$ if $p^x_n\in G$. For $G\subset \p\times_T \p$ a 
filter we define $a_\ell(G)$ and $a_r(G)$ by 
\[a_\ell(G)(n)=1\Leftrightarrow \exists (V,W)\in G (p^x_n\in V), \] 
\[a_r(G)(n)=1\Leftrightarrow \exists (V, W)\in G(p^x_n\in W).\]  

\end{definition} 

Note that since $M$ is countable, both these forcing notions are countable. Thus a forcing 
extension by either one over the universe is either trivial or equivalent to the result of 
adding a Cohen real. 

\def\ptp{\p\times_T \p}

\begin{lemma} 
$(W,  W)\Vdash _{\ptp} (a_\ell (G), a_r(G))\in p[\bt]$. 
\end{lemma} 

\begin{proof} 
Let $(V_1, V_2)\leq(W, W)$ force otherwise. Let $V_1^*\subset \l^{y, z, s}_{\infty,0}\cap M$ 
be the set 
\[\{\psi(y): \psi\in V_1\} \cup\{\psi(z): \psi\in V_1\}
\cup \psi_{\bt}^s\cup \{\theta(y) \Leftrightarrow \theta(z): \theta\in 
S_0\cap M\}.\] 
$V_1^*$ is $\Ubf{\Sigma}_1$ over $M$

\begin{notation} For $A\subset \l^x_{\infty, 0}$ we define $A(y)$ to be 
$\{\psi(y): \psi\in A\}$, $A(z)$ to be $\{\psi(z):\psi\in A\}$. 
\end{notation} 


\medskip 

\def\lx{\l^x_{\infty, 0}\cap \lg} 
\def\lz{\l^z_{\infty, 0}\cap \lg} 


{\bf Claim:} $V_1^*\cup V_2\cup\{\psi^r_T\}$ is consistent. 

\medskip 

{\bf Proof of claim:} Let $\hat{V}_1$ be set of $\psi\in \lx$ such that 
\[V_1\cup V_2(z) \cup \{\psi^r_T\}\cup \{\neg\psi\}\] 
is inconsistent -- in other words, asserting $V_1$ about $x$, $V_2$ about $z$, 
along with $T$ witnessing $xEz$, entails $\psi$ about $x$. 

$\hat{V}_1$ is consistent, just because our assumption on $(V_1, V_2)\in 
\ptp$ entails $V_1\cup V_2(z) \cup \{\psi^r_T\}$ consistent. 
\[\hat{V}_1\supset V_1\supset W,\] 
and so 
\[\hat{V_1}\cup \{\theta\Leftrightarrow \theta(z): \theta\in S_0\}\cup\{\psi^r_{\bt}\}\] 
is consistent. We then let $U_1$ be the set of $\psi\in\lz$ such that 
\[\hat{V}_1 \cup \{\theta\Leftrightarrow \theta(z): \theta\in S_0\}\cup\{\psi^r_\bt\}\cup\{\neg\psi\}\] 
is inconsistent -- in other words, $U_1$ is the set of consequences for $z$ of asserting 
$\hat{V}_1$ along with the existence of an $x$ which is witnessed by $\bt$ to be 
$E$-inequivalent but cannot be separated from $z$ by a formula in $S_0$. 

\medskip 

{\bf Subclaim:} $U_1\cup V_1\cup \{\psi^r_T\}$ is consistent. 

\medskip 

{\bf Proof of subclaim:} Otherwise by \ref{barwise} there are $Z\subset U_1, X\subset V_1$, 
$Z, X\in \lg$, such that if we let 
\[\psi_x=\bigwedge X,\] 
\[\psi_z=\bigwedge Z,\] 
then 
\[\psi_x\wedge \psi^r_T\wedge\psi_z\] 
is inconsistent. 
But then by \ref{interpolant} there is $\theta_0\in S_0$ such that 
\[\psi_x\Rightarrow \theta_0,\]
\[\psi_z\Rightarrow \neg\theta_0,\] 
with a contradiction to the consistency of $U_1$. 
(The point is that if $(a, b, f)\models 
\hat{V_1}\cup \{\theta\Leftrightarrow \theta(z): \theta\in S_0\}\cup\{\psi^r_{\bt}\}$, then 
$a\models \psi_x$, hence $a\models \theta_0$, while $b\models U_1$, and hence 
$b\models \psi_z$, hence 
$b\models \neg\theta_0$, which brutally contradicts $\theta_0\in S_0$.) 
\hfill (Subclaim$\square$) 

\medskip 

{\bf Subclaim:} $\hat{V}_1\cup\{\theta\Leftrightarrow \theta(z): \theta\in S_0\} 
\cup\{\psi^r_\bt\}\cup V_1(y)\cup \{\psi^s_T\}$ is consistent. 

\medskip 

{\bf Proof of subclaim:} Or else by \ref{craig} there would be 
$\psi\in \l^z_{\infty, 0}\cap \lg$ which is a consequence of 
\[\hat{V}_1 \cup\{\theta\Leftrightarrow \theta(z): \theta\in S_0\}\cup\{\psi^r_\bt\}, \] 
and hence by definition of $U_1$ has $\psi$ in $U_1$, 
but also has $\neg\psi$ a consequence of 
\[V_1(y)\cup \{\psi^s_T\}.\] 
Changing variables, $y$ to $x$, we get 
\[V_1\cup\{\psi^r_T\}\] 
entailing $\neg \psi$. 
Thus $\psi$ provides a stark point at which 
$V_1\cup\{\psi^r_T\}$ and $U_1$ disagree, with a contradiction to 
the last subclaim. 
\hfill (Subclaim$\square$) 

\medskip 

{\bf Subclaim:} $\hat{V_1}\cup \{\theta\Leftrightarrow \theta(z): \theta\in S_0\}
\cup \{\psi_\bt^r\}\cup V_1(z)$ is consistent. 

\medskip 

{\bf Proof of subclaim:} 
Go to some generic extension in which we have a model for 
\[\hat{V}_1\cup\{\theta\Leftrightarrow \theta(z): \theta\in S_0\} 
\cup\{\psi^r_\bt\}\cup V_1(y)\cup \{\psi^s_T\},\] 
with 
$a\in 2^\omega$ serving for $x$, $b\in 2^\omega$ for $y$, $c\in 2^\omega$ for 
$z$. 

Then we would have 
\[(c, b)\in p[T],\] 
and so for all $\theta\in S_0$ 
\[b\models \theta\Leftrightarrow c\models \theta.\] 
On the other hand we have for all $\theta\in S_0$ 
\[a\models\theta\Leftrightarrow c\models \theta,\] 
and so for all $\theta\in S_0$
\[b\models\theta\Leftrightarrow a\models \theta.\] 

Combining $(c, b)\in p[T]$ and $(a, c)\in p[\bt]$ we obtain 
\[(a,b)\in p[\bt],\] 
and thus for some $f\in \kappa^\omega$ we have $(a, b, f)$ a model of 
$\hat{V_1}\cup \{\theta\Leftrightarrow \theta(z): \theta\in S_0\}
\cup \{\psi_\bt^r\}\cup V_1(z)$. 
\hfill (Subclaim$\square$) 

\medskip 

After simply changing variables we have 
\[\hat{V_1}(z)\cup \{\theta(y)\Leftrightarrow \theta(z): \theta\in S_0\}
\cup \{\psi_\bt^s\}\cup V_1(y)\] 
consistent. 
Since $\hat{V_1}(z)$ is closed under all the consequences in 
$\l^z_{\infty, 0}\cap \lg$ of 
\[V_1(z)\cup V_2\cup \{\psi^r_T\}\] 
we can appeal to \ref{craig} to obtain the consistency of 
\[\hat{V_1}(z)\cup \{\theta(y)\Leftrightarrow \theta(z): \theta\in S_0\}
\cup \{\psi_\bt^s\}\cup V_1(y) \cup V_2\cup \{\psi^r_T\},\] 
as required. 
\hfill (Claim$\square$) 

\medskip 






\def\q{{\cal Q}} 

Let $\q$ be the set of $(U_1, U_2)$ such that 

\leftskip 0.4in 

(i) $U_1$ is a $\Ubf{\Sigma}_1$ over $M$ 
subset of $\l^{y, z, s}_{\infty, 0}$; 

(ii) $U_1\supset V_1^*$; 

(iii) $U_2$ is a $\Ubf{\Sigma}_1$ over $M$ subset of 
$\lx$; 

(iv) $U_1\cup U_2\cup\{\psi_T^r\}$ is consistent. 

\leftskip 0in 

For $(U_1, U_2)\in \q$ we let 
\[p_1(U_1)=\{\psi(x): \psi\in \l^y_{\infty, 0}\cap \lg, 
U_1\cup\{\neg\psi\} {\rm \: inconsistent}\};\] 
 in otherwords, $p_1(U_1)$ is the set of consequences for $y$ entailed by 
 the theory $U_1$. Similarly we let 
 \[p_2(u_1)=\{\psi(x): \psi\in \l^z_{\infty, 0}\cap \lg, 
U_1\cup\{\neg\psi\} {\rm \: inconsistent}\},\] 
 the consequences for $z$. 
 
 It follows immediately from the 
 definitions that if $(U_1, U_2)\in \q$ then $(p_1(U_1), U_2)\in \ptp$.  
 
 \medskip 
 
 {\bf Claim:} If $(U_1, U_2)\in \q$, then $(p_2(U_1), U_2)\in \ptp$. 
 
 \medskip 
 
 {\bf Proof of claim:} If $p_2(U_1)\cup U_2(z)\cup \{\psi^r_T\}$ is inconsistent, then by 
 \ref{barwise} we get $\psi_x\in \lx$, $\psi_z\in \lz$ with 
 \[\psi_x\wedge \psi^r_T\wedge \psi_z\] 
 inconsistent, $\psi_x$ a consequence of $U_2$, $\psi_z$ a consequence 
 of $p_2(U_1)$. 
 Then by \ref{interpolant} there is some $\theta_0\in S_0$ with 
 \[\psi_x\Rightarrow \theta_0,\] 
 \[\psi_z(x)\Rightarrow \neg\theta_0.\] 
 
 However this contradicts the assumption of $(U_1, U_2)\in \q$, since 
 $a, b, c, f, g$ were to have 
 \[(a, b, f)\models U_1\cup\{\theta(y)\Leftrightarrow \theta(z): \theta\in S_0\}\wedge 
 \psi^s_\bt,\] 
 \[(c, b, g)\models U_2\wedge \psi^r_T,\] 
 then $aEc$ and $\theta_0\in S_0$ gives 
 \[a\models \theta_0\Leftrightarrow c\models 
 \theta_0,\] 
 while the assumption on $(a, b, f)$ 
 yields 
 \[a\models\theta_0\Leftrightarrow b\models S_0,\] 
 and hence 
 \[b\models \theta_0\Leftrightarrow c\models S_0.\] 
 This contradicts $b\models p_2(U_1)$, $c\models U_2$ and $\neg\theta_0(z)$ being a consequence 
 of $p_2(U_1)$, $\theta$ being a consequence of $U_2$. 
 \hfill (Claim$\square$) 
 
 
 
 
 
 
 Note further 
 that if $(W_1, W_2)\leq (p_1(U_1), U_2)$ in $\ptp$, then we can let 
 $U'_1=\{\psi(y): \psi\in W_1\}\cup U_1$  to obtain $(U_1', W_2)\in \q$ below $(U_1, U_2)$ 
 with 
 $(p_1(U_1'), V_2)=(W_1, W_2)$. Similarly on the other side, if $(W_1, W_2)\leq (p_2(U_2), U_2)$ 
 we can obtain $(U_1', W_2)\in \q$ with $p_2(U_1')=W_1$. 
 From these observations one has that for any open dense $D\subset \ptp$ the sets 
 \[\{(U_1, U_2): (p_1(U_1), U_2)\in D\},\] 
 \[\{(U_1, U_2): (p_2(U_1), U_2)\in D\}\] 
 are open dense. In this sense we have a kind of transfer property for open dense sets. 
 
Let $G\subset \q$ be $V$-generic. Let $G^1=\{(p_1(U_1), U_2): (U_1, U_2)\in G\}$ and 
$G^2=\{(p_2(U_1), U_2): (U_1, U_2)\in G\}$. By the transfer property for  open 
dense sets, $G^1$ and $G^2$ are both $V$-generic below the condition 
$(V_1, V_2)$, and hence by our assumption that the claim fails 
\[(a_\ell(G^1), a_r(G^1))\notin p[\bt],\] 
\[(a_\ell(G^2), a_r(G^2))\notin p[\bt].\] 

However it is direct consequence of the definitions that $a_r(G^1)=a_r(G^2)$. Moreover 
it is an easy consequence of the definition of the forcing notion $\q$ that 
\[(a_\ell(G^1), a_\ell(G^2))\in p[\bt],\] 
with a contradiction to $p[\bt]$ defining the complement of an equivalence relation 
in the generic extension. 
\end{proof} 


True to our promises, the next lemma is proved without choice. 


\begin{lemma} There exists a countable collection $(D_n)_{n\in \omega}$ of dense open 
sets in $\ptp$ such that if $G\subset \ptp$ is a filter meeting every $D_n$, then 
\[(a_\ell(G), a_r(G))\in p[\bt].\] 
\end{lemma} 

\begin{proof} The previous lemma will hold true in $L[T, \bt]$ as well as it does 
in $V$, so appealing to reflection 
go to a $\delta>\kappa$ with $L_\delta[T, \bt]$ which also satisfies this claim along 
with a 
large fragment of ZFC. 
Let $N$ be a countable elementary substructure of $L_{\delta}[T, \bt]$. If $G$ is 
$N$-generic, then there will be $f\in (\kappa\cap N)^\omega$ having 
\[N[G]\models (a_\ell(G), a_r(G), f)\in [\bt].\] 
Since $\bt\cap N$ is certainly a subset of $\bt$, we are done. 
\end{proof} 

At this stage it will be momentarily convenient to build elaborations of our propositional 
languages. 

\begin{definition} For $t, t'\in 2^n$, $n\in \omega$, we let $\l^{t, t', r}$ be the language with 
propositions 
\[\{p_n^t: n\in \omega\}, \{p_n^{t'}: n\in \omega\}, 
\{p_{r(n)=\alpha}^{t, t'}: n\in \omega, \alpha\in \kappa\}.\]  For $a, b\in 2^\omega$, 
$f\in \kappa^\omega$ we define 
\[\m_{a, b, f}^{t, {t'}, r}\] 
by setting $p_n^t$ true if $a(n)=1$, $p_n^{t'}$ true if $b(n)=1$, and 
$p^{t, t'}_{r(n)=\alpha}$ if $f(n)=\alpha$. As before, 
\[(a, b, f)\models \varphi\] 
if the resulting $\m_{a, b, f}^{t, {t'}, r}$ satisfies it. We define $\l^t$ and 
substitutions of one formula across 
into the language of another just as before. Again we can define 
\[\psi_T^{t, t', r}\in \l_{\infty, 0}^{t, t', r}\cap \lg\] 
so that $(a, b, f)$ satisfies this formula if and only if $(a, b, f)\in [T]$, and 
similarly with 
\[\psi_\bt^{t, t', r}\in \l_{\infty, 0}^{t, t', r}\cap \lg\] 
and $\bt$. 
\end{definition} 







We now build by induction on $n$, $(w_s)_{s\in 2^n}$ in $\p$, 
$(\sigma_{s_1, s_2})_{s_1, s_2\in 2^n}$ in $\kappa^n\cap M$, 
$(h_s)_{s\in 2^n}$ in $\omega^n$ with the following conditions:- 

\leftskip 0.4in 

\noindent (i) at each $s_1, s_2\in 2^n$ 
\[(h_{s_1}, h_{s_2}, \sigma_{s_1, s_2})\in T\cap N;\] 

\noindent (ii) at each $s_1\neq s_2\in 2^n$ we have 
\[(w_{s_1}, w_{s_2})\in \ptp; \] 




\noindent (iii) at each $s_1, s_2\in 2^n$ with $s_1(n-1)\neq s_2(n-1)$ we have 
\[(w_{s_1}, w_{s_2})\in D_0\cap D_1\cap...\cap D_n;\] 

\noindent (iv) if $s_1(n-1)=s_2(n-1)$ then $\sigma_{s_1, s_2}\supset 
\sigma_{s_1|_{n-1}, s_2|_{n-2}}$; 

\noindent (v) $h_s\supset h_{s|_{n-1}}$; 

\noindent (vi) at each $s\neq t$ we let $v_{s, t}$ be the theory 
\[w_s(s)\cup w_t(t)\]
\[\cup \{p^s_m: m<n, h_{s}(m)=1\}\cup \{\neg p^s_m: m<n, h_{s}(m)=0\}\cup\] 
\[\cup \{p^t_m: m<n, h_{t}(m)=1\}\cup \{\neg p^t_m: m<n, h_{t}(m)=0\}\cup\] 
\[\cup\{p_{r(m)=\alpha}^{s, t}: m<n, \sigma_{s, t}(m)=\alpha\}\cup 
\{\neg p_{r(m)=\alpha}^{s, t}: m<n, \sigma_{s, t}(m)\neq \alpha\}\cup \{\psi^r_T\};\] 
we then require that 
for each $w_s$ includes every $\phi(x)\in \lg$ which is a consequences of 
\[\bigcup_{t\neq t' \in 2^n} v_{t, t'}.\] 

\leftskip 0in 

As is commonly the case with these constructions, when written out in detail the 
clauses are fearsome. (vi) in particular requires an apology. 

The idea is that at stage $n$ we have built a partial story about $2^n$ many reals. 
We are requiring if we pair the stories for any two reals, gaining $(w_s, w_t)$, then 
the condition is in $\ptp$ -- which is like saying they could be inequivalent, but not in a 
way that can be separated by one of the invariant sets in $S_0$. (i) says not only might 
they be equivalent, but here is some partial, finite,  information about the witness that 
could do the job. (iv) states that if $s$ and $t$ in $2^n$ agree on their final term, then 
the witness at this level is consistent with what we saw just for the restriction of $s$ and $t$ to 
the previous lemma; this condition is diametrically opposed to (iii), which states that 
if whenever $s$ and $t$ disagree on a term we immediately ask that $(w_s, w_t)$ flies off 
and meets the first $n+1$ many dense open sets. 

(vi) is a bit more subtle. This condition states that if we collect all the information together 
about all $2^n$ many reals we have in mind at stage $n$, then each $w_s$ 
includes all the entailments of that theory. There is a terrifying typographical massacre in 
expressing this simple idea, just because we need to play around with the subscripts to 
make each $w_s$ refer to a different real. But this is the idea. 

The possibility of completing this construction follows just as in 
\cite{hakelo}. Assume we have built the relevant 
 $(w_s)_{s\in 2^n}$, 
$(\sigma_{s_1, s_2})_{s_1, s_2\in 2^n}$,  
$(h_s)_{s\in 2^n}$, and attempt to ratchet up one more level. 

Let $0^n$ be the element of $2^n$ such that each entry is 0. For each $s$ we can extend 
$w_{0^n}$ and $w_s$ to a pair $(w', w'')\in \ptp$ which meets 
\[D_0\cap D_1\cap...\cap D_n\cap D_{n+1}.\] 
Doing this over several times we can at last assume that 
we have $w^*$ including $w_{0^n}$ and $v_{s^\smallfrown 1}$ extending each 
$w_s$ so that at every $s$ 
\[(w^*, v_{s^\smallfrown 1})\in D_0\cap ...D_{n+1}.\]  
Nothing has really changed in this situation so we can repeated adinfinitum, 
creating $(u_{s^\smallfrown i})_{s\in 2^n, i\in \{0, 1\}}$ so that at each $i\neq j$, 
$s, t\in 2^n$ 
\[(u_{s^\smallfrown i}, u_{t^\smallfrown j})\in D_0\cap...D_{n+1}.\] 

Now again we are confronted with this massive theory, concerning $2^{n+1}$. For 
$s, t\in 2^{n+1}$ we define $v'_{s, t}$ to be 
\[v_s(s)\cup v_t(t)\]
\[\cup \{p^s_m: m<n, h_{s|_n}(m)=1\}\cup \{\neg p^s_m: m<n, h_{s|_n}(m)=0\}\cup\] 
\[\cup \{p^t_m: m<n, h_{t|_n}(m)=1\}\cup \{\neg p^t_m: m<n, h_{t|_n}(m)=0\}\cup\] 
\[\cup\{p_{r(m)=\alpha}^{s, t}: m<n, \sigma_{s|_n, t|_n}(m)=\alpha\}\cup 
\{\neg p_{r(m)=\alpha}^{s, t}: m<n, \sigma_{s|_n, t|_n}(m)\neq \alpha\}\cup\{\psi^r_T\},\] 
and we again go on to take the union of the various $v_{s, t}'$ as $s, t$ range over 
distinct elements of $2^{n+1}$. The construction of the various $w', w'', w^*$ and so on 
can be done so that we maintain the consistency of the unions from (vi) above, and so 
that in the end 
\[\bigcup_{s\neq t, s, t\in 2^{n+1}}v'_{s, t}\] 
is consistent. We can appropriately extend the 
values of the various $h_s$'s and $\sigma_{s, t}$'s by simply filing in further information 
in this giant theory. 


With this all in place we can at least define the reduction of $E_0$. Given $b\in 2^\omega$ we 
let $G_b\subset \p$ be the set of $v$ such that some $w_s\subset v$. We let $f(b)$ be the resulting 
real 
\[a(G_b)\in 2^\omega.\] 
Note that this also equals $\bigcup_n h_{b|_n}$. 

If $b E_0 c$ then we choose some $N$ with 
$b(n)=c(n)$ all $n\geq N$ and let $s=b|_N$, $t=b|_N$. We then appeal to (iv) to obtain an 
increasing sequence 
\[\sigma_{s, t}\subset \sigma_{b|_{N+1}, c|_{N+1}}\subset \sigma_{b|_{N+2}, c|_{N+2}}...\] 
with each 
\[(h_{b|_n}, h_{c|_n}, \sigma_{b|_n, c|_n})\in T, \] 
and hence 
\[\bigcup_{n>N} \sigma_{b|_n, c|_n}\] 
witnesses 
$(f(b), f(c))\in p[T]$, and hence $f(b) E f(c)$. 

Conversely if there are infinitely many $n$ with $b(n)\neq c(n)$ then we have appeal to 
(iii) to get 
\[G_b\times G_c\in \bigcap_{n\in\omega} D_n,\] 
and hence, but the assumption on the $D_n$'s, $f(b)$ and $f(c)$ are 
$E$-inequivalent. 

We do obtain as a consequence of this result a theorem originally 
proved by totally different means in \cite{foreman} and \cite{ditzen}. 

\begin{corollary} (Foreman-Magidor, Ditzen) Assume ZF + AD$^\R$. Then for every 
equivalence $E$ on $2^\omega$ we have either 

\leftskip 0.4in 

\noindent (I) $E_0\leq E$, or 

\noindent (II) there is an ordinal $\alpha$ and 
\[f:  2^\omega\rightarrow {\cal P}(\alpha)\] 
such that $f(x)=f(y)$ if and only if $x E y$. 

\leftskip 0in 

\end{corollary} 

\begin{proof} Fix $E$. First of all we obtain the trees. Woodin has shown in unpublished work that 
AD$^\R$ implies every set of reals has a scale, and so we can certainly find trees $T, \bt$ 
on some $\kappa$ projecting to $E$ and its complement. 

Secondly we need to verify the condition regarding Cohen forcing. 
Given terms $\tau_1, \tau_2, \tau_2$ we can find some $x\in 2^\omega$ with each $\tau_i$ 
in $L[x]$. Then since AD implies the non-existence of an $\omega_1$ sequence of reals we 
have $\omega_1$ inaccessible in $L[x, T, \bt]$. Thus we can find an $L[x, T, \bt]$ generic 
for Cohen forcing, $G$. Since the calculation of $p[\bt]$ is absolute between well founded 
models, we have $p[\bt]$ continues to define the complement of an equivalence relation 
in $L[x, T, \bt, G]$. Since this argument holds for any triple of terms in Cohen forcing, 
we are done. 
\end{proof} 



\section{$\Ubf{\Pi}^1_1$ equivalence relations} 


The argument consists in capturing a certain moment in the proof of 
\ref{hsversion}. It was for this purpose that \ref{hsprecise} was isolated. 

\begin{theorem} Assume every real has a sharp. Let $E$ be a 
$\Ubf{\Pi}^1_1$ equivalence relation. 
Then either 

(I) $E_0\leq_B E$; or 

(II) there is a $\Ubf{\Delta}^1_3$ in the codes assignment of bounded subsets of $\omega_1$ as 
complete invariants to the equivalence classes. 

\end{theorem}  

\begin{proof}  For notational convenience assume $E$ is lightfaced $\Pi^1_1$. Let 
\[\bt\subset 2^{<\omega} \times 2^{<\omega} \times 
\omega^{<\omega}\] 
be canonically chosen to project to the complement of $E$ and let 
\[T\subset 2^{<\omega} \times 2^{<\omega} \times 
\omega_1^{<\omega}\] be equally chosen to project to $E$. Both these trees will exist in 
$L$; in fact $\bt$ will be recursive and $T$ will be $\Sigma_0$. Let $\gamma>\omega_1$ be the least ordinal such that $L_\gamma$ is 
admissible. 

Assume that $E_0$ does not Borel reduce to $E$. 

Let $S_0$ be the set of $\varphi\in \l^x_{\infty, 0}\cap L_\gamma$ 
such that in no generic extension does there 
exist $b_1, b_2, f$ with $(b_1, b_2, f)\in [T]$ with $b_1\models \varphi$, 
$b_2\models \neg\varphi$. 
Following \ref{hsprecise} we have that for any $b\in 2^\omega$ there is no generic extension 
with $(b, c)\in p[\bt]$ but for all $\varphi\in  \l^x_{\infty, 0}\cap L_\gamma$ 
\[b\models \varphi \Leftrightarrow c\models \varphi.\] 

Let $\kappa>\gamma$ be the least ordinal for which $L_\kappa$ satisfies ZFC without 
powerset. Note then that $L_\kappa$ is the Skolem hull of $\omega_1+1$. 
At each $\alpha<\omega_1$ let $M_\alpha$ be the Skolem hull of $\alpha\cup{\omega_1}$ in 
$L_\kappa$. 
Let $C$ be the ordinals $\alpha$ less than $\omega_1$ such that 
\[\alpha\cap M_\alpha=\alpha.\] 
For each $\alpha$ in $C$ let $\kappa(\alpha)$ be such that the transitive 
collapse of $M_\alpha$ is isomorphic to $L_{\kappa(\alpha)}$. Let 
\[i_\alpha : L_{\kappa(\alpha)}\rightarrow L_\gamma\] 
be the inverse of the collapsing map for $M_\alpha$. Let $S_0^\alpha=i^{-1}(S_0)$, 
$T^\alpha=i^{-1}(T)$, $\bt^\alpha=i^{-1}(\bt)$. Define 
\[U_\alpha: 2^\omega\rightarrow {\cal P}(S^\alpha_0)\] 
\[a\mapsto \{\theta\in S_0^\alpha: a\models \theta\}.\] 


\medskip 

{\bf Claim:} For all $\alpha\in C$, $a, b\in 2^\omega$, 
$U_\alpha(a)=U_\alpha(b)\Rightarrow x E y$. 

\medskip 

{\bf Proof of claim:} Note that $i_\alpha[\bt]=\bt$. Moreover $L_{\kappa}^{{\rm Coll}(\omega, \omega_1)}$ 
calculates that there is no pair $a$, $b$ in $p[\bt]$ but having 
\[a\models \theta\Leftrightarrow b\models\theta\] 
all $\theta\in S_0$. Thus the same fact goes down to 
$L_{\kappa(\alpha)}^{{\rm Coll}(\omega, \alpha)}$, 
with $S_0^\alpha$ 
replacing $S_0$. But this fact is $\Sigma^1_1(c)$ for any parameter $c$ encoding $S_0^\alpha$, and 
hence absolute. 
\hfill (Claim$\square$) 

\medskip 

{\bf Claim:} For all $a\in 2^\omega$ there is some $\alpha\in C$ with 
\[a\models \theta\Leftrightarrow a\models i_\alpha(\theta).\] 


\medskip 

{\bf Proof of claim:} Just choose $\alpha$ so that the Skolem hull of $\alpha$ in 
$L_\kappa[a]$, $M^a$, has $M^a\cap \omega_1=\alpha$. Let $L_\delta[a]$ be 
the transitive collapse, and 
\[i^a:L_\delta[a]\rightarrow L_\kappa[a].\] 

It follows from $L_\kappa$ being the Skolem hull of $\omega_1$ that 
$M^a\cap \kappa = M_\alpha\cap \kappa$ and $i^a$ and $i_\alpha$ agree 
on $L_\delta$. Thus by elementarity of $i^a$, for all $\theta\in S_0^\alpha$ 
\[a\models \theta\Leftrightarrow a\models i^a(\theta)\Leftrightarrow a\models 
i_\alpha(\theta).\] 
\hfill (Claim$\square$) 

\medskip 

For each $a\in 2^\omega$ let $\alpha(a)$ be least $\alpha\in C$ 
such that there exists some $bEa$ with 
\[b\models \theta\Leftrightarrow b\models i_\alpha(\theta).\] 


\medskip 

{\bf Claim:} $\alpha(a)$ is uniformly definable over $L[a]$ from any $\omega_1^V$. 

{\bf Proof of claim:} Given $\omega_1^V$ as a parameter, $L[a]$ can define $C$ and the 
corresponding $i_\alpha$, $S_0^\alpha$ just as in $V$. Then for each $\alpha\in C$ the 
existence of $b Ea$ having 
\[b\models \theta\Leftrightarrow b\models i_\alpha(\theta)\] 
will be uniformly $\Sigma^1_2(a, g)$ for any parameter $g$ encoding the collapse of 
$\{\theta\in S^\alpha_0: a\models i_\alpha(\theta)\}$, and hence absolute between 
$L[a]^{{\rm Coll}(\omega, \alpha)}$ and $V$. 
\hfill (Claim$\square$) 

\medskip 

It is then a routine application of our assumption that every real has a sharp to verify the 
function 
\[a\mapsto \alpha(a)\] 
is $\Delta^1_3$. Let $\pi:  \omega_1\rightarrow S_0$ be the canonical bijection induced by 
$L_\gamma$ being the Skolem hull of $\omega_1$. 
We finish by letting 
\[U: 2^\omega\rightarrow 2^{<\omega_1}\] 
\[a\mapsto \{\beta<\alpha(a):a\models i_{\alpha(a)}(\beta)\}.\] 
\end{proof} 


I do not know if the function $U$ can be taken to be $\Ubf{\Delta}^1_2$ in option (II) of the 
theorem. I also do not know if the assumption of sharps is necessary -- the reduction procedure 
described works even without sharps, but it is not clear why it would projective. 



\begin{thebibliography}{99} 

\bibitem{barwise} J. Barwise, {\bf Admissible sets and structures,} Springer-Verlag, 
Berlin New York, 1975. 

\bibitem{ditzen} A. Ditzen, PhD, Caltech, 1992. 

\bibitem{foreman} M. Foreman, M. Magidor, 
{\it Large cardinals and definable counterexamples to the continuum hypothesis,}  
{\bf Annals of Pure and Applied Logic,} vol. 76 (1995), 47--97.

\bibitem{hakelo} L. Harrington, A.S. Kechris, A. Louveau, 
{\it A Glimm-Effros dichotomy for Borel equivalence relations,}  
{\bf Journal of the American Mathematical Society,} vol. 3 (1990), 
903--928. 

\bibitem{harringtonshelah} L. Harrington, S. Shelah, 
{\it Counting equivalence classes for co-$\kappa $-Souslin 
equivalence relations,} {\bf Logic Colloquium '80 (Prague, 1980),  } 
147--152, Stud. Logic Foundations Math., 108, 
North-Holland, Amsterdam-New York, 1982.

\bibitem{hjorthkechrisulm} G. Hjorth, A.S. Kechris, 
{\it Analytic equivalence relations and Ulm-type classifications,} 
{\bf Journal of Symbolic Logic,}  60 (1995), 1273--1300. 

\bibitem{hjorthkechris} G. Hjorth, A.S. Kechris, 
{\it New dichotomies for Borel equivalence relations,} 
{\bf Bulletin of Symbolic Logic,} vol.  3 (1997), 329--346.


\bibitem{jackson} S. Jackson, {\it A computation of $\ubf{\delta}^1_5$,}  
{\bf Memoirs of the American Mathematical Society,} vol. 140 (1999). 

\bibitem{jech} T. Jech, {\bf Set Theory,} Pure and Applied Mathematics. 
Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1978.

\bibitem{keisler} H.J. Keisler, 
{\bf Model theory for infinitary logic. Logic with countable conjunctions and finite quantifiers,} 
Studies in Logic and the Foundations of Mathematics, Vol. 62. North-Holland Publishing Co., Amsterdam-London


\bibitem{moschovakis} Y.N. Moschovakis, {\bf Descriptive Set Theory,} 
 Studies in Logic and the Foundations of Mathematics, 
 100. North-Holland Publishing Co., Amsterdam-New York, 1980. 




\end{thebibliography}

\leftskip 0.5in









\end{document} 


