Suppose $A\equiv B$ and $A$ is $\omega$-saturated. Prove that $B$ is $\omega$-saturated iff $A$ is back-and-forth equivalent to $B$.

logicmodel-theorysolution-verification

Hodges' Shorter Model Theory ex 6.2.5: Suppose $A\equiv B$ and $A$ is $\omega$-saturated. Prove that $B$ is $\omega$-saturated iff $A$ is back-and-forth equivalent to $B$..

  1. I am stuck on the left to right direction, and is not at all certain if my right to left is correct.

  2. I am also not sure if $A\equiv B$ necessitates $(A,\bar a)\equiv(B,\bar b)$.

Could anyone check for me please?

My attempt:

Left to right: assume that $A\equiv B$, $A$ and $B$ are $\omega$-saturated. We are gonna prove that $A$ is back-and-forth equivalent to $B$, i.e. player $\exists$ has a winning strategy for the game $EF_{\omega}(A,B)$.

At the end of the game, sequences $\bar a=(a_i:i<\gamma)$ and $\bar b=(b_i:i<\gamma)$ have been chosen.

$\exists$ wins the game with the play $(\bar a, \bar b)$ iff $(A,\bar a)\equiv_0(B,\bar b)$, i.e. for every atomic sentence $\phi$ of language $L$, $A\vDash \phi \iff B\vDash \phi$. A winning strategy is a description of how to generate a play $(\bar a, \bar b)$ such that should $\exists$ follow this strategy, he always wins.

$A\equiv B$ means they are elementarily equivalent, i.e. for every sentence $\phi$ of $L$, $A\vDash \phi \iff B\vDash \phi$. And for $A$ to be $\omega$-saturated, it means if $(A,\bar a)\equiv (B,\bar b)$ and $d\in B$, there is a $c\in A$ such that $(A,\bar a, c)\equiv(B,\bar b,d)$. Likewise for $B$.

Suppose we have a play $(\bar a,\bar b)$. We expand $A$ and $B$ to form the structure $(A,\bar a)$ and $(B,\bar b)$ respectively. Since $A\equiv B$, it is also the case that $(A,\bar a)\equiv(B,\bar b)$. But from the definition of $\omega$-saturated, this gives us $(A,\bar a, c)\equiv(B,\bar b,d)$. But since being elementarily equivalent means that they both satisfy every sentence in $L$, this must include atomic sentence as well, thereby satisfying $(A,\bar a, c)\equiv_0(B,\bar b,d)$.

(Stuck)

Right to left:

Suppose $(A,\bar a)\equiv (B,\bar b)$ and we have a $c\in A$, we need to prove that there is a $d\in B$ such that $(A,\bar a, c)\equiv(B,\bar b,d)$. We also know that $(A,\bar a)\equiv_0 (B,\bar b)$.

Furthermore, $A$ is $\omega$-saturated, i.e. if $(A,\bar a)\equiv (B,\bar b)$ and $d\in B$, there is a $c\in A$ such that $(A,\bar a, c)\equiv(B,\bar b,d)$.

Since $A$ is $\omega$-saturated, and we assumed $(A,\bar a)\equiv (B,\bar b)$ and that there is a $c\in A$, we get $(A,\bar a, c)\equiv(B,\bar b,d)$.

Best Answer

($\Rightarrow$) The strategy of $\exists$ is as follows. Assume as induction hypothesis that $(A,\bar a)\equiv (B,\bar b)$ and suppose that $\forall$ plays $d\in B$. Then $\exists$ plays $c\in A$ such that $(A,\bar a, c)\equiv(B,\bar b,d)$. Likewise if $\forall$ plays an element of $A$.

At the and of the game $\bar a=(a_i:i<\color{blue}\omega)$ and $\bar b=(b_i:i<\color{blue}\omega)$ have been chosen such that $(A,\bar a)\equiv (B,\bar b)$ and a fortiori $(A,\bar a)\equiv_0 (B,\bar b)$.

($\Leftarrow$) Assume that $A$ and $B$ are both countable. Then $\forall$ can force that $\bar a=(a_i:i<\omega)$ and $\bar b=(b_i:i<\omega)$. enumerate $A$, respectively $B$, then $(A,\bar a)\equiv_0(B,\bar b)$ implies that $A\simeq B$ hence $B$ is also $\omega$-saturated.

EDIT: the uncountable case.

The general case, (no assumption of the cardinality of $A$ and $B$) is more complicated so I only sketch it.

For semplicity we may assume that $L$ is countable (otherwise we need a transfinite EF-game). Let $\bar b$ a finite tuple of elements of $B$. Let $\bar a$ be the result of $\forall$ playing $\bar b$ and $\exists$ responding with the winning strategy. It is well-known that $(A,\bar a)\equiv(B,\bar b)$.

Let $p(x,\bar b)$ a type finitely consistent in $B$. We claim $p(x,\bar b)$ is realized in $B$ (this will prove the saturation of $B$).

By elementarity $p(x,\bar a)$ is finitely consistent in $A$, and by saturation it is realized by some $c\in A$. Let $\forall$ play $c$ and let $d$ be the response of $\exists$. We claim that $B,d\models p(x,\bar b)$.

Let $\bar a'=(a'_i:i<\color{blue}\omega)$ and $\bar b'=(b'_i:i<\color{blue}\omega)$ be the result of the game where $\forall$ plays so that $A'=\{a'_i:i<\color{blue}\omega\}$ is an elementary substructure of $A$ and, similarly, $B'=\{b'_i:i<\color{blue}\omega\}$ is an elementary substructure of $B$. The strategy of $\forall$ is that of the downward Löwenheim-Skolem theorem. (Here we use that $L$ is countable.)

If $\exists$ replies with her winning strategy, in the end we obtain $A'\simeq B'$. As $A,c\models p(x,\bar a)$ then $B,d\models p(x,\bar b)$. QED

Related Question