% 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: mN} \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}