Weak Ehrenfeucht-Fraïssé games

Hyttinen, Tapani; Kulikov, Vadim

doi:10.1090/S0002-9947-2011-05222-0

Weak Ehrenfeucht-Fraïssé games
HTML articles powered by AMS MathViewer

by Tapani Hyttinen and Vadim Kulikov PDF

Trans. Amer. Math. Soc. 363 (2011), 3309-3334 Request permission

Abstract:

In this paper we define a game which is played between two players $\textbf {I}$ and $\textbf {II}$ and two mathematical structures $\mathcal {A}$ and $\mathcal {B}$. The players choose elements from both structures in $\alpha$ moves, and at the end of the game player $\textbf {II}$ wins if the chosen structures are isomorphic. Thus the difference between this and the ordinary Ehrenfeucht-Fraïssé game is that the isomorphism can be arbitrary, whereas in the ordinary EF-game it is determined by the moves of the players. We investigate determinacy of the weak EF-game for different $\alpha$ (the length of the game) and its relation to the ordinary EF-game.

References

M. Burke and M. Magidor: Shelah’s pcf theory and its applications, Annals of Pure and Applied Logic, 1990.
Tapani Hyttinen, Games and infinitary languages, Ann. Acad. Sci. Fenn. Ser. A I Math. Dissertationes 64 (1987), 32. MR 881268
Tapani Hyttinen, Saharon Shelah, and Heikki Tuuri, Remarks on strong nonstructure theorems, Notre Dame J. Formal Logic 34 (1993), no. 2, 157–168. MR 1231281, DOI 10.1305/ndjfl/1093634649
Tapani Hyttinen, Saharon Shelah, and Jouko Väänänen, More on the Ehrenfeucht-Fraïssé game of length $\omega _1$, Fund. Math. 175 (2002), no. 1, 79–96. MR 1971240, DOI 10.4064/fm175-1-5
Thomas Jech, Set theory, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2003. The third millennium edition, revised and expanded. MR 1940513
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
David W. Kueker, Countable approximations and Löwenheim-Skolem theorems, Ann. Math. Logic 11 (1977), no. 1, 57–103. MR 457191, DOI 10.1016/0003-4843(77)90010-9
Alan Mekler, Saharon Shelah, and Jouko Väänänen, The Ehrenfeucht-Fraïssé-game of length $\omega _1$, Trans. Amer. Math. Soc. 339 (1993), no. 2, 567–580. MR 1191613, DOI 10.1090/S0002-9947-1993-1191613-1
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
S. Shelah, Classification theory and the number of nonisomorphic models, 2nd ed., Studies in Logic and the Foundations of Mathematics, vol. 92, North-Holland Publishing Co., Amsterdam, 1990. MR 1083551