Structurable equivalence relations and L_ω1ω interpretations

2024/09/04 by Rishi Banerjee, Ruiyuan Chen, Banerjee, Rishi +1
Computer Science · #Computability, Logic, AI Algorithms

paper · pdf · doi:10.48550/arxiv.2409.02896

Abstract

We show that the category of countable Borel equivalence relations (CBERs) is dually equivalent to the category of countable L_ω1ω theories which admit a one-sorted interpretation of a particular theory we call T_LN \sqcup T_sep that witnesses embeddability into 2^ℕ and the Lusin--Novikov uniformization theorem. This allows problems about Borel combinatorial structures on CBERs to be translated into syntactic definability problems in L_ω1ω, modulo the extra structure provided by T_LN \sqcup T_sep, thereby formalizing a folklore intuition in locally countable Borel combinatorics. We illustrate this with a catalogue of the precise interpretability relations between several standard classes of structures commonly used in Borel combinatorics, such as Feldman--Moore ω-colorings and the Slaman--Steel marker lemma. We also generalize this correspondence to locally countable Borel groupoids and theories interpreting T_LN, which admit a characterization analogous to that of Hjorth--Kechris for essentially countable isomorphism relations.

Related

• Borel functors, interpretations, and strong conceptual completeness for \mathcal L_ω1ω
• Structurable equivalence relations
• Definable expansions on countable groups and countable Borel equivalence relations
• Realizations of countable Borel equivalence relations
• Countable Borel equivalence relations and quotient Borel spaces