# Abstract # I. AN OMITTING TYPES THEOREM FOR STATIONARY LOGIC [[Barwise, Kaufmann, Makkai - Stationary logic]] # II. A COUNTEREXAMPLE TO INTERPOLATION FOR STATIONARY LOGIC # III. BACK-AND-FORTH SYSTEMS FOR SOME LOGICS WITH GENERALIZED QUANTIFIERS In this chapter we give and apply some back-and-forth criteria for two structures to satisfy the same sentences of a given logic. In $\S 1,2$, and 6 (respectively) we give such criteria for the logics $L(Q)$ (and $L_{\infty \omega}(Q)$ ), L(aa) (and $\left.\mathrm{L}_{\infty \omega}(a a)\right)$, and Keisler's probability Iogic $\mathrm{L}_{\omega \mathrm{P}}$. $\S \S 3,4$, and 5 involve applications of the back-and-forth criteria developed for "determinate" structures for stationary logic in $\S 2$, and also include some relevant examples. We conclude with some open questions in $\S 7$. >[!info] Definition >For any set $\left\{Q_i: i \varepsilon I\right\}$ of quantifiers, $L_{\infty \omega}\left(\left\{Q_i: i \in I\right\}\right)$ denotes a logic with the following class of formulas: it is the least class of formulas containing all atomic formulas of $L$, which closed under negation, disjunction, and the operations $\phi(x, \vec{y}) \mapsto Q_i x \phi(x, \vec{y}) \quad$ (for each $i \varepsilon I$ ). > The *quantifier rank* $\operatorname{qr}(\phi)$ of a formula $\phi$ of this logic is defined by induction on the complexity of $\phi$ (in the usual manner) as follows: $\operatorname{qr}(\phi)=$ > $ > \begin{array}{ll} > 0 & \text { if } \phi \text { is atomic } \\ > \operatorname{qr}(\psi) & \text { if } \phi \text { is } \neg \psi . \\ > \operatorname{qr}(\psi)+1 & \text { if } \phi \text { is } Q_i x \psi \text {; and } \\ > \sup (\operatorname{qr}(\psi): \psi \varepsilon \Psi\} & \text { if } \phi \text { is } \bigvee \Psi . > \end{array} > $ > > $L_{\infty \omega}(\mathtt{aa})$ is the infinitary version of $L(\mathtt{aa})$. Its class of formulas is the least class containing all formulas of $L(\mathtt{aa})$ which is closed under all the operations of $L(\mathtt{aa})$, as well as arbitrary disjunctions. (The notion of satisfaction is extended to $\mathrm{L}_{\infty\omega}(\mathtt{aa})$ in the obvious manner.) > The *quantifier rank* of a formula of $\mathrm{L}_{\infty \omega \omega}$ (aa) is defined just as above except for the following additional clause: $\operatorname{qr}(\phi)=\operatorname{qr}(\psi)+1 \quad\text{ if } \phi \text{ is } \mathtt{aa} s \psi. $ >[!info] Definition >Let $\underline{A}$ and $\underline{B}$ be two structures for the same language, and let $L^{*}$ be any logic. >$\underline{A}$ and $\underline{B}$ are $L^{*}$-equivalent if $\underline{A}$ and $\underline{B}$ satisfy the same sentences of $L^{*}$; in symbols, $\underline{A} \equiv \underline{B}(L*)$. >$\underline{A}$ and $\underline{B}$ are $(L*,\alpha)$-equivalent if $\underline{A}$ and $\underline{B}$ satisfy the same sentences of $L^{*}$ of quantifier rank at most $\alpha$; in symbols, $\underline{A} \equiv^\alpha \underline{B}\left(L^*\right)$. ## §1. Back-and-forth systems for weak models of $L(Q)$ ## §2. Back-and-forth systems for stationary logic. >[!note] Notation >Let $\mathrm{P}_{\omega_1}(\mathrm{X})$ denote the set of all countable subsets of $X$, for any set $X$. For two sets $A$ and $B$, we write $A * B$ to represent the set $[A \times B] \cup\left[P_{\omega_1}(A) \times P_{\omega_1}(B)\right]$. If $\vec{x}$ and $\vec{s}$ are sequences of first- and second-order variables, respectively, and $f \subseteq A* B$, then $f$ has type $(\vec{x}, \vec{s})$ if $\operatorname{card}(f \cap[A \times B])=\operatorname{card}(\vec{x})$ and $\operatorname{card}\left(f \cap\left[\mathrm{P}_{\omega_1}(A) \times \mathrm{P}_{\omega_1}(B)\right]\right) = \operatorname{card}(\vec{s})$ > > Suppose that $\underline{A}$ and $\underline{B}$ are L-structures, and that $f$ is a partial function from $A$ to $B$. > We write "$\underline{A} \vDash \phi(\operatorname{dom} f)$ iff $\underline{B} \vDash \phi( \mathrm{rn} f)quot; as an abbreviation for the following statement: > - For any assignment $g$ from the free variables $\left(x_1, \ldots, x_n\right)$ of $\phi$ to $A$, if the range of $g$ is contained in the domain of $f$, then $\underline{A} \vDash \phi\left(g\left(x_1\right), \ldots, g\left(x_n\right)\right) \quad$ iff $\underline{B}=\phi\left(f\left(g\left(x_1\right)\right), \ldots, f\left(g\left(x_n\right)\right)\right)$. > > A similar abbreviation is defined for $f \subseteq A*B$ >[!info] Definition > Fix two L-structures $\underline{A}$ and $\underline{B}$. $\left(F_\beta: \beta \leq \alpha\right)$ is an *$(L(\mathtt{aa}),\alpha)$ back-and-forth system from $\underline{A}$ to $\underline{B}$* if the following conditions are satisfied. > (1) For all $f \in F_0$, $f \subseteq A * B$ and for every atomic formula $\phi, \underline{A}\vDash\phi(\operatorname{dom} f)$ iff $\underline{B}\vDash\phi(\operatorname{rn} f)$. > (2) $0 \in F_\alpha$. > (3) Whenever $\gamma<\beta \leq \alpha$ and $f \in F_\beta$ : > > (i) $(\forall a \in A)(\exists b \in B)\left[f \cup\{(a, b)\} \in F_\gamma\right]$, > (ii) $(\forall b \in B)(\exists a \in A)\left[f \cup \{(a, b)\} \in F_\gamma\right]$, > (iii) $\left(\mathtt{aa}s \in P_{\omega_1}(A)\right) \left(\mathtt{stat}t \in P_{\omega_1}(B)\right) \left[f \cup\{(s, t)\} \in F_\gamma\right]$ > (iv) $(\mathtt{aa} t \in P_{\omega_1} (B))(\mathtt{stat} s \in P_{\omega_1}(A)) \left[f \cup \{(s, t)\} \in F_\gamma\right]$ > > $\left(F_n: n<\omega\right)$ is an *$L(\mathtt{aa})$ back-and-forth system from $\underline{A}$ to $\underline{B}$* if for each $k<\omega,\left(F_n: n \leq k\right)$ is an $\left(L(\mathtt{aa}), k\right)$ back-and-forth system from $\underline{A}$ to $\underline{B}$. > ^a59ff8 >[!note] Remark > We could also impose two other conditions in the above definition. > (4) Whenever $\gamma<\beta \leq \alpha, F_\beta \subseteq F_\gamma$. > (5) For all $\beta \leq \alpha, f \in F_\beta$, and $s_1, s_2 \in P_{\omega_1}(A) \cap \mathrm { dom } f$ > $ > \begin{aligned} > & s_1 \subseteq s_2 \quad \text { iff } \\ > & f\left(s_1\right) \subseteq f\left(s_2\right) \quad \text { iff } \operatorname{not}\left(s_2 \subseteq s_1\right) \quad \text { iff } \\ > & \operatorname{not}\left(f\left(s_2\right) \subseteq f\left(s_1\right)\right) . > \end{aligned} > $ > > The proofs show that all of our theorems remain true if we add these conditions to Definition 2.2 (or to the **2.4 THEOREM.** Let $\underline{A}$ and $\underline{B}$ be two L-structures. If there is an ($L(\mathtt{aa})$, $\alpha$) back-and-forth system from A to $\underline{B}$, then $\underline{A} \equiv^\alpha \underline{B}\left(L_{\infty \omega}(\mathtt{aa})\right)$. The converse is true if $\alpha<\omega$ and $L$ is finite. ^3b15e5 # IV. A sentence of $L(\mathtt{aa})$ which is not expressible in $L_{\infty\infty}$ The language for the sentence contains lt;,R,\varepsilon$ as binary predicates and $U,V,P^{U},P^{V}$ as unary predicates. - Let $\psi$ be the conjunction of the following: 1. $(U,<),(V,<)$ are disjoint well orderings, and lt;\, \subseteq U\times U \cup V \times V$. 2. $\varepsilon$ is an extensional relation which is a subset of $\mathrm{U} \times \mathrm{P}^{U} \cup V \times \mathrm{P}^{U}$. So we can think of the elements of $\mathrm{P}^{U}$ and $\mathrm{P}^V$ as being subsets of $U$ and $V$. 3. $P^{U}=P_{\omega_{1}}(U)$ and $P^{V}=\mathcal{P}_{\omega_1}(V)$ 4. $\forall x \forall y\left[R(x, y) \leftrightarrow P^U(x) \wedge P^V(y) \wedge(x,<{\restriction} x)\cong(y,<{\restriction} y)\right]$ All these can be formulated as $\mathcal{L}_{\omega_{1}\omega_{1}}$ sentences. - Let $\phi$ be the $L(\mathtt{aa})$ sentence $\mathtt{aa}s \exists x \exists y\left[ P^U(x) \wedge P^V(y) \wedge x=s\cap U \wedge y=s\cap V \wedge R(x,y)\right]$ **Lemma.** For a model $\mathfrak{A}$ of the above language, $\mathfrak{A}\vDash \psi \land \phi$ iff $(U^{\mathfrak{A}},<^{\mathfrak{A}})\cong(V^{\mathfrak{A}},<^{\mathfrak{A}})$ **Theorem (Malitz).** No sentence of $L_{\infty\infty}$ can express isomorphism between two arbitrary well-orders. **Corollary.** There is no sentence in $L_{\infty\infty}$ which is equivalent to $\phi$.