An Ehrenfeucht-Fraïssé game for \(\mathcal L_{\omega_1\omega}\) (Q2856638)

Ehrenfeucht-Fraïssé games, sometimes called back and forth games, have played an important role in the model theory both of first-order logic and of extended logics. Ehrenfeucht-Fraïssé games are used, among others, in order to give an algebraic characterization of those pairs of structures which satisfy the same class of \(\mathcal L\)-sentences, for various logics \(\mathcal L\). Some basic results are recalled by the authors; further details, applications and references can be found in [\textit{C. C. Chang} and \textit{H. J. Keisler}, Model theory. 3rd rev. ed. Amsterdam etc.: North-Holland (1990; Zbl 0697.03022); \textit{J. Barwise} (ed.) and \textit{S. Feferman} (ed.), Model-theoretic logics. New York: Springer (1985; Zbl 0587.03001; Zbl 0587.03002)].NEWLINENEWLINERecall that \(\mathcal L_{ \omega _1,\omega} \) is the extension of first-order logic in which countable disjunctions and conjunctions of formulas are allowed. On the one hand, in many respects, \(\mathcal L _{ \omega _1, \omega } \) and its fragments are the best behaved among infinitary logics; on the other hand, and strangely enough, it seems that no appropriate Ehrenfeucht-Fraïssé game has been developed before for \(\mathcal L _{ \omega _1, \omega } \).NEWLINENEWLINEIn the present paper, the authors successfully develop a useful Ehrenfeucht-Fraïssé game for \(\mathcal L _{ \omega _1, \omega } \) and prove an adequacy theorem. The main tool is a notion of size (a measure of complexity) of an \(\mathcal L _{ \omega _1, \omega } \)-formula. The size is defined in terms of infinite natural sums of ordinals, and it is a measure of complexity finer than the more usual quantifier rank: the size of, say, a conjunction is always strictly larger than the sizes of the conjuncts.NEWLINENEWLINEMore generally, the authors carry over an abstract study of possible ``nice complexity measures'' and prove a generalized adequacy theorem relative to such measures and for a suitable variation on the game. They also give applications of the game to the study of complexity of properties of infinite binary stringsNEWLINENEWLINEAt the end, the authors briefly discuss the problems that arise when trying to generalize their results to larger infinitary languages, e.g., \(\mathcal L _{ \omega _2, \omega }\). They show that there is no natural generalization of size which satisfies some natural properties.NEWLINENEWLINE Remark. However, not all the above ``natural'' properties of size are used in the proofs of the adequacy theorems, hence, it is highly plausible that most results of the paper generalize to \(\mathcal L _{ \lambda,\omega }\), for an arbitrary cardinal \(\lambda\), and for some appropriate variation on the notion of size.