# Abstract $L_{\infty \omega}(K)$ is the logic obtained by adding a Lindström's quantifier $K \vec{x}_1 \ldots \vec{x}_k\left(\phi_1\left(\vec{x}_1\right) \ldots \phi_k\left(\vec{x}_k\right)\right)$ to the logical operations of $L_{\infty \omega}$. The corresponding finitary logic is $L_{\omega \omega}(K)$, and $L_{\infty \omega}\left(K_i\right)_{i \in I}$ is obtained by adjoining a family of quantifiers. In this paper, we give back-and-forth systems characterizing elementary equivalence in those logics and their fragments of bounded quantifier rank. This generalizes work of Fraissé and Ehrenfeucht for $L_{\omega \omega}$, Karp for $L_{\infty \omega}$, Brown, Lipner, and Vinner for cardinal quantifiers, Badger for Magidor-Malitz quantifiers, and others. Our systems apply to higher order quantifiers also. # 1. Generalized Quantifiers A *quantifier symbol* is a symbol $Q$ together with a sequence of positive integers $\left\langle n_1, \ldots, n_k\right\rangle$ called the *type* of the quantifier symbol. **Formation rule:** If $Q$ is a quantifier symbol of type $\left\langle n_1, \ldots, n_k\right\rangle, \phi_1, \ldots, \phi_k$ are formulas, and $\vec{x}_1, \ldots, \vec{x}_k$ are lists of $n_1, \ldots, n_k$ variables, respectively, then $Q \vec{x}_1, \ldots, \vec{x}_k\left(\phi_1, \ldots, \phi_k\right)$ is a formula. It is understood that only those free variables of $\phi_i$ which appear in the list $\vec{x}_i$ are bound by the quantifier. **Interpretation:** If $\mathfrak{A}$ is a structure and If $Q$ is a quantifier symbol of type $\left\langle n_1, \ldots, n_k\right\rangle$, then an *interpretation of $Q$ in $\mathfrak{A}$* is $\mathfrak{q} \subseteq \mathcal{P}(A^{n_{1}})\times\dots\times\mathcal{P}(A^{n_{k}})$. So $(\mathfrak{A,q})\vDash Q \vec{x}_1, \ldots, \vec{x}_k\left(\phi_1, \ldots, \phi_k\right)$ iff $\begin{aligned} & \left( \pi \vec{x}_1 \phi_1, \dots, \pi \vec{x}_k \phi_k\right) \in \mathfrak{q} \text { where } \\ & \pi \vec{x} \phi=\left\{\vec{a} \mid(\mathfrak{A,q}) \vDash \phi(\vec{x} / \vec{a})\right\} . \end{aligned}$ # 2. Back-and-forth systems >[!info] Definition >A back-and-forth between $(\mathfrak{A} ; \mathfrak{q})$ and $(\mathfrak{B} ; \mathfrak{r})$ consists of a linearly ordered set $\mathrm{P}=(P,<)$, called the set of parameters, and a family $\left\{E_n^P \mid p \in P\right\}$ of equivalence relations in $A^n \cup B^n$ for each $n \in \omega$, satisfying: >> (i) $\emptyset \stackrel{p}{\sim} \emptyset$ >>(ii) (Extension property). Let $s=\max \left\{n_1, \ldots, n_k\right\}$ and $p<p_1<\ldots<$ $p_s=p^{\prime}$, then for all sequences $\sigma$ in $A$ and $\tau$ in $B$ such that $\sigma \stackrel{p}{\sim} \tau$ there exist functions $f_i: A^{n_{i}} \rightarrow B^{n_i}, 1 \leqslant i \leqslant k$, such that: >>>(A) $\sigma \vec{a} \stackrel{p}{\sim} \tau f_i(\vec{a})$ for all $\vec{a} \in A^{n_i}, 1 \leqslant i \leqslant k$. >>>(B) If $X_i \subseteq A^n, 1 \leqslant i \leqslant k$, then $\left(\left[X_1\right]_\sigma^p, \ldots,\left[X_k\right]_\sigma^p\right) \in \mathfrak{q}$ implies $\left(\left[f_1^{\prime}\left(X_1\right)\right]_\tau^p, \ldots,\left[f_k^{\prime}\left(X_k\right)\right]_\tau^p\right) \in \mathfrak{r}$. >> >> (iii) As (ii), interchanging the roles of $A$ and $B$. > >(iv) (Isomorphism property). If $\left(a_1, \ldots, a_n\right) \stackrel{p}{\sim}\left(b_1, \ldots, b_n\right)$ then the assignment $a_i \mapsto b_i$ is a partial isomorphism from $\mathfrak{A}$ to $\mathfrak{B}$. > > A back-and-forth for a collection of quantifiers is a system which is a back-and-forth for each of them. Where: >>[!note] Notation >>$\sigma \overset{p}{\sim} \sigma^{\prime}$ denotes $\left(\sigma, \sigma^{\prime}\right) \in E_n^p$; the value of $n$ will be clear from the context. >> >>For each $\sigma \in A^k$, $\vec{a}$ and $p\in P$ >> $ >> [\vec{a}]_\sigma^p=\left\{\vec{x} \in A^n \mid \sigma \vec{x} \stackrel{p}{\sim} \sigma \vec{a}\right\} >> $ >> is the corresponding equivalence class of $\vec{a}$ in $A^n$. If $X \subseteq A^n$ we write, abusing the language, $[X]_\sigma^p=\cup\left\{[\vec{a}]_\sigma^p \mid \vec{a} \in X\right\}$. >> Analogous notation valid with respect to sequences in $\mathrm{B}$. **Theorem** For structures $\mathfrak{A,B}$ with corresponding collections $C,D$ of interpretations for quantifiers: (a) $(\mathfrak{A} ; C) \stackrel{\alpha}{\equiv}(\mathfrak{B} ; D)$ iff $(\mathfrak{A} ; C) \stackrel{(\alpha,<)}{\sim}(\mathfrak{B} ; D)$. (b) $(\mathfrak{A} ; C) \stackrel{\infty}{\equiv}(\mathfrak{B} ; D)$ iff $(\mathfrak{A} ; C) \stackrel{(\alpha,<)}{\sim}(\mathfrak{B} ; D)$ for all ordinals $\alpha$.