In the heyday of infinitary logic in the 1960’s and 70’s, most attention was focused on \(L_{\omega_1\omega}\) and its fragments [see, e.g., H. J. Keisler, Model theory for infinitary logic (North Holland, Amsterdam) (1971; Zbl 0222.02064)], since countable formulas seemed best behaved. The past decade has seen a renewed interest in \(L_{\infty \omega}\) and its finite variable fragments \(L^{(k)}_{\infty\omega}\) (for \(2\leq k<\omega\)) and the modal fragment of \(L^{\lozenge}_{\infty\omega}\) [see, e.g., H.-D. Ebbinghaus and J. Flum, Finite model theory (Springer, Berlin) (1995; Zbl 0841.03014), on the former, and J. Barwise and L. Moss, Vicious circles. On the mathematics of non-wellfounded phenomena (CSLI Lect. Notes 60, CSLI, Stanford) (1996; Zbl 0865.03002), on the latter], due to various connections with topics in computer science. These logics form a hierarchy of increasingly powerful logics \[ L^{\lozenge}_{\infty\omega}\subset L^{(2)}_{\infty\omega}\subset L^{(3)}_{\infty\omega}\subset\cdots\subset L^{(k)}_{\infty\omega}\subset \cdots\subset L_{\infty\omega}, \] with each of these inclusions being proper. Moreover, there is a useful and elegant algebraic characterization of equivalence in \({\mathcal L}\) in each of these logics \({\mathcal L}\), from bisimilarity at the left end to potential isomorphism at the right. These algebraic relations on structures are often defined by what is called a “pebble game”, a game between two players, one of whom wants to show that the structures are not equivalent, the other who wants to show they are.
Most of the recent work involving the finite variable fragments \(L^{(k)}_{\infty\omega}\) has focused on finite structures. As a result, there are many open questions regarding these logics when one drops the restriction to finite structures – questions that should really have been settled in the 70’s, but were overlooked, probably due to the preoccupation with \(L_{\omega_1\omega}\). We address a certain class of these questions in this paper, namely, questions involving interpolation and preservation. The following is a sample result: if a sentence \(\varphi\) of \(L_{\infty\omega}\) is preserved under bisimulation then it is logically equivalent to a sentence of the modal fragment \(L^{\lozenge}_{\infty\omega}\). We obtain this as a corollary to an interpolation theorem relating \(L_{\infty\omega}\) and \(L^{\lozenge}_{\infty\omega}\).
A glance through this paper will show that we have obtained a number of results of this same general character: an interpolation theorem with a preservation theorem as consequence. The proofs all use a single method. We introduce this method by proving an interpolation theorem for \(L_{\infty\omega}\) in this section. In Section 2, we extract a general method by analyzing this proof of interpolation in terms of “co-inductive pebble games”. This analysis results in a certain “abstract interpolation theorem” which is then applied to yield other results in Section 3. Section 4 discusses some open questions.