AMS eBook CollectionsOne of the world's most respected mathematical collections, available in digital format for your library or institution
Generalized descriptive set theory and classification theory
About this Title
Sy-David Friedman, Kurt Gödel Research Center, University of Vienna, Tapani Hyttinen, Department of Mathematics and Statistics, University of Helsinki and Vadim Kulikov, Kurt Gödel Research Center, University of Vienna – and – Department of Mathematics and Statistics, University of Helsinki
Publication: Memoirs of the American Mathematical Society
Publication Year:
2014; Volume 230, Number 1081
ISBNs: 978-0-8218-9475-0 (print); 978-1-4704-1671-3 (online)
DOI: https://doi.org/10.1090/memo/1081
Published electronically: December 16, 2013
MSC: Primary 03C55, 03C45, 03E15, 03E47, 03C75, 03E35
Table of Contents
Chapters
- 1. History and Motivation
- 2. Introduction
- 3. Borel Sets, ${\Delta _1^1}$ Sets and Infinitary Logic
- 4. Generalizations From Classical Descriptive Set Theory
- 5. Complexity of Isomorphism Relations
- 6. Reductions
- 7. Open Questions
Abstract
Descriptive set theory is mainly concerned with studying subsets of the space of all countable binary sequences. In this paper we study the generalization where countable is replaced by uncountable. We explore properties of generalized Baire and Cantor spaces, equivalence relations and their Borel reducibility. The study shows that the descriptive set theory looks very different in this generalized setting compared to the classical, countable case. We also draw the connection between the stability theoretic complexity of first-order theories and the descriptive set theoretic complexity of their isomorphism relations. Our results suggest that Borel reducibility on uncountable structures is a model theoretically natural way to compare the complexity of isomorphism relations.
Acknowledgement: The authors wish to thank the John Templeton Foundation for its generous support through its project Myriad Aspects of Infinity (ID #13152). The authors wish to thank also Mittag-Leffler Institute (the Royal Swedish Academy of Sciences).
The second and the third authors wish to thank the Academy of Finland for its support through its grant number 1123110.
The third author wants to express his gratitude to the Research Foundation of the University of Helsinki and the Finnish National Graduate School in Mathematics and its Applications for the financial support during the work.
We are grateful to Jouko Väänänen for the useful discussions and comments he provided on a draft of this paper.
- 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
- D. Blackwell, Borel sets via games, Ann. Probab. 9 (1981), no. 2, 321–322. MR 606995
- Sy-David Friedman, Consistency of the Silver Dichotomy in Generalised Baire Space, submitted.
- John Gregory, Higher Souslin trees and the generalized continuum hypothesis, J. Symbolic Logic 41 (1976), no. 3, 663–671. MR 485361, DOI 10.2307/2272043
- A. Halko: Negligible subsets of the generalized Baire space $\o _1^{\o _1}$, Ann. Acad. Sci. Ser. Diss. Math. 108 (1996).
- 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
- 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
- Bradd Hart, Ehud Hrushovski, and Michael C. Laskowski, The uncountable spectra of countable theories, Ann. of Math. (2) 152 (2000), no. 1, 207–257. MR 1792295, DOI 10.2307/2661382
- G. Hjorth: Group actions and countable models – A survey article presented at the ASL European meeting in Utrecht, 1999.
- Taneli Huuskonen, Tapani Hyttinen, and Mika Rautila, On potential isomorphism and non-structure, Arch. Math. Logic 43 (2004), no. 1, 85–120. MR 2036250, DOI 10.1007/s00153-003-0185-z
- Sy-David Friedman and Tapani Hyttinen, On Borel equivalence relations in generalized Baire space, Arch. Math. Logic 51 (2012), no. 3-4, 299–304. MR 2899693, DOI 10.1007/s00153-011-0266-3
- T. Hyttinen, V. Kulikov: On Borel* sets in the generalized Baire space – arXiv:1209.3933 [math.LO] (2012)
- T. Hyttinen, V. Kulikov: On $\Sigma ^1_1$-complete equivalence relations on the generalized Baire space. arXiv:1209.3932 [math.LO] – arXiv:1209.3933 [math.LO] (2012)
- Tapani Hyttinen and Mika Rautila, The canary tree revisited, J. Symbolic Logic 66 (2001), no. 4, 1677–1694. MR 1877015, DOI 10.2307/2694968
- Tapani Hyttinen and Saharon Shelah, Constructing strongly equivalent nonisomorphic models for unsuperstable theories. Part A, J. Symbolic Logic 59 (1994), no. 3, 984–996. MR 1295983, DOI 10.2307/2275922
- Tapani Hyttinen and Saharon Shelah, Constructing strongly equivalent nonisomorphic models for unsuperstable theories. Part B, J. Symbolic Logic 60 (1995), no. 4, 1260–1272. MR 1367209, DOI 10.2307/2275887
- Tapani Hyttinen and Saharon Shelah, Constructing strongly equivalent nonisomorphic models for unsuperstable theories. Part C, J. Symbolic Logic 64 (1999), no. 2, 634–642. MR 1777775, DOI 10.2307/2586489
- Tapani Hyttinen and Heikki Tuuri, Constructing strongly equivalent nonisomorphic models for unstable theories, Ann. Pure Appl. Logic 52 (1991), no. 3, 203–248. MR 1111753, DOI 10.1016/0168-0072(91)90031-G
- Thomas Jech, Set theory, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2003. The third millennium edition, revised and expanded. MR 1940513
- Carol R. Karp, Finite-quantifier equivalence, Theory of Models (Proc. 1963 Internat. Sympos. Berkeley), North-Holland, Amsterdam, 1965, pp. 407–412. MR 0209132
- M. Karttunen: Model theory for infinitely deep languages – Ann. Acad. Sci. Fenn. Ser. A I Math. Dissertationes, vol 64, 1987.
- Martin Koerwien, A complicated $\omega$-stable depth 2 theory, J. Symbolic Logic 76 (2011), no. 1, 47–65. MR 2791337, DOI 10.2178/jsl/1294170989
- 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
- V. Kulikov: Borel reductions in the Generalised Cantor Space – Journal of Symbolic Logic, to appear (2012).
- 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
- Alan H. Mekler and Saharon Shelah, The canary tree, Canad. Math. Bull. 36 (1993), no. 2, 209–215. MR 1222536, DOI 10.4153/CMB-1993-030-6
- 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
- Mark Nadel and Jonathan Stavi, $L_{\infty }{}_{\lambda }$-equivalence, isomorphism and potential isomorphism, Trans. Amer. Math. Soc. 236 (1978), 51–74. MR 462942, DOI 10.1090/S0002-9947-1978-0462942-3
- Saharon Shelah, A combinatorial problem; stability and order for models and theories in infinitary languages, Pacific J. Math. 41 (1972), 247–261. MR 307903
- S. Shelah: Classification Theory, Revised Edition – North Holland Publishing Company Amsterdam New-York Oxford Tokyo, 2000.
- Saharon Shelah, Existence of many $L_{\infty ,\lambda }$-equivalent, nonisomorphic models of $T$ of power $\lambda$, Ann. Pure Appl. Logic 34 (1987), no. 3, 291–310. Stability in model theory (Trento, 1984). MR 899084, DOI 10.1016/0168-0072(87)90005-4
- Saharon Shelah, The number of non-isomorphic models of an unstable first-order theory, Israel J. Math. 9 (1971), 473–487. MR 278926, DOI 10.1007/BF02771463
- Saharon Shelah, The spectrum problem. I. $\aleph _{\varepsilon }$-saturated models, the main gap, Israel J. Math. 43 (1982), no. 4, 324–356. MR 693353, DOI 10.1007/BF02761237
- Saharon Shelah, Diamonds, Proc. Amer. Math. Soc. 138 (2010), no. 6, 2151–2161. MR 2596054, DOI 10.1090/S0002-9939-10-10254-8
- 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
- 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
- Heikki Tuuri, Relative separation theorems for $\scr L_{\kappa +\kappa }$, Notre Dame J. Formal Logic 33 (1992), no. 3, 383–401. MR 1184069, DOI 10.1305/ndjfl/1093634403
- J. Väänänen: How complicated can structures be? – Nieuw Archief voor Wiskunde. June 2008, 117-121.
- J. Väänänen: Games and trees in infinitary logic: A Survey. – In M. Krynicki, M. Mostowski and L. Szczerba, editors, Quantifiers, Kluwer Academic Publishers, 105-138, 1995.
- Jouko Väänänen, Models and games, Cambridge Studies in Advanced Mathematics, vol. 132, Cambridge University Press, Cambridge, 2011. MR 2768176
- 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