Games and Lindström Theorems

The Ehrenfeucht–Fraïsse game for a logic usually provides an intuitive characterizarion of its expressive power while in abstract model theory, logics are compared by their expressive powers. In this paper, I explore this connection in details by proving a general Lindström theorem for logics which have certain types of Ehrenfeucht–Fraïsse games. The results generalize and uniform some known results and may be applied to get new Lindström theorems for logics.

1. \(L_{\infty \omega }\) is the same as first-order logic except that it allows conjunction (or disjunction) of arbitrarily many conjuncts (or disjuncts). \(L_{\kappa \omega }\) is the logic which allows conjunction (or disjunction) of less than \(\kappa \) many conjuncts (or disjuncts). First-order logic is just \(L_{\omega \omega }\).

2. Here we take a generous view about EF-games, which will be justified later by our framework.

3. For people who know partial isomorphism, you may notice this definition is not exactly the standard one. This is because in general when talking about the EF-game for first-order logic, people usually assume that the signature is relational so that the relation between \(EF_n(\mathfrak {A},\mathfrak {B})\) and \(\mathfrak {A}\equiv _n\mathfrak {B}\) is more beautiful (these two notations are defined below). Here we need to take constants into account. This adjustment is not in any sense essential but will make our presentation more elegant.

4. Although here \(L(\tau )\) is a class of sentences, we can and will allow it to be a class of formulas in Sects. 4 and 5 which are then evaluated at structures with designated elements. This adjustment is not in any sense essential. For example, see [16, Convention 1.10].

5. It may be a proper class instead of a set.

6. Whenever we write \(\psi \in L\), we mean that there exists a signature \(\tau \) s.t \(\psi \in L(\tau )\).

7. \((\mathfrak {A},U^A)\) is just the expansion of \(\mathfrak {A}\) with the interpretation of U (denoted as \(U^A\)).

8. In this paper, all those relations are symmetric, so there is no confusion caused when saying there is such a relation between \(\mathfrak {A}\) and \(\mathfrak {B}\).

9. For this notation, one can see [7, p.115].

10. When counting the quantifier rank of a formula, we count other quantifiers and first-order quantifiers equally.

11. In this sense, the definition covers simple unary generalized quantifiers, Lindström quantifiers and so on. See for example [12].

12. Although \(\Delta \) may be very complicated, for first-order logic, \(\backsim _\infty \) can just be partial isomorphisms by Theorem 2.3.

13. It is the least cardinal \(\mu \) s.t for any \(\varphi \in L\), there exists a signature \(\tau \) of cardinality less than \(\mu \) s.t \(\varphi \in L(\tau )\). Thus, if a logic has the finite occurrence property, then its occurrence number should be no greater than \(\omega \). For more details, see [3].

14. Here, \(\backsim _\infty \) is of course the one in the definition of codeable EF-games. For different logics, \(\backsim _\infty \) are actually different, but I believe no confusion would be caused.

15. The above proof strategy leading to this conclusion is exactly what we refer to later when we say “similar to the proof of Theorem 3.3”. It is frequently used in abstract model theory, see [3, Chap 3].

