On the complexity of Borel equivalence relations with some countability property

Lecomte, Dominique

doi:10.1090/tran/7942

On the complexity of Borel equivalence relations with some countability property
HTML articles powered by AMS MathViewer

by Dominique Lecomte PDF

Trans. Amer. Math. Soc. 373 (2020), 1845-1883 Request permission

Abstract:

We study the class of Borel equivalence relations under continuous reducibility. In particular, we characterize when a Borel equivalence relation with countable equivalence classes is $\mathbf {\Sigma }^{0}_{\xi }$ (or $\mathbf {\Pi }^{0}_{\xi }$). We characterize when all the equivalence classes of such a relation are $\mathbf {\Sigma }^{0}_{\xi }$ (or $\mathbf {\Pi }^{0}_{\xi }$). We prove analogous results for the Borel equivalence relations with countably many equivalence classes. We also completely solve these two problems for the first two ranks. In order to do this, we prove some extensions of the Louveau-Saint Raymond theorem, which itself generalized the Hurewicz theorem characterizing when a Borel subset of a Polish space is $G_\delta$.

References

Scot Adams and Alexander S. Kechris, Linear algebraic groups and countable Borel equivalence relations, J. Amer. Math. Soc. 13 (2000), no. 4, 909–943. MR 1775739, DOI 10.1090/S0894-0347-00-00341-6
John D. Clemens, Dominique Lecomte, and Benjamin D. Miller, Essential countability of treeable equivalence relations, Adv. Math. 265 (2014), 1–31. MR 3255454, DOI 10.1016/j.aim.2014.07.035
Gabriel Debs and Jean Saint Raymond, Borel liftings of Borel sets: some decidable and undecidable statements, Mem. Amer. Math. Soc. 187 (2007), no. 876, viii+118. MR 2308388, DOI 10.1090/memo/0876
Su Gao, Invariant descriptive set theory, Pure and Applied Mathematics (Boca Raton), vol. 293, CRC Press, Boca Raton, FL, 2009. MR 2455198
L. A. Harrington, A. S. Kechris, and A. Louveau, A Glimm-Effros dichotomy for Borel equivalence relations, J. Amer. Math. Soc. 3 (1990), no. 4, 903–928. MR 1057041, DOI 10.1090/S0894-0347-1990-1057041-5
Greg Hjorth and Alexander S. Kechris, New dichotomies for Borel equivalence relations, Bull. Symbolic Logic 3 (1997), no. 3, 329–346. MR 1476761, DOI 10.2307/421148
S. Jackson, A. S. Kechris, and A. Louveau, Countable Borel equivalence relations, J. Math. Log. 2 (2002), no. 1, 1–80. MR 1900547, DOI 10.1142/S0219061302000138
Alexander S. Kechris, Classical descriptive set theory, Graduate Texts in Mathematics, vol. 156, Springer-Verlag, New York, 1995. MR 1321597, DOI 10.1007/978-1-4612-4190-4
A. S. Kechris, The theory of countable Borel equivalence relations, preprint, 2018 (see the author’s webpage at http://www.math.caltech.edu/).
Dominique Lecomte, A dichotomy characterizing analytic digraphs of uncountable Borel chromatic number in any dimension, Trans. Amer. Math. Soc. 361 (2009), no. 8, 4181–4193. MR 2500884, DOI 10.1090/S0002-9947-09-04792-8
Dominique Lecomte, How can we recognize potentially $\Pi ^0_\xi$ subsets of the plane?, J. Math. Log. 9 (2009), no. 1, 39–62. MR 2665781, DOI 10.1142/S0219061309000793
Dominique Lecomte, Potential Wadge classes, Mem. Amer. Math. Soc. 221 (2013), no. 1038, vi+83. MR 3057834, DOI 10.1090/S0065-9266-2012-00658-7
Dominique Lecomte, A separation result for countable unions of Borel rectangles, J. Symb. Log. 84 (2019), no. 2, 517–532. MR 3961611, DOI 10.1017/jsl.2019.13
Alain Louveau, A separation theorem for $\Sigma ^{1}_{1}$ sets, Trans. Amer. Math. Soc. 260 (1980), no. 2, 363–378. MR 574785, DOI 10.1090/S0002-9947-1980-0574785-X
Alain Louveau, Ensembles analytiques et boréliens dans les espaces produits, Astérisque, vol. 78, Société Mathématique de France, Paris, 1980 (French). With an English summary. MR 606933
A. Louveau and J. Saint-Raymond, Borel classes and closed games: Wadge-type and Hurewicz-type results, Trans. Amer. Math. Soc. 304 (1987), no. 2, 431–467. MR 911079, DOI 10.1090/S0002-9947-1987-0911079-0
B. D. Miller, Forceless, ineffective, powerless proofs of descriptive dichotomy theorems, Lecture 3, The Harrington-Kechris-Louveau theorem, draft (see the author’s webpage at https://dl.dropboxusercontent.com/u/47430894/Web/otherwork/paristhree.pdf).
Yiannis N. Moschovakis, Descriptive set theory, Studies in Logic and the Foundations of Mathematics, vol. 100, North-Holland Publishing Co., Amsterdam-New York, 1980. MR 561709
Christian Rosendal, Cofinal families of Borel equivalence relations and quasiorders, J. Symbolic Logic 70 (2005), no. 4, 1325–1340. MR 2194249, DOI 10.2178/jsl/1129642127
Jack H. Silver, Counting the number of equivalence classes of Borel and coanalytic equivalence relations, Ann. Math. Logic 18 (1980), no. 1, 1–28. MR 568914, DOI 10.1016/0003-4843(80)90002-9
S. M. Srivastava, A course on Borel sets, Graduate Texts in Mathematics, vol. 180, Springer-Verlag, New York, 1998. MR 1619545, DOI 10.1007/978-3-642-85473-6