The Ehrenfeucht-Fraïssé-game of length $\omega _ 1$
HTML articles powered by AMS MathViewer
- by Alan Mekler, Saharon Shelah and Jouko Väänänen PDF
- Trans. Amer. Math. Soc. 339 (1993), 567-580 Request permission
Abstract:
Let $\mathfrak {A}$ and $\mathfrak {B}$ be two first order structures of the same vocabulary. We shall consider the Ehrenfeucht-Fraïssé-game of length ${\omega _1}$ of $\mathfrak {A}$ and $\mathfrak {B}$ which we denote by ${\mathcal {G}_{{\omega _1}}}(\mathfrak {A},\mathfrak {B})$. This game is like the ordinary Ehrenfeucht-Fraïssé-game of ${L_{\omega \omega }}$ except that there are ${\omega _1}$ moves. It is clear that ${\mathcal {G}_{{\omega _1}}}(\mathfrak {A},\mathfrak {B})$ is determined if $\mathfrak {A}$ and $\mathfrak {B}$ are of cardinality $\leq {\aleph _1}$. We prove the following results: Theorem 1. If $V = L$, then there are models $\mathfrak {A}$ and $\mathfrak {B}$ of cardinality ${\aleph _2}$ such that the game ${\mathcal {G}_{{\omega _1}}}(\mathfrak {A},\mathfrak {B})$ is nondetermined. Theorem 2. If it is consistent that there is a measurable cardinal, then it is consistent that ${\mathcal {G}_{{\omega _1}}}(\mathfrak {A},\mathfrak {B})$ is determined for all $\mathfrak {A}$ and $\mathfrak {B}$ of cardinality $\leq {\aleph _2}$. Theorem 3. For any $\kappa \geq {\aleph _3}$ there are $\mathfrak {A}$ and $\mathfrak {B}$ of cardinality $\kappa$ such that the game ${\mathcal {G}_{{\omega _1}}}(\mathfrak {A},\mathfrak {B})$ is nondetermined.References
- J. Barwise and S. Feferman (eds.), Model-theoretic logics, Perspectives in Mathematical Logic, Springer-Verlag, New York, 1985. MR 819531
- Shai Ben-David, On Shelah’s compactness of cardinals, Israel J. Math. 31 (1978), no. 1, 34–56. MR 506381, DOI 10.1007/BF02761379
- Maxim R. Burke and Menachem Magidor, Shelah’s $\textrm {pcf}$ theory and its applications, Ann. Pure Appl. Logic 50 (1990), no. 3, 207–254. MR 1086455, DOI 10.1016/0168-0072(90)90057-9
- Paul C. Eklof and Alan H. Mekler, Almost free modules, North-Holland Mathematical Library, vol. 46, North-Holland Publishing Co., Amsterdam, 1990. Set-theoretic methods. MR 1055083
- F. Galvin, T. Jech, and M. Magidor, An ideal game, J. Symbolic Logic 43 (1978), no. 2, 284–292. MR 485391, DOI 10.2307/2272827
- Moti Gitik and Saharon Shelah, Cardinal preserving ideals, J. Symbolic Logic 64 (1999), no. 4, 1527–1551. MR 1780068, DOI 10.2307/2586794
- Leo Harrington and Saharon Shelah, Some exact equiconsistency results in set theory, Notre Dame J. Formal Logic 26 (1985), no. 2, 178–188. MR 783595, DOI 10.1305/ndjfl/1093870823
- Paul Hill, New criteria for freeness in abelian groups. II, Trans. Amer. Math. Soc. 196 (1974), 191–201. MR 352294, DOI 10.1090/S0002-9947-1974-0352294-8
- Wilfrid Hodges and Saharon Shelah, Infinite games and reduced products, Ann. Math. Logic 20 (1981), no. 1, 77–108. MR 611395, DOI 10.1016/0003-4843(81)90012-7
- Tapani Hyttinen, Games and infinitary languages, Ann. Acad. Sci. Fenn. Ser. A I Math. Dissertationes 64 (1987), 32. MR 881268
- Thomas Jech, Set theory, Pure and Applied Mathematics, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1978. MR 506523
- T. Jech, M. Magidor, W. Mitchell, and K. Prikry, Precipitous ideals, J. Symbolic Logic 45 (1980), no. 1, 1–8. MR 560220, DOI 10.2307/2273349
- Thomas Jech and Saharon Shelah, Full reflection of stationary sets below $\aleph _\omega$, J. Symbolic Logic 55 (1990), no. 2, 822–830. MR 1056391, DOI 10.2307/2274667
- R. Björn Jensen, The fine structure of the constructible hierarchy, Ann. Math. Logic 4 (1972), 229–308; erratum, ibid. 4 (1972), 443. With a section by Jack Silver. MR 309729, DOI 10.1016/0003-4843(72)90001-0
- 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
- Jean-Pierre Serre, Trees, Springer-Verlag, Berlin-New York, 1980. Translated from the French by John Stillwell. MR 607504, DOI 10.1007/978-3-642-61856-7
- Saharon Shelah, Generalized quantifiers and compact logic, Trans. Amer. Math. Soc. 204 (1975), 342–364. MR 376334, DOI 10.1090/S0002-9947-1975-0376334-6
- Saharon Shelah, Reflecting stationary sets and successors of singular cardinals, Arch. Math. Logic 31 (1991), no. 1, 25–53. MR 1126352, DOI 10.1007/BF01370693 —, Classification theory, rev. ed., North-Holland, 1990.
Additional Information
- © Copyright 1993 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 339 (1993), 567-580
- MSC: Primary 03C55; Secondary 03E05, 03E35, 03E55, 90D44
- DOI: https://doi.org/10.1090/S0002-9947-1993-1191613-1
- MathSciNet review: 1191613