This article concerns the study of equivalence relations on Polish spaces up to Borel reducibility. Given equivalence relations E and F on Polish spaces X and Y, respectively, a map $f\colon X\to Y$ is said to be a reduction of E to F if for any $x_1,x_2\in X$ ,

$$ \begin{align*} x_1\mathrel{E}x_2\iff f(x_1)\mathrel{F}f(x_2). \end{align*} $$

We say that E is Borel reducible to F, denoted ${E}\leq _B{F}$ if there is a Borel measurable function which is a reduction of E to F. In this case, we think of E as no more complicated than F. Borel reducibility is the most central concept in the study of equivalence relations on Polish spaces. Say that E and F are Borel bireducible, denoted $E\sim _B F$ , if $E\leq _B F$ and $F\leq _B E$ . We write $E<_B F$ (a strict reduction) if a Borel reduction exists in only that direction. An equivalence relation E on a Polish space X is Borel if E is a Borel subset of $X\times X$ , with the product topology.

A central motivation for the field is to study the complexity of various classification problems in mathematics. Generally speaking, separable mathematical objects can be coded as members of some Polish space. Natural notions of equivalence, such as isomorphism between countable graphs, isometry between separable metric spaces, or homeomorphism between compact metric spaces, can then be seen as equivalence relations on Polish spaces. These are generally analytic, and sometimes Borel. The focus on Borel measurable reductions is an attempt to consider only maps coming from “natural mathematical practice.” The particular choice of “Borel measurability” is strongly supported by theoretical and experimental evidence, as well as the success of the field since its inception with the papers [Reference Friedman and StanleyFS89, Reference Harrington, Kechris and LouveauHKL90]. For more background the reader is referred to the expository books [Reference GaoGao09, Reference KanoveiKan08], and the surveys [Reference ForemanFor18, Reference Hjorth and KechrisHK01, Reference KechrisKec02, Reference KechrisKec99, Reference Kechris and Tucker-DrobKTD12, Reference RosMR21].

Given equivalence relations $F_1, F_2$ on spaces $Y_1, Y_2$ respectively, define $F_1\times F_2$ on $Y_1\times Y_2$ as the pointwise relation: $(y_1,y_2), (y^{\prime }_1,y^{\prime }_2)\in Y_1\times Y_2$ are $F_1\times F_2$ -related if $y_1\mathrel {F_1}y^{\prime }_1$ and $y_2\mathrel {F_2}y^{\prime }_2$ .

In this note we provide a counterexample to the following conjecture, attributed to Zapletal in [Reference KanoveiKan08].

Conjecture 1 [Reference KanoveiKan08, Conjecture 14.1.6]

Let $X,Y$ be Polish spaces, $P\subseteq X\times Y$ a Borel set, F a Borel equivalence relation on X and E a Borel equivalence relation on P so that for any $(x,y),(x^{\prime },y^{\prime })\in P$ ,

$$ \begin{align*} (x,y)\mathrel{E}(x^{\prime},y^{\prime}) \implies x\mathrel{F}x^{\prime}. \end{align*} $$

Assume that G is a Borel equivalence relation so that for any $x_0\in X$ ,

$$ \begin{align*} E\restriction \left\{ (x,y)\in P :\, x\mathrel{F}x_0 \right\} \mathrel{\leq_B} {G}. \end{align*} $$

Then ${E}\mathrel {\leq _B}{F\times G}$ .

Roughly speaking, the conjecture says that if E extends F on the first coordinate, and on every fiber E is no more complicated than G, then E is no more complicated than $F\times G$ .

Two particularly important families of Borel equivalence relations are the smooth equivalence relations and the countable equivalence relations. (See [Reference GaoGao09, Chapters 5.4 and 7].)

An equivalence relation G is said to be smooth if G is Borel reducible to $=_{\mathbb {R}}$ , where $=_{\mathbb {R}}$ is the equality relation on the Polish space $\mathbb {R}$ . A Borel equivalence relation F on a Polish space Y is countable if each F-class is countable.

The motivation for this conjecture is as follows. The conjecture is true in the case where F is a countable Borel equivalence relation and G is smooth (see [Reference KanoveiKan08, Theorem 14.1.1]). This fact is essential in the proof of a dichotomy, due to Hjorth and Kechris [Reference Hjorth and KechrisHK01], for the equivalence relation $E_3$ (see [Reference KanoveiKan08, Chapter 14]).

Our counterexample will use the Friedman–Stanley jump, defined as follows. Given a space X, let $X^{\mathbb {N}}$ be the space of all sequence $x = \left ( x(n) :\, n\in \mathbb {N}\right ) $ , where $x(n) \in X$ , equipped with the product topology. If X is Polish, then $X^{\mathbb {N}}$ is Polish.

Definition 2 (Friedman–Stanley [Reference Friedman and StanleyFS89])

Let E be an equivalence relation on a Polish space X. Define $E^+$ on the space $X^{\mathbb {N}}$ by

$$ \begin{align*} x\mathrel{E^+}y \iff \forall n \exists m (x(n)\mathrel{E}y(m))\ \&\ \forall n \exists m (y(n) \mathrel{E} x(m)), \end{align*} $$

that is, $ \left \{ [x(n)]_E :\, n\in \mathbb {N} \right \} = \left \{ [y(n)]_E :\, n\in \mathbb {N} \right \} $ .

Note that if E is Borel, then $E^+$ is Borel. Friedman and Stanley proved the following (see [Reference GaoGao09, Theorem 8.3.6]).

Define F on $X = \mathbb {R}^{\mathbb {N}}$ by $ F = (=_{\mathbb {R}})^+$ . That is, $x\mathrel {F}y$ if x and y enumerate the same sets of reals.

Next we define the equivalence relation E. Let $2^{\mathbb {N}}$ be the space of binary sequences, given the product topology, where the set $2 = \{0,1\}$ is given the discrete topology. Consider the Polish space $\mathbb {R}^{\mathbb {N}} \times (2^{\mathbb {N}})^{\mathbb {N}}$ with the product topology. Given $(x,y)\in \mathbb {R}^{\mathbb {N}} \times (2^{\mathbb {N}})^{\mathbb {N}}$ , define $A^{(x,y)}_n = \left \{ x(m) :\, y(n)(m)=1 \right \} $ for $n\in \mathbb {N}$ . That is, we view each $y(n)$ as a binary sequence “carving out” a subset of the set enumerated by x.

$$ \begin{align*} \begin{array}{ccccc} \vdots & \vdots & \vdots & \vdots\\ {\color{yellow} \ast} & 1 & 0 & 1 & \ldots\\ {\color{green} \ast} & 1 & 1 & 0 & \ldots\\ {\color{red} \ast} & 0 & 1 & 1 & \ldots\\ {\color{blue} \ast} & 0 & 1 & 0 & \ldots\\ x & y(0) & y(1) & y(2) \end{array}\mapsto \begin{array}{cccc} \vdots & \vdots & \vdots\\ {\color{yellow} \ast} & - & {\color{yellow} \ast} & \ldots\\ {\color{green} \ast} & {\color{green} \ast} & - & \ldots\\ - & {\color{red} \ast} & {\color{red} \ast} & \ldots\\ - & {\color{blue} \ast} & - & \ldots\\ A^{(x,y)}_0 & A^{(x,y)}_1 & A^{(x,y)}_2 \end{array} \end{align*} $$

Define $P\subseteq \mathbb {R}^{\mathbb {N}} \times (2^{\mathbb {N}})^{\mathbb {N}}$ as the set of all $(x,y)$ such that:

1. (1) $\forall m\exists k (y(k)(m)=1)$ ;

2. (2) $\forall k \exists m (y(k)(m)=1)$ ;

3. (3) $\forall k,l_1,l_2(x(l_1)\mathrel {=}{}x(l_2)\rightarrow y(k)(l_1)=y(k)(l_2))$ .

That is: (1) each $x(m)$ appears in $A^{(x,y)}_k$ for some k, (2) each $A^{(x,y)}_k$ is not empty, and (3) if x enumerates the same item twice, on indices $l_1$ and $l_2$ , then each binary sequence $y(k)$ agrees on $l_1$ and $l_2$ . Note that P is a Borel set. In fact it is a dense $G_\delta $ subset of $\mathbb {R}^{\mathbb {N}} \times (2^{\mathbb {N}})^{\mathbb {N}}$ .

Finally, we define an equivalence relation E on P by

$$ \begin{align*} (x,y) \mathrel{E} (x^{\prime},y^{\prime}) \iff \left\{ A^{(x,y)}_n :\, n\in\mathbb{N} \right\} = \left\{ A^{(x^{\prime},y^{\prime})}_n :\, n\in\mathbb{N} \right\} , \end{align*} $$

that is, $(x,y)$ and $(x^{\prime },y^{\prime })$ code the same sets of subsets of $\mathbb {R}$ . Note that E is Borel.

Remark 4 For $(x,y)\in P$ , property (1) in the definition of P implies that $ \left \{ x(m) :\, m\in \mathbb {N} \right \} = \bigcup \left \{ A^{(x,y)}_n :\, n\in \mathbb {N} \right \} $ . It follows that E and F satisfy the property

$$ \begin{align*} (x,y)\mathrel{E}(x^{\prime},y^{\prime}) \implies x\mathrel{F}x^{\prime}. \end{align*} $$

Let $=_{2^{\mathbb {N}}}$ be the equality relation on $2^{\mathbb {N}}$ , and let $G = (=_{2^{\mathbb {N}}})^+$ . Note that G and F are Borel bireducible (as there is a Borel bijection between $\mathbb {R}$ and $2^{\mathbb {N}}$ , see [Reference GaoGao09, Corollary 1.4.3]).

Claim 5 For any $x_0\in \mathbb {R}^{\mathbb {N}}$ ,

$$ \begin{align*} E\restriction \left\{ (x,y)\in P :\, x\mathrel{F}x_0 \right\} \mathrel{\leq_B} {G}. \end{align*} $$

Proof Fix $x_0\in \mathbb {R}^{\mathbb {N}}$ . Define $f\colon \left \{ (x,y)\in P :\, x\mathrel {F}x_0 \right \} \to (2^{\mathbb {N}})^{\mathbb {N}}$ by

$$ \begin{align*} \begin{split} f(x,y)(n)(k) = i & \iff (\forall k^{\prime}\in\mathbb{N})(x(k^{\prime})=x_0(k) \implies y(n)(k^{\prime})=i) \\ & \iff (\exists k^{\prime}\in \mathbb{N})(x(k^{\prime})=x_0(k) \wedge y(n)(k^{\prime})=i). \end{split} \end{align*} $$

The equivalence between the definitions above follows from clause (3) in the definition of P. Note that $f(x,y)(n)(k)$ is well defined by clause (2).

What f does is the following. The F-class of $x_0$ are all sequences which enumerate the same set as $x_0$ . Using a fixed enumeration of this set, via $x_0$ , we code subsets of it, $A^{(x,y)}_n$ , as binary sequences by identifying k with $x_0(k)$ . In particular, $f(x_0,y) = y$ for $(x_0,y)\in P$ . We claim that f is a reduction of $E\restriction \left \{ (x,y)\in P :\, x\mathrel {F}x_0 \right \} $ to G.

The main point is the following. Given $(x,y), (x^{\prime },y^{\prime })\in P$ with $x\mathrel {F} x_0 \mathrel {F} x^{\prime }$ ,

$$ \begin{align*} (\star)\hspace{5mm} \forall n,m\in\mathbb{N}\, (A_n^{(x,y)} = A_m^{(x^{\prime},y^{\prime})} \iff f(x,y)(n) = f(x^{\prime},y^{\prime})(m)). \end{align*} $$

This implies that $(x,y)\mathrel {E}(x^{\prime },y^{\prime }) \iff f(x,y)\mathrel {G}f(x^{\prime },y^{\prime })$ , and so f is the desired reduction.