16. The reason why we need the reduct property here is that \(A'\) and \(B'\) may not be closed under the full signature of the structure \((\mathfrak {C},\mathfrak {A'}|_\tau ,\mathfrak {B'}|_{\tau '},P,<)\) where \(A'\) and \(B'\) are the universes of \(\mathfrak {A}'\) and \(\mathfrak {B}'\) respectively.

17. In [6], although the result only mentions the property of countably compactness explicitly, Caicedo implicitly assumes that the logics he consider have the finite occurrence property which allows him to use his Lemma 3.3.

18. In fact, we don’t even need to assume the renaming property for a logic.

19. Since I try to be as general as possible, a logic L may only be allowed to contain formulas of a certain signature \(\tau \). In that case, the following definitions and propositions should be interpreted w.r.t the right signature (e.g. \(\mathfrak {A}\) and \(\mathfrak {B}\) should be structures of signature \(\tau \), \(\varphi (\bar{x},\bar{y})\) in the definition of “symmetric definable EF-game” and \(\psi (\bar{x})\) in the theorems should be first-order formulas of signature \(\tau \) and so on).

20. For those who know bisimulation games, you may wonder why I don’t call it symmetric definable bisimulation game. The reason is that its generalized version - which I call “general definable EF-game” in the following does cover the standard EF-game for first-order logic.

21. Since \(L\subseteq L_{\omega \omega }\), the quantifier rank of a formula of L is defined in the standard way.

22. See [5, Thm. 2.68].

23. As we’ve mentioned above, L may only contain formulas of certain signatures. In that case, “for any signature” means “for any allowed or meaningful signature”. We could make this precise by saying that a signature \(\tau '\) is meaningless for L if there exists a proper subset \(\tau \) of \(\tau '\) s.t \(L(\tau )=L(\tau ')\). However, this point is not essential for the following proofs and results, and will make our statements more clumsy. Therefore, we don’t make it explicit in what follows.

24. As indicated in the third item in the following, the length of \(\bar{x}\) and \(\bar{y}\) may depend on the index j. We avoid more subscripts or subscripts in order to keep the notation more readable.

25. See Definition 2.2.

26. Take the 2-variable fragment \(L^2_{\omega \omega }\) of \(L_{\omega \omega }\) as an example: \(\varphi _1(x_1,x_2,y_1,y_2):=x_1=y_1\vee x_2=y_2\) and \(\varphi _2(x_1,x_2,y):=x_1=y\vee x_2=y\) define the EF-game for \(L^2_{\omega \omega }\). To see that the logic is closed under \(\varphi _1,\varphi _2\), let \(\psi (x_1,x_2)\in L^2_{\omega \omega }\) (W.L.O.G assume that \(y_1,y_2\) don’t occur in \(\psi (x_1,x_2)\) and \(x_1,x_2\) do have free occurrences in \(\psi (x_1,x_2)\), then the set of all variables in \(\psi (x_1,x_2)\) is \(\{x_1,x_2\}\) as \(\psi (x_1,x_2)\in L^2_{\omega \omega }\)), then \(\exists x_1\exists x_2(\varphi _1(x_1,x_2,y_1,y_2)\wedge \psi (x_1,x_2))=\exists x_1\exists x_2((x_1=y_1\vee x_2=y_2)\wedge \psi (x_1,x_2))\textit{ eq } \exists x_1\exists x_2((x_1=y_1\wedge \psi (x_1,x_2))\vee (x_2=y_2\wedge \psi (x_1,x_2)))\textit{ eq }\exists x_1\exists x_2(\psi (y_1/x_1,x_2)\vee \psi (x_1,y_2/x_2)) \textit{ eq } \exists x_2 \psi (y_1/x_1,x_2)\vee \exists x_1\psi (x_1,y_2/x_2)\) where \(y_1/x_1(y_2/x_2)\) means that \(y_1(y_2)\) replaces every occurrence of \(x_1(x_2)\), no matter bounded or free. Now, we have \(\exists x_2 \psi (y_1/x_1,x_2) \textit{ eq }\exists y_2\psi (y_1/x_1,y_2/x_2)\) and \(\exists x_1\psi (x_1,y_2/x_2)\textit{ eq } \exists y_1\psi (y_1/x_1,y_2/x_2)\). \(\exists x_2 \psi (y_1/x_1,x_2)\vee \exists x_1\psi (x_1,y_2/x_2)\textit{ eq }\exists y_2\psi (y_1/x_1,y_2/x_2)\vee \exists y_1\psi (y_1/x_1,y_2/x_2)\in L^2_{\omega \omega }\). \(L^2_{\omega \omega }\) is closed under \(\varphi _1\). The closure under \(\varphi _2\) can be shown similarly.

27. The guarded fragment of first-order logic is the same as first-order logic, except that it only allows guarded quantification: \(\exists \bar{x}(\alpha (\bar{x},\bar{y})\wedge \varphi (\bar{x},\bar{y}))\) and \(\forall \bar{x}(\alpha (\bar{x},\bar{y})\rightarrow \varphi (\bar{x},\bar{y}))\) where \(\alpha \) is an atomic formula containing all free variables of \(\varphi \) (called a “guard”). See [1] and [10] for details.

28. This may remind you of the (Robinson) diagram of a structure, see [11, p. 16] .

29. Namely, there is no formula \(\psi (\bar{x})\) of \(L(\tau )\) s.t \(T\vDash _{L'} \psi (\bar{x})\leftrightarrow \varphi (\bar{x})\). As \(L'\) is an extension of L, we can view T as a set of formulas of \(L'(\tau )\) and \(\psi (\bar{x})\) as a formula of \(L'(\tau )\). Thus the notation is justified.

30. Here it is crucial that \(\exists \bar{x}(\varphi _j(\bar{x},\bar{y})\wedge \psi (\bar{x}))\) is itself a formula of \(L(\tau )\). For otherwise, even if L is closed under subformulas, it is not necessary the case that \(\varphi _j(\bar{x},\bar{y})\in L\).

31. Set occurrence property is assumed in the background.

32. It’s not difficult to see that there is a balance between compactness and set occurrence property. For example, we can replace compactness by countably compactness, but then we need to strengthen set occurrence property to the finite occurrence property and require that the cardinality of the set of formulas in a finite signature should be countable.

33. It is worth noticing that \(\varphi _1\) and \(\varphi _2\) don’t belong to \(L^2_{\omega \omega }\).

34. Note that set occurrence property and closure under constants are assumed in the background. In particular, in Barwise and Feferman [3], the logics they consider are assumed to be regular (slightly stronger than our definition) and has finite occurrence property. For convenience, we will state the theorem in our terms.

35. In fact, if we assume a logic \(L\subseteq L_{\omega \omega }\) admits naming, it’s easy to see that if \(\psi (\bar{a})\in L\) implies \(\exists \bar{x} \psi (\bar{x})\in L\), then \(L\equiv L_{\omega \omega }\). Thus the proof strategy really belongs to first-order logic specifically. This is a bit surprising if you consider the original Lindström theorem for first-order logic: we don’t need the whole first-order logic to make the proof work, so the proof strategy can be applied to fragments of first-order logic. See van Benthem, ten Cate and Väänänen [4] .

The author thank Jouko Väänänen for his guidance during the project named “Some aspects of EF-games”, during which the original version of this paper came out. The author is also grateful to the anonymous reviewers of GandALF 2022 for their useful comments on the writing of the original version of this paper.

Authors and Affiliations

1. Institute for Logic, Language and Computation (ILLC), University of Amsterdam, Naritaweg 6C6, 1043BX, Amsterdam, The Netherlands

   Cheng Liao

Corresponding author

Correspondence to Cheng Liao.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This work was completed with the support of Prof. Jouko Väänänen, who gave me many useful comments on the original report.

Springer Nature or its licensor holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions