4
$\begingroup$

Let $X$ and $Y$ be standard Borel spaces: topological spaces homeomorphic to Borel subsets of complete metric spaces. Given a surjective Borel map $f:X\to Y$, we get an equivalence relation $\sim_f\subseteq X^2$ given by $x\sim_fx'$ iff $f(x) = f(x')$. Since $\sim_f = (f\times f)^{-1}(\Delta_Y)$ where $\Delta_Y$ is the diagonal of $Y$, we obtain that $\sim_f$ is a Borel subset of $X$.

Now, let $\sim$ be any other equivalence on $X$ which is a Borel subset of $X^2$. Does there always exist a Borel space $Z$ and a Borel map $g:X\to Z$ such that $\sim = \sim_g$? Can we take $g$ to be surjective in such case? What conditions on $\sim$ are sufficient to ensure that $g$ can be chosen to be surjective?

If we could define a topological structure on $X/\!_\sim$ which turns it into a Borel space, then a natural projection $\pi:X\to X/\!_\sim$ would be a desired map $g$.

  1. I think that if we endow $X/\!_\sim$ with the $\pi$-quotient topology, then will turn to be an analytic space, but not Borel in general. Is that correct? In such case, perhaps we can can take $Z$ being a one-point compactification of $X/\!_\sim$, though $g = \pi$ would fail to be surjective in such case.

  2. If endowing with the quotient topology only leads to analytic spaces, can we still introduce some different topology on $X/\!_\sim$ so that it becomes a Borel space and $\pi$ is a Borel map?

Edited: as Joel pointed out in his answer, the existence of $(g,Z)$ is equivalent to $\sim$ being smooth, that is there exists a Borel reduction from $\sim$ to $\mathrm{id}_Z$.

Kechris in his book "Classical Descriptive Set Theory" provides sufficient conditions for the smoothness in (18.20) such as existence of a Borel selector, or $\sim$ being a closed subset of a Polish space. Here by a selector is meant a map $h:X\to X$ such that $x\sim h(x)$ and $x\sim x'$ implies $h(x) = h(x')$.

The existence $(g,Z)$ with surjective $g$ is a stronger version of smoothness requiring the existence of a surjective Borel reduction. Existence of a Borel selector of $\sim$ implies the existence such a reduction. The book of Kechris, e.g. (12.16), provides sufficient conditions for the existence of a Borel selector. The existence of surjective $g$ does not necessarily imply the existence of a Borel selector (see my comment to the OP).

The procedure via the quotient topology in 1. may not work in some cases as to be analytic, $X/\!_\sim$ needs not only to be a quotient of a Borel space, but also countably separated.

$\endgroup$
5
  • $\begingroup$ Could you clarify your statement in the second-to-last paragraph? Does Kechris prove that the existence of a surjective reduction to $=$ is equivalent to having a Borel selector? Your statement about sufficiency suggests that he proves only one direction. $\endgroup$ Jul 18, 2014 at 14:52
  • $\begingroup$ @JoelDavidHamkins: hopefully I've made it less confusing. Statement regarding sufficiency is about sufficient conditions for the existence of a Borel selector. For equivalence of surjective reduction and existence of Borel selectors: the latter implies existence of a Borel transversal which we can take as $Z$. I think the former implies the latter, but I'm still working the proof - so "apparently" so far. Any doubts regarding that statement? $\endgroup$
    – SBF
    Jul 18, 2014 at 15:09
  • $\begingroup$ I see. By "apparently", you mean that you think this equivalence is true, but so far don't have a proof? OK. $\endgroup$ Jul 18, 2014 at 15:11
  • $\begingroup$ @JoelDavidHamkins: indeed, that's what I mean. I've updated this phrase again to avoid confusion. $\endgroup$
    – SBF
    Jul 18, 2014 at 15:31
  • $\begingroup$ @JoelDavidHamkins: my hypothesis that existence of a surjective $g$ implies existence of a Borel selector is not correct. If such a surjection $g$ exists, and there is a Borel selector $h:X \to X$ for $\sim_g$, then $h$ is $g$-measurable, and hence it factors through $g$ as $h = s\circ g$ where $s:Z\to X$ is Borel. The fact that $s\circ g$ is a Borel selector for $\sim_g$ is equivalent to $g\circ s = \mathrm{id}_Z$, and according to your answer such $s$ may fail to exist. $\endgroup$
    – SBF
    Jul 20, 2014 at 17:48

1 Answer 1

3
$\begingroup$

The answer is no, and this kind of question is part of the subject of the theory of Borel equivalence relations.

The equivalence relations $\sim$ for which there is a Borel function $g:X\to Z$ into a standard Borel space $Z$, with $x\sim y\iff g(x)=g(y)$ are, by definition, precisely the smooth equivalence relations (see the definition on page 5 of the link above). But there are equivalence relations that are not smooth, such as the relation $E_0$ of eventual equality of infinite binary sequences. You can find the arguments that various relations are not smooth in the article to which I linked; see also page 5 of these notes of Simon Thomas and Scott Schneider; my favorite proof of this uses forcing (one adds a Cohen real, and sees where it maps in the extension, and then argues that that image real must be already in the ground model, which is impossible).

The subject of Borel equivalence relations studies the entire hierarchy of Borel equivalence relations under Borel reducibility, which is a kind of complexity notion that in effect analyzes the relative difficulty of classification problems in mathematics, and the smooth equivalence relations occupy a region near the very bottom of the hierarchy, among the simplest relations.

$\endgroup$
14
  • $\begingroup$ Thank you, could you suggest then what is incorrect in my construction of $Z$ via a one-point compactification of $X/\!_\sim$ endowed with a quotient topology? Also, do I understand this correctly - if $\sim$ is smooth, still there may not be a surjective version of $g$? $\endgroup$
    – SBF
    Jul 18, 2014 at 12:57
  • $\begingroup$ In general, I don't think your quotient space is a standard Borel space (and the strategy cannot work for non-smooth relations). Regarding surjective maps, I'm not sure, but perhaps one of the Borel ER experts here on MO can answer. To my way of thinking, the general question here would be: suppose $E\leq_B F$ is a Borel reduction of equivalence relation $E$ on $X$ to $F$ on $Y$. When is there a surjective Borel reduction of $E$ to $F$? $\endgroup$ Jul 18, 2014 at 13:15
  • $\begingroup$ The quotient space is not Borel, but I thought it is analytic, then we could take $Z$ being any Borel superset of $X/\!_\sim$. Anyways, let me think of your formulation regarding surjectivity - I'll also check what's in Kechris on Borel ERs, maybe 18.20 is of help here. Can you update the link to notes of Thomas and Schneider, please? Currently it opens Hjorth's notes. I've edited the link, so just wanted to be sure that's the one you've meant. $\endgroup$
    – SBF
    Jul 18, 2014 at 13:23
  • $\begingroup$ Yes, that's it, and I've approved your edit. $\endgroup$ Jul 18, 2014 at 13:35
  • $\begingroup$ In Kechris, a selector of $\sim$ is $h:X\to X$ such that $h(x)\sim x$ and such that $x\sim x'$ implies $h(x) = h(x')$. I guess, the existence of a Borel selector is exactly the existence of a surjective Borel reduction. There are some sufficient conditions in the book, and it may be easier to look for other using this terminology. $\endgroup$
    – SBF
    Jul 18, 2014 at 14:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.