To see $(\star )$ , assume first that $A_n^{(x,y)} = A_m^{(x^{\prime },y^{\prime })}$ . For each $k\in \mathbb {N}$ fix $k_1, k_2$ so that $x(k_1) = x_0(k) = x^{\prime }(k_2)$ . Then

$$ \begin{align*} f(x,y)(n)(k) = y(n)(k_1) = y^{\prime}(m)(k_2) = f(x^{\prime},y^{\prime})(m)(k), \end{align*} $$

where the middle equality follows from clause (3) in the definition of P and the assumption $A_n^{(x,y)} = A_m^{(x^{\prime },y^{\prime })}$ . We conclude that $f(x,y)(n) = f(x,y)(m)$ .

Next, assume that $f(x,y)(n) = f(x^{\prime },y^{\prime })(m)$ . For any $k_1$ so that $y(n)(k_1) = 1$ (and so $x(k_1)\in A_n^{(x,y)}$ ) we show that $x(k_1)\in A_m^{(x^{\prime },y^{\prime })}$ . Fix $k,k_2$ so that $x(k_1) = x_0(k) = x^{\prime }(k_2)$ . Then

$$ \begin{align*} y^{\prime}(m)(k_2) = f(x^{\prime},y^{\prime})(m)(k) = f(x,y)(n)(k) = y(n)(k_1) = 1, \end{align*} $$

and so $x(k_1) = x^{\prime }(k_2) \in A_m^{(x^{\prime },y^{\prime })}$ . It follows that $A_n^{(x,y)} \subseteq A_m^{(x^{\prime },y^{\prime })}$ . By symmetry we also get $A_m^{(x^{\prime },y^{\prime })} \subseteq A_n^{(x,y)}$ , and so $A_n^{(x,y)} = A_m^{(x^{\prime },y^{\prime })}$ .

We include a proof that $((=_{\mathbb {R}})^+)^+ \leq _B E$ , which we use below. The idea is simple. Given $z\in (\mathbb {R}^{\mathbb {N}})^{\mathbb {N}}$ , each $z(n)\in \mathbb {R}^{\mathbb {N}}$ codes a subset of $\mathbb {R}$ . We will send z to a pair $(x,y)\in P$ so that x enumerates the set of all reals appearing in the sets $z(n)$ , and $y(n)$ carves out the subset $z(n)$ of x.

Fix a bijection $e\colon \mathbb {N}\times \mathbb {N}\to \mathbb {N}$ . Define $x(e(i,j)) = z(i)(j)$ . Define $y(n)(e(i,j)) = 1$ if there is some k so that $z(n)(k) = z(i)(j)$ , and $y(n)(e(i,j))=0$ otherwise. The map $z\mapsto (x,y)$ is a Borel reduction of $((=_{\mathbb {R}})^+)^+$ to E.

We will also use the well known fact that $(=_{\mathbb {R}})^+ \times (=_{\mathbb {R}})^+ \sim _B (=_{\mathbb {R}})^+$ . For the non-trivial direction, fix an injective Borel map $\iota \colon \mathbb {R}\times \{0,1\} \to \mathbb {R}$ and consider the map sending $(x,y)\in \mathbb {R}^{\mathbb {N}} \times \mathbb {R}^{\mathbb {N}}$ to $z\in \mathbb {R}^{\mathbb {N}}$ so that $z(2n) = \iota (x(n),0)$ and $z(2n+1) = \iota (y(n),1)$ . Then $(x,y)\mapsto z$ is is a Borel reduction of $(=_{\mathbb {R}})^+ \times (=_{\mathbb {R}})^+$ to $(=_{\mathbb {R}})^+$ .

Now Conjecture 1 would imply that $E \leq _B F \times G$ , and so

$$ \begin{align*} ((=_{\mathbb{R}})^+)^+ \leq_B E \leq_B F \times G \leq_B (=_{\mathbb{R}})^+ \times (=_{\mathbb{R}})^+ \leq_B (=_{\mathbb{R}})^+, \end{align*} $$

a contradiction, as $((=_{\mathbb {R}})^+)^+ \not \leq _B (=_{\mathbb {R}})^+$ by Fact 3.