# The Back-and-Forth Property See [[Barwise, Feferman (eds.) - Model-theoretic logics]] VIII.2 >[!info] Definition >A function $f$ from a structure $\mathfrak{M}$ to a structure $\mathfrak{N}$ (for the same vocabulary) is said to be a *partial isomorphism* from $\mathfrak{M}$ to $\mathfrak{R}$ if $f$ extends to an isomorphism of the substructure of $\mathfrak{M}$ generated by $\operatorname{dom} f$ onto the substructure of $\mathfrak{R}$ generated by range $f$. > >Let $\kappa$ be a cardinal. A set $F$ of partial isomorphisms from $\mathfrak{M}$ to $\mathfrak{N}$ is said to be a *$\kappa$-back and forth set* if for any $f \in F$ : (i) $\forall X \subseteq M[|X|<\kappa \rightarrow \exists g \in F[f \subseteq g \land X \subseteq \operatorname{dom} g]]$; (ii) $\forall Y \subseteq N[|Y|<\kappa \rightarrow \exists h \in F[f \subseteq h \land Y \subseteq \mathrm{ra} h]]$. > >If such a set $F$ exists, then we say that $\mathfrak{M}$ and $\mathfrak{N}$ have the *$\kappa$-back and forth property* or are *$\kappa$-partially isomorphic*, and write $\mathfrak{M} \cong_{p, \kappa} \mathfrak{N}$. >Denote $\cong_{p}=\cong_{p,\omega}$. > >A logic $\mathcal{L}$ has the *Karp property* if $\mathfrak{M} \cong_{p} \mathfrak{N}$ implies $\mathfrak{M} \equiv_{\mathcal{L}} \mathfrak{N}$. **Theorem (Karp's Theorem).** $\mathfrak{M} \equiv_{\infty \omega} \mathfrak{N}$ iff $\mathfrak{M} \cong_p \mathfrak{N}$. **Corollary.** If $|M|=|N|=\aleph_0$ and $\mathfrak{M} \equiv_{\infty \omega} \mathfrak{N}$, then $\mathfrak{M} \cong \mathfrak{N}$. **Theorem 1.2 (Lindström/Barwise).** If $\mathcal{L}$ is a Karp-logic in which $\langle\omega,<\rangle$ is not characterizable by a single sentence even with additional predicates, then $\mathcal{L}=\mathcal{L}_{\omega \omega}$. ## For generalized quantifiers **Def.** Back and forth property ![[Pasted image 20230212114055.png]] **Def.** Back and forth isomorphism ![[Pasted image 20230212114141.png]] ![[Pasted image 20230212114309.png]] **Def.** Monotone quantifier ![[Pasted image 20230212114346.png]] **Theorem.** ![[Pasted image 20230201101502.png]] # Ehrenfeucht-Fraïssé games *Ehrenfeucht-Fraïssé games*, or *back-and-forth* games, are a technique for determining whether two structrues have the back-and-forth property. The main idea given two structures, we play a game between two players – _Spoiler_ and _Duplicator_ (sometimes called Adam and Eve, Abelar and Eloise, or simply Player I and Player II). Duplicator wants to show that the two structures are similar, whereas Spoiler wants to show that they are different. Here "similar" and "different" ultimately mean "satisfy the same formulas of a certain logic". The exact rules of the game depend on the logic. Suppose $\mathfrak{A}$ and $\mathfrak{B}$ are structures of the same type and fix a logic $\mathcal{L}$. For every ordinal $\gamma$, a game $G_{\gamma}^{\mathcal{L}}(\mathfrak{A},\mathfrak{B})$ is defined by describing the possible moves at each turn, and the winning conditions for each player. ## Examples ### First order logic **$\exists$-move.** I chooses $x_i \in M \cup M^{\prime}$ and then II chooses $y_i \in M \cup M^{\prime}$ such that $ x_i \in M \Longleftrightarrow y_i \in M^{\prime} $ Duplicator wins if the map $x_{i} \mapsto y_{i}$ is a partial isomorphism. ### Generalized quantifiers Let $Q$ be a [[Generalized quantifiers|monotone generalized quantifier]]. **$Q$-move.** I first chooses $Y \in Q(M) \cup Q\left(M^{\prime}\right)$. Then II chooses $X \in Q(M) \cup$ $Q\left(M^{\prime}\right)$ such that $ Y \in Q(M) \Longleftrightarrow X \in Q\left(M^{\prime}\right) $ Now I chooses $x_i$ and finally II chooses $y_i$ such that $x_i \in X \Rightarrow y_i \in Y$ . ### From Models and Games sec 10.3 pg. 296 ![[Pasted image 20230212123614.png]] # Resources [[Ehrenfeucht - An application of games to the completeness problem for formalized theories]] [[Badger - An Ehrenfeucht game for the multivariable quantifiers of Malitz and some applications]] [[Vinner - A generalization of Ehrenfeucht’s game and some applications]] [[Väänänen - Models and Games]] [[Barwise, Feferman (eds.) - Model-theoretic logics]] VIII.2