6
$\begingroup$

It is known from metric space topology that a closed equivalence relation on a Polish space has either countably many or $\mathfrak{c}$ many equivalence classes.

A short elementary proof is given in Srivastava "A course on Borel sets", Theorem 2.6.7. This proof does not proceed through a Borel or analytic cross section for the equivalence relation. Is it possible that a closed equivalence relation can have no analytic cross section?

(A "cross section", or "transversal", is a set with exactly one point in each equivalence class. An equivalence relation on a space $X$ is "closed" if it is a closed subset of the product space $X\times X$.)

Several results asserting the existence of a Borel or analytic cross section assume additional conditions, such as requiring the equivalence classes to be closed, for example.

The stated theorem is a particular instance of a much deeper theorem of J. Silver: every coanalytic equivalence relation has either countably many or $\mathfrak{c}$ many equivalence classes. For a proof, see Jech "Set Theory", 3rd ed. 2002/2006, Chapter 32.

$\endgroup$
9
$\begingroup$

The answer to this question is found, for example, in Su Gao's book Invariant Descriptive Set Theory. In exercise 5.4.6 an outline is given for an example of a closed equivalence relation with no Borel selector. (A selector is a map $s\colon X\to X$ such that $s(x)\mathrel{E}x$ and $x\mathrel{E}x'\implies s(x)\mathrel{E}s(x')$. On page 87 it is explained that if $E$ is Borel then having a Borel selector is equivalent to having a Borel transversal, i.e. cross-section). For completeness, here is the statement of exercise 5.4.6.

Let $F$ be a closed subset of $\omega^\omega\times\omega^\omega$ such that the set $\{x:\exists y(x,y)\in F)\}$ is analytic and not Borel. Let $X=F$ and define the equivalence relation $E$ on $X$ by $(x,y)\mathrel{E}(x',y')\iff x=x'$. Then $E$ is closed and has no Borel selector.

$\endgroup$
6
$\begingroup$

There is a recursion theory method which is quite similar to Samuel's.

By a classical recursion theory result, there is a recursive functional $F$ so that for any $x\in \omega^{\omega}$, $F(x)$ codes an $x$-recursive tree $T\subseteq \omega^{<\omega}$ so that $[T]$ has an infinite path but no infinite path hyperarithmetic in $x$. Then let $(x_0,y_0)E(x_1,y_1)$ if $x_0=x_1$ and $y_0,y_1\in F(x)$. Then $E$ is a $\Pi^0_1$-equivalence relation and has no $\mathbf{\Sigma}^1_1$-cross section.

Note that the non-compactness plays an important role here. Otherwise, you can't find a counter example.

$\endgroup$
3
$\begingroup$

Shashi Srivastava suggests taking the equivalence relation on $\omega^\omega$ induced by a continuous $f:\omega^\omega\to \omega^\omega$ with non-Borel range. This is a closed equivalence relation with no Borel cross-section.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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