AMS eBook CollectionsOne of the world's most respected mathematical collections, available in digital format for your library or institution
Souslin quasi-orders and bi-embeddability of uncountable structures
About this Title
Alessandro Andretta and Luca Motto Ros
Publication: Memoirs of the American Mathematical Society
Publication Year:
2022; Volume 277, Number 1365
ISBNs: 978-1-4704-5273-5 (print); 978-1-4704-7097-5 (online)
DOI: https://doi.org/10.1090/memo/1365
Published electronically: April 13, 2022
Keywords: Generalized descriptive set theory,
infinitary logics,
$\kappa$-Souslin sets,
determinacy,
(bi-)embeddability,
uncountable structures,
non-separable metric spaces,
non-separable Banach spaces
Table of Contents
Chapters
- 1. Introduction
- 2. Preliminaries and notation
- 3. The generalized Cantor space
- 4. Generalized Borel sets
- 5. Generalized Borel functions
- 6. The generalized Baire space and Baire category
- 7. Standard Borel $\kappa$-spaces, $\kappa$-analytic quasi-orders, and spaces of codes
- 8. Infinitary logics and models
- 9. $\kappa$-Souslin sets
- 10. The main construction
- 11. Completeness
- 12. Invariant universality
- 13. An alternative approach
- 14. Definable cardinality and reducibility
- 15. Some applications
- 16. Further completeness results
- Indexes
Abstract
We provide analogues of the results from Friedman and Motto Ros (2011) and Camerlo, Marcone, and Motto Ros (2013) (which correspond to the case $\kappa = \omega$) for arbitrary $\kappa$-Souslin quasi-orders on any Polish space, for $\kappa$ an infinite cardinal smaller than the cardinality of $\mathbb {R}$. These generalizations yield a variety of results concerning the complexity of the embeddability relation between graphs or lattices of size $\kappa$, the isometric embeddability relation between complete metric spaces of density character $\kappa$, and the linear isometric embeddability relation between (real or complex) Banach spaces of density $\kappa$.- 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
- Alessandro Andretta and Riccardo Camerlo, Analytic sets of reals and the density function in the Cantor space, Eur. J. Math. 5 (2019), no. 1, 49–80. MR 3918833, DOI 10.1007/s40879-018-0238-9
- Jon Barwise, Infinitary logic and admissible sets, J. Symbolic Logic 34 (1969), no. 2, 226–252. MR 406760, DOI 10.2307/2271099
- 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
- Filippo Calderoni, Heike Mildenberger, and Luca Motto Ros, Uncountable structures are not classifiable up to bi-embeddability, J. Math. Log. 20 (2020), no. 1, 2050001, 49. MR 4094553, DOI 10.1142/S0219061320500014
- Filippo Calderoni and Simon Thomas, The bi-embeddability relation for countable abelian groups, Trans. Amer. Math. Soc. 371 (2019), no. 3, 2237–2254. MR 3894051, DOI 10.1090/tran/7513
- Riccardo Camerlo, Alberto Marcone, and Luca Motto Ros, Invariantly universal analytic quasi-orders, Trans. Amer. Math. Soc. 365 (2013), no. 4, 1901–1931. MR 3009648, DOI 10.1090/S0002-9947-2012-05618-2
- Riccardo Camerlo, Alberto Marcone, and Luca Motto Ros, On isometry and isometric embeddability between ultrametric Polish spaces, Adv. Math. 329 (2018), 1231–1284. MR 3783437, DOI 10.1016/j.aim.2018.03.001
- Riccardo Camerlo, Alberto Marcone, and Luca Motto Ros, Polish metric spaces with fixed distance set, Ann. Pure Appl. Logic 171 (2020), no. 10, 102832, 25. MR 4108225, DOI 10.1016/j.apal.2020.102832
- J. Chaber, G. Gruenhage, and R. Pol, On Souslin sets and embeddings in integer-valued function spaces on $\omega _1$, Topology Appl. 82 (1998), no. 1-3, 71–104. Special volume in memory of Kiiti Morita. MR 1602431, DOI 10.1016/S0166-8641(97)00058-8
- Vitalij A. Chatyrko and Alexandre Karassev, The (dis)connectedness of products in the box topology, Questions Answers Gen. Topology 31 (2013), no. 1, 11–21. MR 3075890
- Alex Chigogidze and John R. Martin, Fixed point sets of autohomeomorphisms of uncountable products, Topology Appl. 80 (1997), no. 1-2, 63–71. MR 1469467, DOI 10.1016/S0166-8641(97)00005-9
- John D. Clemens, Classifying Borel automorphisms, J. Symbolic Logic 72 (2007), no. 4, 1081–1092. MR 2371193, DOI 10.2178/jsl/1203350774
- John D. Clemens, Isometry of Polish metric spaces, Ann. Pure Appl. Logic 163 (2012), no. 9, 1196–1209. MR 2926279, DOI 10.1016/j.apal.2012.01.001
- 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
- Paul Cohen, The independence of the continuum hypothesis, Proc. Nat. Acad. Sci. U.S.A. 50 (1963), 1143–1148. MR 157890, DOI 10.1073/pnas.50.6.1143
- Mirna D amonja and Jouko Väänänen, Chain models, trees of singular cardinality and dynamic EF-games, J. Math. Log. 11 (2011), no. 1, 61–85. MR 2833151, DOI 10.1142/S0219061311001006
- Valentin Ferenczi, Alain Louveau, and Christian Rosendal, The complexity of classifying separable Banach spaces up to isomorphism, J. Lond. Math. Soc. (2) 79 (2009), no. 2, 323–345. MR 2496517, DOI 10.1112/jlms/jdn068
- Ekaterina B. Fokina, Sy-David Friedman, Valentina Harizanov, Julia F. Knight, Charles McCoy, and Antonio Montalbán, Isomorphism relations on computable structures, J. Symbolic Logic 77 (2012), no. 1, 122–132. MR 2951633, DOI 10.2178/jsl/1327068695
- Harvey Friedman and Lee Stanley, A Borel reducibility theory for classes of countable structures, J. Symbolic Logic 54 (1989), no. 3, 894–914. MR 1011177, DOI 10.2307/2274750
- Sy-David Friedman, Tapani Hyttinen, and Vadim Kulikov, Generalized descriptive set theory and classification theory, Mem. Amer. Math. Soc. 230 (2014), no. 1081, vi+80. MR 3235820
- Sy-David Friedman and Vladimir Kanovei, Some natural equivalence relations in the Solovay model, Abh. Math. Semin. Univ. Hambg. 78 (2008), no. 1, 91–98. MR 2501530, DOI 10.1007/s12188-008-0003-y
- Sy-David Friedman and Luca Motto Ros, Analytic equivalence relations and bi-embeddability, J. Symbolic Logic 76 (2011), no. 1, 243–266. MR 2791347, DOI 10.2178/jsl/1294170999
- S. Gao, Invariant Descriptive Set Theory, Monographs and Textbooks in Pure and Applied Mathematics, CRC Press, Taylor&Francis Group, 2009.
- 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
- K. Gödel, The consistency of the axiom of choice and the generalized continuum hypothesis, Proceedings of the National Academy of Sciences of the United Staes of America 24 (1938), 556–557.
- Aapo Halko, Negligible subsets of the generalized Baire space $\omega ^{\omega _1}_1$, Ann. Acad. Sci. Fenn. Math. Diss. 107 (1996), 38. MR 1413840
- Aapo Halko and Saharon Shelah, On strong measure zero subsets of $^\kappa 2$, Fund. Math. 170 (2001), no. 3, 219–229. MR 1880900, DOI 10.4064/fm170-3-1
- Leo Harrington, Long projective wellorderings, Ann. Math. Logic 12 (1977), no. 1, 1–24. MR 465866, DOI 10.1016/0003-4843(77)90004-3
- Leo Harrington, Analytic determinacy and $0^{\sharp }$, J. Symbolic Logic 43 (1978), no. 4, 685–693. MR 518675, DOI 10.2307/2273508
- 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
- Leo Harrington, David Marker, and Saharon Shelah, Borel orderings, Trans. Amer. Math. Soc. 310 (1988), no. 1, 293–302. MR 965754, DOI 10.1090/S0002-9947-1988-0965754-3
- L. Harrington and R. Sami, Equivalence relations, projective and beyond, Logic Colloquium ’78 (Mons, 1978) Stud. Logic Found. Math., vol. 97, North-Holland, Amsterdam-New York, 1979, pp. 247–264. MR 567673
- Leo Harrington and Saharon Shelah, Counting equivalence classes for co-$\kappa$-Souslin equivalence relations, Logic Colloquium ’80 (Prague, 1980) Stud. Logic Found. Math., vol. 108, North-Holland, Amsterdam-New York, 1982, pp. 147–152. MR 673790
- Greg Hjorth, A dichotomy for the definable universe, J. Symbolic Logic 60 (1995), no. 4, 1199–1207. MR 1367205, DOI 10.2307/2275883
- Greg Hjorth, Orbit cardinals: on the effective cardinalities arising as quotient spaces of the form $X/G$ where $G$ acts on a Polish space $X$, Israel J. Math. 111 (1999), 221–261. MR 1710740, DOI 10.1007/BF02810686
- 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
- Greg Hjorth and Alexander S. Kechris, Analytic equivalence relations and Ulm-type classifications, J. Symbolic Logic 60 (1995), no. 4, 1273–1300. MR 1367210, DOI 10.2307/2275888
- Wilfrid Hodges, Model theory, Encyclopedia of Mathematics and its Applications, vol. 42, Cambridge University Press, Cambridge, 1993. MR 1221741, DOI 10.1017/CBO9780511551574
- H. H. Hung and S. Negrepontis, Spaces homeomorphic to $(2^{\alpha })_{\alpha }$, Bull. Amer. Math. Soc. 79 (1973), 143–146. MR 367930, DOI 10.1090/S0002-9904-1973-13132-5
- Tapani Hyttinen and Vadim Kulikov, On $\Sigma ^1_1$-complete equivalence relations on the generalized Baire space, MLQ Math. Log. Q. 61 (2015), no. 1-2, 66–81. MR 3319714, DOI 10.1002/malq.201200063
- S. D. Iliadis, A note on hierarchies of Borel type sets, Topology Appl. 159 (2012), no. 7, 1702–1704. MR 2904057, DOI 10.1016/j.topol.2011.09.041
- Steve Jackson, AD and the very fine structure of $L(\textbf {R})$, Bull. Amer. Math. Soc. (N.S.) 21 (1989), no. 1, 77–81. MR 980305, DOI 10.1090/S0273-0979-1989-15766-2
- Steve Jackson, Suslin cardinals, partition properties, homogeneity. Introduction to Part II, Games, scales, and Suslin cardinals. The Cabal Seminar. Vol. I, Lect. Notes Log., vol. 31, Assoc. Symbol. Logic, Chicago, IL, 2008, pp. 273–313. MR 2463617, DOI 10.1017/CBO9780511546488.015
- Steve Jackson, Structural consequences of AD, Handbook of set theory. Vols. 1, 2, 3, Springer, Dordrecht, 2010, pp. 1753–1876. MR 2768700, DOI 10.1007/978-1-4020-5764-9_{2}2
- Thomas Jech, Set theory, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2003. The third millennium edition, revised and expanded. MR 1940513
- Akihiro Kanamori, The higher infinite, 2nd ed., Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2003. Large cardinals in set theory from their beginnings. MR 1994835
- Vladimir Kanovei, An Ulm-type classification theorem for equivalence relations in Solovay model, J. Symbolic Logic 62 (1997), no. 4, 1333–1351. MR 1617937, DOI 10.2307/2275646
- Vladimir Kanovei, Borel equivalence relations, University Lecture Series, vol. 44, American Mathematical Society, Providence, RI, 2008. Structure and classification. MR 2441635, DOI 10.1090/ulect/044
- M. Katětov, On universal metric spaces, General topology and its relations to modern analysis and algebra, VI (Prague, 1986) Res. Exp. Math., vol. 16, Heldermann, Berlin, 1988, pp. 323–330. MR 952617
- Alexander S. Kechris, On projective ordinals, J. Symbolic Logic 39 (1974), 269–282. MR 398833, DOI 10.2307/2272639
- Alexander S. Kechris, The axiom of determinacy implies dependent choices in $L(\textbf {R})$, J. Symbolic Logic 49 (1984), no. 1, 161–173. MR 736611, DOI 10.2307/2274099
- 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
- 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 and Benjamin D. Miller, Topics in orbit equivalence, Lecture Notes in Mathematics, vol. 1852, Springer-Verlag, Berlin, 2004. MR 2095154, DOI 10.1007/b99421
- H. Jerome Keisler, Model theory for infinitary logic. Logic with countable conjunctions and finite quantifiers, Studies in Logic and the Foundations of Mathematics, Vol. 62, North-Holland Publishing Co., Amsterdam-London, 1971. MR 344115
- Kyriakos Keremedis, The compactness of $2^\textbf {R}$ and the axiom of choice, MLQ Math. Log. Q. 46 (2000), no. 4, 569–571. MR 1791873, DOI 10.1002/1521-3870(200010)46:4<569::AID-MALQ569>3.0.CO;2-J
- Richard Ketchersid, More structural consequences of $\textrm {AD}$, Set theory and its applications, Contemp. Math., vol. 533, Amer. Math. Soc., Providence, RI, 2011, pp. 71–105. MR 2777745, DOI 10.1090/conm/533/10504
- Julia F. Knight, A complete $L_{\omega _{1}\omega }$-sentence characterizing $\aleph _{1}$, J. Symbolic Logic 42 (1977), no. 1, 59–62. MR 491141, DOI 10.2307/2272318
- Peter Koellner and W. Hugh Woodin, Large cardinals from determinacy, Handbook of set theory. Vols. 1, 2, 3, Springer, Dordrecht, 2010, pp. 1951–2119. MR 2768702, DOI 10.1007/978-1-4020-5764-9_{2}4
- Jan Kraszewski, Properties of ideals on the generalized Cantor spaces, J. Symbolic Logic 66 (2001), no. 3, 1303–1320. MR 1856743, DOI 10.2307/2695108
- Kenneth Kunen, Set theory, Studies in Logic and the Foundations of Mathematics, vol. 102, North-Holland Publishing Co., Amsterdam-New York, 1980. An introduction to independence proofs. MR 597342
- K. Kuratowski, Topology. Vol. I, Academic Press, New York-London; Państwowe Wydawnictwo Naukowe [Polish Scientific Publishers], Warsaw, 1966. New edition, revised and augmented; Translated from the French by J. Jaworowski. MR 217751
- Alain Louveau and Christian Rosendal, Complete analytic equivalence relations, Trans. Amer. Math. Soc. 357 (2005), no. 12, 4839–4866. MR 2165390, DOI 10.1090/S0002-9947-05-04005-5
- P. Lücke and P. Schlicht, Continuous images of closed sets in generalized Baire spaces, Israel Journal of Mathematics 209 (2015), no. 1, 421–461.
- Donald A. Martin, Projective sets and cardinal numbers: some questions related to the continuum problem, Wadge degrees and projective ordinals. The Cabal Seminar. Volume II, Lect. Notes Log., vol. 37, Assoc. Symbol. Logic, La Jolla, CA, 2012, pp. 484–508. MR 2907001
- D. A. Martin and R. M. Solovay, Internal Cohen extensions, Ann. Math. Logic 2 (1970), no. 2, 143–178. MR 270904, DOI 10.1016/0003-4843(70)90009-4
- Alan Mekler and Jouko Väänänen, Trees and $\Pi ^1_1$-subsets of $^{\omega _1}\omega _1$, J. Symbolic Logic 58 (1993), no. 3, 1052–1070. MR 1242054, DOI 10.2307/2275112
- Julien Melleray, Computing the complexity of the relation of isometry between separable Banach spaces, MLQ Math. Log. Q. 53 (2007), no. 2, 128–131. MR 2308492, DOI 10.1002/malq.200610032
- Arnold W. Miller, A Dedekind finite Borel set, Arch. Math. Logic 50 (2011), no. 1-2, 1–17. MR 2765632, DOI 10.1007/s00153-010-0195-6
- Deane Montgomery and Leo Zippin, Topological transformation groups, Interscience Publishers, New York-London, 1955. MR 73104
- Yiannis N. Moschovakis, Descriptive set theory, 2nd ed., Mathematical Surveys and Monographs, vol. 155, American Mathematical Society, Providence, RI, 2009. MR 2526093, DOI 10.1090/surv/155
- Luca Motto Ros, On the complexity of the relations of isomorphism and bi-embeddability, Proc. Amer. Math. Soc. 140 (2012), no. 1, 309–323. MR 2833542, DOI 10.1090/S0002-9939-2011-10896-7
- Luca Motto Ros, The descriptive set-theoretical complexity of the embeddability relation on models of large size, Ann. Pure Appl. Logic 164 (2013), no. 12, 1454–1492. MR 3093397, DOI 10.1016/j.apal.2013.06.018
- Luca Motto Ros, Can we classify complete metric spaces up to isometry?, Boll. Unione Mat. Ital. 10 (2017), no. 3, 369–410. MR 3691805, DOI 10.1007/s40574-017-0125-1
- I. I. Parovičenko, On a universal bicompactum of weight $\aleph$, Dokl. Akad. Nauk SSSR 150 (1963), 36–39. MR 150732
- Saharon Shelah, On co-$\kappa$-Souslin relations, Israel J. Math. 47 (1984), no. 2-3, 139–153. MR 738165, DOI 10.1007/BF02760513
- Saharon Shelah, Strong dichotomy of cardinality, Results Math. 39 (2001), no. 1-2, 131–154. MR 1817405, DOI 10.1007/BF03322680
- Saharon Shelah, On nice equivalence relations on ${}^\lambda 2$, Arch. Math. Logic 43 (2004), no. 1, 31–64. MR 2036248, DOI 10.1007/s00153-003-0183-1
- Saharon Shelah and Jouko Väänänen, Stationary sets and infinitary logic, J. Symbolic Logic 65 (2000), no. 3, 1311–1320. MR 1791377, DOI 10.2307/2586701
- Saharon Shelah and Pauli Väisänen, On equivalence relations second order definable over $H(\kappa )$, Fund. Math. 174 (2002), no. 1, 1–21. MR 1925484, DOI 10.4064/fm174-1-1
- Saharon Shelah and Hugh Woodin, Large cardinals imply that every reasonably definable set of reals is Lebesgue measurable, Israel J. Math. 70 (1990), no. 3, 381–394. MR 1074499, DOI 10.1007/BF02801471
- 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
- John R. Steel, An outline of inner model theory, Handbook of set theory. Vols. 1, 2, 3, Springer, Dordrecht, 2010, pp. 1595–1684. MR 2768698, DOI 10.1007/978-1-4020-5764-9_{2}0
- John R. Steel, PFA implies $\textrm {AD}^{L(\Bbb R)}$, J. Symbolic Logic 70 (2005), no. 4, 1255–1296. MR 2194247, DOI 10.2178/jsl/1129642125
- J. R. Steel, Closure properties of pointclasses, Wadge degrees and projective ordinals. The Cabal Seminar. Volume II, 2012, pp. 102–117.
- Alexander S. Kechris, On Spector classes, Cabal Seminar 76–77 (Proc. Caltech-UCLA Logic Sem., 1976–77) Lecture Notes in Math., vol. 689, Springer, Berlin, 1978, pp. 245–277. MR 526922
- Jacques Stern, On Lusin’s restricted continuum problem, Ann. of Math. (2) 120 (1984), no. 1, 7–37. MR 750715, DOI 10.2307/2007070
- A. H. Stone, Paracompactness and product spaces, Bull. Amer. Math. Soc. 54 (1948), 977–982. MR 26802, DOI 10.1090/S0002-9904-1948-09118-2
- Ken-ichi Tamano and Hui Teng, Normality and covering properties of open sets of uncountable products, Topology Proc. 18 (1993), 313–322. MR 1305139
- Yusuf Ünlü, Spaces for which the generalized Cantor space $2^{J}$ is a remainder, Proc. Amer. Math. Soc. 86 (1982), no. 4, 673–678. MR 674104, DOI 10.1090/S0002-9939-1982-0674104-1
- Jouko Väänänen, Models and games, Cambridge Studies in Advanced Mathematics, vol. 132, Cambridge University Press, Cambridge, 2011. MR 2768176, DOI 10.1017/CBO9780511974885
- Robert Vaught, Invariant sets in topology and logic, Fund. Math. 82 (1974/75), 269–294. MR 363912, DOI 10.4064/fm-82-3-269-294
- A. M. Vershik, The universal Uryson space, Gromov’s metric triples, and random metrics on the series of natural numbers, Uspekhi Mat. Nauk 53 (1998), no. 5(323), 57–64 (Russian); English transl., Russian Math. Surveys 53 (1998), no. 5, 921–928. MR 1691182, DOI 10.1070/rm1998v053n05ABEH000069
- William Wilfred Wadge, Reducibility and determinateness on the Baire space, ProQuest LLC, Ann Arbor, MI, 1983. Thesis (Ph.D.)–University of California, Berkeley. MR 2633374
- W. Hugh Woodin, The axiom of determinacy, forcing axioms, and the nonstationary ideal, Second revised edition, De Gruyter Series in Logic and its Applications, vol. 1, Walter de Gruyter GmbH & Co. KG, Berlin, 2010. MR 2723878, DOI 10.1515/9783110213171