Complete analytic equivalence relations

Louveau, Alain; Rosendal, Christian

doi:10.1090/S0002-9947-05-04005-5

Complete analytic equivalence relations
HTML articles powered by AMS MathViewer

by Alain Louveau and Christian Rosendal PDF

Trans. Amer. Math. Soc. 357 (2005), 4839-4866 Request permission

Abstract:

We prove that various concrete analytic equivalence relations arising in model theory or analysis are complete, i.e. maximum in the Borel reducibility ordering. The proofs use some general results concerning the wider class of analytic quasi-orders.

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
Howard Becker and Alexander S. Kechris, The descriptive set theory of Polish group actions, London Mathematical Society Lecture Note Series, vol. 232, Cambridge University Press, Cambridge, 1996. MR 1425877, DOI 10.1017/CBO9780511735264
Riccardo Camerlo and Su Gao, The completeness of the isomorphism relation for countable Boolean algebras, Trans. Amer. Math. Soc. 353 (2001), no. 2, 491–518. MR 1804507, DOI 10.1090/S0002-9947-00-02659-3
J.D. Clemens, Ph.D. thesis, U.C. Berkeley (2001).
John D. Clemens, Su Gao, and Alexander S. Kechris, Polish metric spaces: their classification and isometry groups, Bull. Symbolic Logic 7 (2001), no. 3, 361–375. MR 1860610, DOI 10.2307/2687754
R. Fraïssé, Sur la comparaison des types d’ordre, C.R. Acad. Sci 226 (1948), 987-988 and 1330-1331.
Su Gao, Coding subset shift by subgroup conjugacy, Bull. London Math. Soc. 32 (2000), no. 6, 653–657. MR 1781575, DOI 10.1112/S0024609300007463
Su Gao and Alexander S. Kechris, On the classification of Polish metric spaces up to isometry, Mem. Amer. Math. Soc. 161 (2003), no. 766, viii+78. MR 1950332, DOI 10.1090/memo/0766
G. Godefroy and N. J. Kalton, Lipschitz-free Banach spaces, Studia Math. 159 (2003), no. 1, 121–141. Dedicated to Professor Aleksander Pełczyński on the occasion of his 70th birthday. MR 2030906, DOI 10.4064/sm159-1-6
Misha Gromov, Metric structures for Riemannian and non-Riemannian spaces, Progress in Mathematics, vol. 152, Birkhäuser Boston, Inc., Boston, MA, 1999. Based on the 1981 French original [ MR0682063 (85e:53051)]; With appendices by M. Katz, P. Pansu and S. Semmes; Translated from the French by Sean Michael Bates. MR 1699320
Greg Hjorth, Universal co-analytic sets, Proc. Amer. Math. Soc. 124 (1996), no. 12, 3867–3873. MR 1343698, DOI 10.1090/S0002-9939-96-03494-6
Greg Hjorth, Classification and orbit equivalence relations, Mathematical Surveys and Monographs, vol. 75, American Mathematical Society, Providence, RI, 2000. MR 1725642, DOI 10.1090/surv/075
A.S. Kechris, Lectures on definable group actions and equivalence relations, circulated notes (1994).
Alexander S. Kechris, New directions in descriptive set theory, Bull. Symbolic Logic 5 (1999), no. 2, 161–174. MR 1791302, DOI 10.2307/421088
Alexander S. Kechris, Actions of Polish groups and classification problems, Analysis and logic (Mons, 1997) London Math. Soc. Lecture Note Ser., vol. 262, Cambridge Univ. Press, Cambridge, 2002, pp. 115–187. MR 1967835
Richard Laver, On Fraïssé’s order type conjecture, Ann. of Math. (2) 93 (1971), 89–111. MR 279005, DOI 10.2307/1970754
Alain Louveau, On the reducibility order between Borel equivalence relations, Logic, methodology and philosophy of science, IX (Uppsala, 1991) Stud. Logic Found. Math., vol. 134, North-Holland, Amsterdam, 1994, pp. 151–155. MR 1327979, DOI 10.1016/S0049-237X(06)80042-X
Alain Louveau, Two results on Borel orders, J. Symbolic Logic 54 (1989), no. 3, 865–874. MR 1011175, DOI 10.2307/2274748
A. Louveau, Closed quasi-orders and their vicinity, manuscript, 2001.
A. Louveau, Analytic partial orders, manuscript, 2002.
Alain Louveau and Christian Rosendal, Relations d’équivalence analytiques complètes, C. R. Acad. Sci. Paris Sér. I Math. 333 (2001), no. 10, 903–906 (French, with English and French summaries). MR 1873805, DOI 10.1016/S0764-4442(01)02160-7
Alain Louveau and Boban Veli ković, A note on Borel equivalence relations, Proc. Amer. Math. Soc. 120 (1994), no. 1, 255–259. MR 1169042, DOI 10.1090/S0002-9939-1994-1169042-2
Richard Mansfield and Galen Weitkamp, Recursive aspects of descriptive set theory, Oxford Logic Guides, vol. 11, The Clarendon Press, Oxford University Press, New York, 1985. With a chapter by Stephen Simpson. MR 786122
C. St. J. A. Nash-Williams, On well-quasi-ordering infinite trees, Proc. Cambridge Philos. Soc. 61 (1965), 697–720. MR 175814, DOI 10.1017/s0305004100039062
Jaroslav Ne et il, The homomorphism structure of classes of graphs, Combin. Probab. Comput. 8 (1999), no. 1-2, 177–184. Recent trends in combinatorics (Mátraháza, 1995). MR 1684628, DOI 10.1017/S0963548398003460
C. Rosendal, Cofinal families of Borel quasi-orders and equivalence relations, to appear in Journal of Symbolic Logic.
C. Rosendal, Etude descriptive de l’isomorphisme dans la classe des espaces de Banach, Thesis, Université Paris 6 (2003).
Richard Mansfield and Galen Weitkamp, Recursive aspects of descriptive set theory, Oxford Logic Guides, vol. 11, The Clarendon Press, Oxford University Press, New York, 1985. With a chapter by Stephen Simpson. MR 786122
Lee J. Stanley, Borel diagonalization and abstract set theory: recent results of Harvey Friedman, Harvey Friedman’s research on the foundations of mathematics, Stud. Logic Found. Math., vol. 117, North-Holland, Amsterdam, 1985, pp. 11–86. MR 835254, DOI 10.1016/S0049-237X(09)70155-7
Simon Thomas and Boban Velickovic, On the complexity of the isomorphism relation for finitely generated groups, J. Algebra 217 (1999), no. 1, 352–373. MR 1700491, DOI 10.1006/jabr.1998.7825