5
$\begingroup$

What do we know about the complexity of the theory of Borel equivalence relations, with the Borel reducibility order $\leq_B$?

That is, let $\mathcal{B}$ be the set of all Borel equivalence relations on your favorite uncountable Polish space, modulo bireducibility. What is the complexity of the first order theory of $(\mathcal{B},\leq_B)$? Is it known to be undecidable?

A result of Louveau-Velickovic (A note on Borel Equivalence Relations, PAMS, 1994) shows that $(\mathcal{P}(\omega),\subseteq^*)$ embeds into $(\mathcal{B},\leq_B)$, and thus so does any partial order of size $\leq\aleph_1$. Does this provide an answer to my question?

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ I don’t know much about $\mathcal B$ to answer the main question, however the mere fact that it contains $(\mathcal P(\omega),\subseteq^*)$ does not imply anything: $(\mathcal P(\omega),\subseteq^*)$ is an atomless Boolean algebra, hence its theory is decidable. $\endgroup$
    – Emil Jeřábek
    Commented Jul 23, 2014 at 17:28
  • $\begingroup$ That is, it does not imply anything about the complexity of the full first-order theory of $\mathcal B$. It does imply the decidability of universal sentences (and their Boolean combinations). $\endgroup$
    – Emil Jeřábek
    Commented Jul 23, 2014 at 17:36
  • 1
    $\begingroup$ A related question would be: what is known about the rigidity of $\cal B$? $\endgroup$
    – Joel David Hamkins
    Commented Jul 23, 2014 at 17:45
  • $\begingroup$ @Burak: No. This is again decidable (whether it’s all sets or Borel sets makes no difference). In general, in order to show undecidability, one shouldn’t look for large but orderly substructures like Boolean algebras, but rather for small and combinatorially peculiar substructures. Preferably definable. $\endgroup$
    – Emil Jeřábek
    Commented Jul 23, 2014 at 18:23
  • $\begingroup$ Would it help to know that there exists an assignment of Borel subsets of $\mathbb{R}$ to countable Borel equivalence relations $B \mapsto E_B$ such that $B \subseteq C \leftrightarrow E_B \leq_B E_C$, see here Theorem 3.3? For a second I thought this was true for all subsets and posted a faulty comment, but let me add this anyway. $\endgroup$
    – Burak
    Commented Jul 23, 2014 at 18:23

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .