% 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{A selection theorem for treeable sets\footnote{Key words and phrases: Borel equivalence relations, treeable equivalence relation, selection theorem, uniformization. 2000 Mathematics Subject Classification: Primary 03E15} } \maketitle \abstract{A smooth treeable equivalence relation admits a selector; an essentially countable treeable equivalence relation admits a Borel section meeting each class in a countable non-empty set.} \section{Introduction} In the literature of Borel equivalence relations, treeable equivalence relations have largely been studied in the context of a countable vertex set. The purpose of this brief note is to extract the definition from that narrow context, and consider how the notion behaves when we allow trees with possibly uncountable splitting. \begin{definition} A set $A$ in a Polish space is {\it treeable} if there is a Borel $R\subset A\times A$ such that provides the structure of a tree -- which is to say, $R$ is symmetric and irreflexive, connected, and without cycles. In this paper it is convenient to use the notions of effective descriptive set theory, in the sense of \cite{moschovakis}, and naturally enough, we say that the treeing is $\Delta^1_1(x)$ if $R\in \Delta^1_1(x)$. \end{definition} \begin{theorem} \label{theorem} Let $x\in 2^\omega$, $A\subset 2^\omega$ in $\Sigma^1_1(x)$, $A$ non-empty and $\Delta^1_1(x)$ treeable. Then $A\cap\Delta^1_1(x)$ is non-empty. \end{theorem} \begin{definition} An equivalence relation $E$ on a Polish space $X$ is {\it treeable} if there is a Borel $R\subset X\times X$ which provides a forest whose connected components are the $E$-classes -- that is to say, $R$ is symmetric and irreflexive, without cycles, and $xEy$ if and only if there is a sequence $x_0=x, x_1,..., x_n=y$ with each $(x_i, x_{i+1})\in R$. An equivalence relation $E$ is {\it smooth} if there is a Borel function $\theta$ from $X$ to some Polish space with \[x_1 E x_2\] if and only if $\theta(x_1)=\theta(x_2)$. An equivalence relation $E$ is {\it essentially countable} if and only if there is a Borel function $\theta$ from $X$ to some Polish space $Y$, equipped with a Borel equivalence relation $F$ all of whose classes are countable, such that \[x_1 E x_2\] if and only if $\theta(x_1) F \theta(x_2)$. \end{definition} Note that any treeable equivalence relation $E$ is necessarily Borel, since there will be a unique loopless path connecting $x$ to $y$ if they are equivalent, and we can apply the theorem on the projection of Borel sets in the plane with countable sections (see 18.10 \cite{kechris}). \begin{corollary} \label{corollary1} If $E$ is treeable and smooth, then there is a Borel selector -- that is to say, a Borel set meeting each equivalence class in exactly one point. \end{corollary} \begin{corollary} \label{corollary2} If $E$ is treeable and essentially countable, then there is a Borel set meeting each equivalence class in a countable non-empty set. \end{corollary} The proof of \ref{corollary1} from \ref{theorem} is short. We may assume $E$ lives on $2^\omega$ and there is some single $y\in 2^\omega$ such that the indicated $\theta$ and $R$ are in $\Delta^1_1(y)$. We may also assume $\theta: 2^\omega\rightarrow 2^\omega$. Then for any $z\in 2^\omega$ we can let $S(z)$ be the first element, in some canonical enumeration of $\Delta^1_1(\theta(z), y)$ which meets $[z]_E$. By \ref{theorem}, such exists. It depends only on $\theta(z)$, and hence only on $[z]_E$. I leave to the reader the routine, though tedious, verification $z\mapsto S(z)$ is Borel. The proof of \ref{corollary2} is entirely parallel. Given $\theta$ as indicated, we again define $S(z)$ to be the first element of $\Delta^1_1(\theta(z), y)$ which meets $[z]_E$. Since \[\{S(z'): z'E z\}\] is always countable, the set $\{S(z): z\in 2^\omega\}$ will meet each class in a {\it countable} non-empty set. We give the proof of \ref{theorem} in the next section. In the final section we observe that a treeable equivalence relation induced by the continuous action of a Polish group is essentially countable -- answering a question raised in \cite{hjorth}. \section{proof} We make use of the language and armory of {\it Gandy-Harrington forcing}. \def\p{{\cal P}} \begin{notation} Let $\p$ denote the partial order of non-empty $\Sigma^1_1$ subsets of $2^\omega$ ordered under inclusion and let $\p_2$ denote the partial order of non-empty $\Sigma^1_1$ subsets of $2^\omega\times 2^\omega$ likewise ordered under inclusion \end{notation} The reader should refer to \cite{sacks} or \cite{hakelo} for a proof of the following.\footnote{As a forewarning on terminology \cite{sacks} drops credit to Harrington and calls $\p$ {\it Gandy forcing} while \cite{hakelo} uses the {\it Gandy-Harrington topology}, recasting the results in the language of topological spaces and the Baire category theorem.} \begin{proposition} \label{projection} (1) If $G\subset \p$ is sufficiently generic filter, then there will be a unique element in \[\bigcap G.\] (2) If $G\subset \p_2$ is $V$-generic, then there will be unique $V$-generic $G_\ell, G_r\subset \p$ with \[G\subset G_\ell\times G_r.\] \end{proposition} \begin{notation} For $G$ a sufficiently generic filter on $\p$, $x(G)$ denotes the unique real in its intersection. For $G\subset G_\ell\times G_r$ as above, \[x_r(G) =x(G_r),\] \[x_\ell (G)=x(G_\ell).\] We will also at times have need to consider the product forcing, \[\p\times\p.\] Then for any $V$-generic $G\subset \p\times\p$ it is a standard fact for product forcing that there are $V$-generic $G_\ell, G_r\subset \p$ with $G=G_\ell\times G_r$, whence we again let $x_r(G) =x(G_r), x_\ell (G)=x(G_\ell)$. \end{notation} \begin{lemma} \label{compute} If $B\in \p$, $y\in 2^\omega$, \[B\Vdash y\in \Delta^1_1(x(\dot{G})),\] then $y\in \Delta^1_1$. \end{lemma} \def\xg{x(\dot{G})} \def\xgr{x_r(\dot{G})} \def\xgl{x_\ell (\dot{G})} \begin{proof} We can find $A\in\Sigma^1_1$ and refine $B$ to $B'\in \p$ such that \[B'\Vdash \{z: (z, \xg)\in A\}=\{y\}.\] Then for all $n$ \[y(n)=0\] if and only if there exists \[(z, a)\in A\] with \[z(n)=0.\] Thus $y$ is a $\Sigma^1_1$ singleton, and hence $\Delta^1_1$ as required. \end{proof} Similarly: \begin{lemma} \label{compute2} If $B\in \p_2$ and \[B\Vdash_{\p_2} y\in \Delta^1_1(\xgl, \xgr),\] then $y\in\Delta^1_1$. \end{lemma} With these weapons in hand, we can start on the proof of the theorem. For notational convenience let us in fact assume $A\in \Sigma^1_1$ and $R\in \Delta^1_1$. The general case relativizes without disruption, simply because the relevant facts for $\p$ and $\p_2$ carry through to their relativized versions. The statement that $R$ provides a treeing of $A$ is easily checked to be $\Pi^1_2$ and hence absolute to generic extensions. We will assume that $A\cap \Delta^1_1$ is empty and fight our way through to a contradiction. \begin{definition} We say that $y\in A$ is {\it critical} if there exist $B_0, B_1\in \p$ below $A$ with $(B_0, B_1)$ forcing the shortest path in $R$ from $\xgl$ to $\xgr$ passes through $y$. \end{definition} \begin{lemma} \label{1} There are only countably many critical reals. \end{lemma} \begin{proof} If $y$ is critical, then any sufficiently generic $G\subset \p\times\p$ below the relevant $(B_0, B_1)$ has $y\in \Delta^1_1(G)$. Since $\p\times\p$ exists up to isomorphism in $L_{\omega_2^{\rm ck}}$, any such $y$ will be in the countable set \[L_{\omega_1^{\rm ck}}[G].\] \end{proof} \begin{notation} For $x, y\in A$ let $f(x, y)$ denote the first element after $x$ in the shortest $R$-path from $x$ to $y$ and let $l(x, y)$ denote the last element before $y$. \end{notation} $f(x, y)$ and $l(x, y)$ will be well defined when $x\neq y$ by our assumption of $R$ treeing $A$. Our assumption that $A\cap\Delta^1_1=0$ entails that for any $y$ and $B\leq A$ \[B\Vdash f(y, \xg) {\rm \: well \: defined.}\] \begin{lemma} \label{2} There exists a critical real. \end{lemma} \begin{proof} Otherwise choose $y_0\in A$ arbitrary. By our supposition of the lemma failing, we have for all $B_0, B_1\in \p$ below $A$ and $C$ Borel, \[B_0\Vdash f(y_0,\xg)\in C\] if and only \[B_1\Vdash f(y_0, \xg)\in C.\] Varying over all possible $C$, we obtain some $y_1$ such that \[A\Vdash f(y_0, \xg)=y_1.\] Repeating the same consideration round after round, we obtain a sequence of adjacent points, $y_0, y_1, y_2,...$ with at each $i$ \[A\Vdash f(y_i, \xg)=y_{i+1}.\] This at last pushes $\xg$ to be infinitely far away from $y_0$, and a contradiction on $R$ treeing $A$ in the generic extension. \end{proof} \begin{notation} Let $T_0$ be the convex hull of the critical points; in other words, $T_0$ is the smallest subtree of $(A, R)$ containing all the critical points. $T_0$ is again countable. For $y\in A$ let \[c(y)\] be the closest point in $T_0$ to $y$. In the case $y\notin T_0$ we let \[s(y)=l(y, c(y)).\] For $y\in T_0$ we just let $s(y)=y$, though this case will have only nominal interest for us. \end{notation} Hence $s(y)$ is the last non-critical point on the path from $y$ back to the convex closure of the set of critical points. \begin{notation} For $y_0, y_1\in A$ set \[y_0 E y_1\] if $s(y_0)=s(y_1)$. \end{notation} \begin{lemma} \label{3} \[(A, A) \Vdash_{\p\times \p} \xgl \!\!\not\! \! E \xgr.\] \end{lemma} \begin{proof} Otherwise we could find some single $y_1\notin T_0$ and $B\leq A$ with \[B\Vdash_\p s(\xg)=y_1.\] Then since $y_1$ is {\it not} critical, \[(B, B)\Vdash_{\p\times\p} l(\xgl, y_1)=l(\xgr, y_1).\] Continuing in the same manner we find $y_2, y_3, y_4,...$ such that at each $i$, \[B\Vdash_\p l(\xg, y_i)=y_{i+1},\] with the same contradiction as in \ref{2}. \end{proof} \begin{lemma} \label{4} \[A\times A\Vdash_{\p_2} \xgl E \xgr.\] \end{lemma} \begin{proof} Or else we obtain some $B\leq A\times A$ and some $y_0\in T_0$ with $B$ forcing the least path from $\xgl$ to $\xgr$ passing through $y_0$, which gives $y_0$ by \ref{compute2}, and a contradiction to our assumption $A\cap \Delta^1_1=0$. \end{proof} Now events really do screech into contradiction. From \ref{3} we can find some $B_0, B_1\leq A$ and Borel $C$ with \[B_0\Vdash_\p \xg\in C,\] \[B_1\Vdash_\p \xg\notin C,\] yielding \[B_0\times B_1\Vdash \xgl\in C, \xgr\notin C\] from projection, in violation of \ref{4}. \section{An after thought on Polish group actions} We need a couple of notions from the theory of Borel reducibility. \cite{hjorthkechris} is one place where more background can be found. \begin{definition} An equivalence relation $E$ on Polish $X$ is essentially countable if there is a Borel equivalence relation $F$ on Polish $Y$ with all its classes countable and $E\leq_B F$ -- which is to say, for some Borel $\theta: X\rightarrow Y$ \[x_0 E x_1\Leftrightarrow \theta(x_0) F \theta(x_1).\] \end{definition} From now on assume that $E$ is a treeable equivalence relation arising from the continuous action of a Polish group $G$ on a Polish space $X$, so that $x_1 E x_2$ if and only if \[\exists g\in G(g\cdot x_1 =x_2).\] Let $R$ be the Borel treeing. We will work towards showing $E$ essentially countable. \begin{notation} For $V\subset G$ open and \[\forall^*g\in V(...g...)\] indicates that for a relatively comeager collection of $g\in V$ we have $(...g...)$. \end{notation} \begin{notation} For $x_1 E x_2$, let $p(x_1, x_2)$ denote the shortest $R$-path from $x_1$ to $x_2$. \end{notation} \begin{lemma} \label{path} For all $x\in X$ there exists non-empty open $V_0, V_1, W_0, W_1\subset G$ such that $\forall^*g_0\in V_0\forall^* g_1\in V_1\forall^*h_0\in W_0\forall^* h_1\in W_1$ \[p(g_0\cdot x, h_0\cdot x) {\rm \: intersects \:} p(g_1\cdot x, h_1\cdot x).\] \end{lemma} \begin{proof} Assuming failure of the lemma we get that for a comeager collection of $(g_0, g_1, h_0, h_1)\in G^4$ \[p(g_0\cdot x, h_0\cdot x) {\rm \: does \: not \: intersect \:} p(g_1\cdot x, h_1\cdot x).\] Taking sufficiently generic choices of these group elements can find $x_0=g_0\cdot x, x_1=g_1\cdot x$ and $y_0=h_0\cdot x, y_1=h_1\cdot x$ such that $p(x_i, y_j)$ does not intersect $p(x_l, y_k)$ ($i, j, l, k\in \{0, 1\}$) when $i\neq l$ and $j\neq k$. Let $x_0'$ be the last common point on $p(x_0, y_0)$, $p(x_0, y_1)$. Similarly take $x_1'$ to be the last common point on $p(x_1, y_0)$, $p(x_1, y_1)$, $y_0'$ the last common point on $p(y_0, x_0)$, $p(y_0, x_1)$, and $y_1'$ the last common point on $p(y_1, x_0)$, $p(y_1, x_1)$. Then we have a cycle obtained by adjoining \[p(x_0', y_0')^\smallfrown p(y_0', x_1')^\smallfrown p(x_1', y_1')^\smallfrown p(y_1', x_0'),\] with a nasty rebuttal of our assumption that $R$ was a treeing. \end{proof} \begin{corollary} \label{path2} For all $x\in X$ there exists non-empty open $V, W\subset G$ such that $\forall^*(g_0, g_1)\in V^2\forall^*(h_0, h_1)\in W^2$ \[p(g_0\cdot x, h_0\cdot x) {\rm \: intersects \:} p(g_1\cdot x, h_1\cdot y).\] \end{corollary} \begin{proof} Referring back to \ref{path}, take $V, V', W, W'$ to be non-empty open subsets of $V_0, V_1, W_0, W_1$ such that for some $m, n$ $\forall^* g\in V \forall^* g'\in V'\forall^*h\in W\forall^* h'\in W'$ we have the $n^{\rm th}$ element of $p(g\cdot x, h\cdot x)$ equals the $m^{\rm th}$ element of $p(g'\cdot x, h'\cdot x)$. Then $V$ and $W$ are as required. \end{proof} \begin{definition} For $V, W\subset G$ basic open and non-empty, $x\in X$, $y\in [x]_E$, we say that $(V, W, x)$ {\it conquers} $y$ if $\forall^*g\in V\forall^*h\in W$ the point $y$ appears somewhere along $p(g\cdot x, h\cdot x)$. It follows from \ref{path2} that for every $x$ there will be some $y, W, V$ with $(V, W, x)$ conquering $y$. We let $T_x$ be the convex hull of the set of points \[\{y\in [x]_E: \exists V, W((V, W, x) {\rm \: conquers} \: y)\}.\] \end{definition} \begin{lemma} $T_x$ is always a countable non-empty set. \end{lemma} \begin{proof} Non-empty by the last lemma and countable by the second countability of $G$. \end{proof} \begin{lemma} If $x_0 E x_1$ then $T_{x_0}=T_{x_1}$. \end{lemma} \begin{proof} Since if $(V_0, W_0, x_0)$ conquers $y$ then we can choose non-empty basic open $V_1, W_1$ with \[V_1\cdot x_1\subset V_0\cdot x_0,\] \[W_1\cdot x_1\subset W_0\cdot x_0.\] \end{proof} \begin{lemma} The set of $x$ with $x\in T_x$ is Borel. \end{lemma} \begin{proof} Let $B\subset X\times X$ be the set of $(x, y)$ for which there exists $V, W$ with $(V, W, x)$ conquering $y$. Since the assignment \[(x, g, h)\mapsto p(g\cdot x, h\cdot x)\] is Borel as a function from $X$ to $X^{<\infty}$, it follows from the preservation of Borel sets under the categoricity quantifiers $\forall^*, \exists^*$ (see 16.1 \cite{kechris}) that $B$ is Borel. $x\in T_x$ if and only if there are $y_0, y_1$ with $(x, y_0), (x, y_1)\in B$ and the unique shortest $R$-path from $y_0$ to $y_1$ passes through $x$. We finish by using that the projection of a Borel set in the plane with countable sections is Borel. \end{proof} \begin{lemma} There is a Borel function \[x\mapsto \theta(x)\] such that $\theta(x)\in T_x$. \end{lemma} \begin{proof} By the uniformization of Borel sets with countable sections. \end{proof} Finally we let $X_0=\{x: x\in T_x\}$. We have seen this is a Borel subset of $X$, and hence a standard Borel space in its own right, and thus allowing a compatible topology under which it is Polish (see 13.4 \cite{kechris}). The lemmas above established that $E$ has countable classes when restricted to $X_0$ and $\theta$ witnesses $E\leq_B E|_{X_0}$. The ebullient conjectures of \cite{hjorthkechris} suggest the following: \begin{question} Let $E$ be treeable. Must it be the case that either: \leftskip 0.4in \noindent (I) $E$ essentially countable, or \noindent (II) $E_1\leq_B E$? \leftskip 0.4in \end{question} \begin{thebibliography}{99} \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{hjorth} G. Hjorth, {\it Non-treeability for product group actions,} to appear in the {\bf Israel Journal of Mathematics.} \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{jakelo} S. Jackson, A.S. Kechris, A. Louveau, {\it Countable Borel equivalence relations,} {\bf Journal of Mathematical Logic,} vol. 2 (2002), 1--80. \bibitem{kechris} A.S. Kechris, {\bf Classical Descriptive Set Theory,} Springer-Verlag, New York, 1995. \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. \bibitem{sacks} G.E. Sacks, {\bf Higher recursion theory,} Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1990. \end{thebibliography} \leftskip 0.5in \end{document}