Skip to main content
1 of 3
Emil Jeřábek
  • 47.8k
  • 4
  • 151
  • 209

$\let\fii\varphi\def\fk{\mathfrak}\def\cL{\mathcal L}\def\aeba{A\exists B\forall}\let\TO\Rightarrow$Here is a quick and dirty proof that Q1 is true for countable languages. I have no doubts it holds for uncountable languages as well, though this may require a more elaborate argument.

So, assume that $\fii$ is not equivalent over $T$ to an $\cL_{A\exists B\forall}$ sentence. This implies $T+(T+\fii)_{\aeba}\nvdash\fii$, thus there exists $$\fk N\models T+\neg\fii$$ such that $\fk N\models(T+\fii)_{\aeba}$. The latter means that $T+\fii+\mathrm{Th}_{A\forall B\exists}(\fk N)$ is consistent, hence there exists $$\fk M\models T+\fii$$ such that $$\fk M\TO_{\aeba}\fk N,$$ by which I mean that $\fk M\models\psi\implies\fk N\models\psi$ for all $\psi\in\cL_{\aeba}$.

Using the Löwenheim–Skolem theorem and standard results on the existence of recursively saturated models, we may assume that $\fk M$ and $\fk N$ are countable, and the joint 4-sorted model $(\fk M,\fk N)$ is recursively saturated.

Let us fix enumerations $A(\fk M)=\{a_n:n\in\omega\}$ and $B(\fk N)=\{b_n:n\in\omega\}$. By induction on $n$, we will construct sequences $\{c_n:n\in\omega\}\subseteq A(\fk N)$ and $\{d_n:n\in\omega\}\subseteq B(\fk M)$ such that $$(\fk M,\{a_i:i<n\},\{d_i:i<n\})\TO_{\aeba}(\fk N,\{c_i:i<n\},\{b_i:i<n\})$$ for each $n$. (I will write $a_{<n}=\{a_i:i<n\}$ etc.) Once we carry this out, the assignments $a_n\mapsto c_n$ and $b_n\mapsto d_n$ will provide embeddings of $A(\fk M)$ in $A(\fk N)$ and $B(\fk N)$ in $B(\fk M)$ (respectively), witnessing that $\fii$ is not preserved under passing to $A$-super-$B$-substructures.

For $n=0$, we have nothing to do. Assume that the construction has been carried out up to $n$, and consider $a_n$. The set of formulas $$p(x)=\{\psi^{\fk M}(a_{<n},d_{<n},a_n)\to\psi^{\fk N}(c_{<n},b_{<n},x):\psi\in\cL_{\aeba}\}$$ is a recursive type of $(\fk M,\fk N)$: in particular, if $\psi_j$, $j<k$, are $\cL_{\aeba}$ formulas such that $\fk M\models\psi_j(a_{<n},d_{<n},a_n)$, then $$\fk M\models\exists x^A\,\bigwedge_{j<k}\psi_j(a_{<n},d_{<n},x^A),$$ hence $$\fk N\models\exists x^A\,\bigwedge_{j<k}\psi_j(c_{<n},b_{<n},x^A)$$ using $(\fk M,a_{<n},d_{<n})\TO_{\aeba}(\fk N,c_{<n},b_{<n})$, which shows that $p(x)$ is consistent. Thus, by recursive saturation, there exists $c_n\in A(\fk N)$ such that $(\fk M,a_{\le n},d_{<n})\TO_{\aeba}(\fk N,c_{\le n},b_{<n})$.

Dually, we can find a suitable $d_n\in B(\fk M)$ as a realization of the recursive type $$q(y)=\{\psi^{\fk M}(a_{\le n},d_{<n},y)\to\psi^{\fk N}(c_{\le n},b_{<n},b_n):\psi\in\cL_{\aeba}\}.$$ Again, to see that $q(y)$ is consistent, let $\psi_j$, $j<k$, be $\cL_{\aeba}$ formulas such that $\fk N\nvDash\psi_j(c_{\le n},b_{<n},b_n)$. Then $$\fk N\nvDash\forall y^B\,\bigvee_{j<k}\psi_j(c_{\le n},b_{<n},y^B),$$ thus using $(\fk M,a_{\le n},d_{<n})\TO_{\aeba}(\fk N,c_{\le n},b_{<n})$, we have $$\fk M\nvDash\forall y^B\,\bigvee_{j<k}\psi_j(a_{\le n},d_{<n},y^B).$$

Emil Jeřábek
  • 47.8k
  • 4
  • 151
  • 209