A proper pseudo-elementary class whose complement is an elementary class

Solution 1:

No. Even stronger: If a class $K$ of $L$-structures and its complement $K'$ are both pseudo-elementary, then both $K$ and $K'$ are elementary, and in fact finitely axiomatizable.

This statement puts together two classical facts:

1. Every pseudo-elementary class is closed under ultraproducts and isomorphisms, and
2. A class $K$ of $L$-structures is a finitely axiomatizable elementary class if and only if both $K$ and it's complement are closed under ultraproducts and isomorphisms.

I've given proofs of these statements below. Note that the proof of 2 relies on the Keisler-Shelah theorem. It's possible that in the special case of pseudo-elementary classes, there's another proof that avoids Keisler-Shelah, but it's not obvious to me at the moment.

Proof of 1: Let $K$ be a pseudo-elementary class of $L$-structures. Then there is a language $L^*\supseteq L$ and an elementary class $K^*$ of $L^*$-structures such that $K = K^*|_L$ (here $|_L$ denotes the reduct to $L$).

For closure under ultraproducts, let $(M_i)_{i\in I}$ be a family of structures in $K$, and let $U$ be an ultrafilter on $I$. For each $i\in I$, we can pick a structure $M_i^*$ in $K^*$ such that $M_i^*|_L = M_i$. Since $K^*$ is an elementary class, $\prod_{i\in I}M_i^*/U\in K^*$. So $\prod_{i\in I}M_i/U = \left(\prod_{i\in I}M_i^*/U\right)|_L\in K$.

For closure under isomorphisms, let $M\in K$, and let $f\colon M\to N$ be an isomorphism. Pick a structure $M^*\in K^*$ such that $M^*|_L = M$. Then we can use $f$ to transport the interpretations of the symbols in $L^*\setminus L$ to $N$, obtaining a structure $N^*$ such that $f\colon M^*\to N^*$ is an isomorphism. Since $K^*$ is an elementary class, $N^*\in K^*$. So $N = N^*|_L\in K$.

Proof of 2: For the easy direction, if $K$ is a finitely axiomatizable elementary class, say $K$ is axiomatized by $\{\varphi_1,\dots,\varphi_n\}$, then the complement of $K$ is axiomatized by $\lnot \bigwedge_{i=1}^n \varphi_i$. So $K$ and its complement are both elementary classes, and hence both closed under ultraproducts and isomorphisms.

For the other direction, assume $K$ and its complement are closed under ultraproducts and isomorphisms. First we show that $K$ is an elementary class. Define $$T = \text{Th}(K) = \{\varphi\mid M\models \varphi\text{ for all }M\in K\}.$$ We'd like to show that any model of $T$ is in $K$. So suppose for contradiction that $N\models T$ but $N\notin K$. I want to begin by constructing an ultraproduct of structures in $K$ which is elementarily equivalent to $N$.

The idea of the construction is the same as the ultraproduct proof of the compactness theorem. Let $T' = \text{Th}(N)$, and note that $T\subseteq T'$. Let $I = \mathcal{P}_{\text{fin}}(T')$, the set of finite subsets of $T'$. For any $\Phi\in I$, let $X_{\Phi} = \{\Psi\in I\mid \Phi\subseteq \Psi\}\subseteq I.$ Now the family of sets $F = \{X_\Phi\mid \Phi\in I\}$ has the finite intersection property, since $\bigcup_{i=1}^n \Phi_i \in \bigcap_{i=1}^n X_{\Phi_i}$. So $F$ extends to an ultrafilter $U$ on $I$.

For any $\Phi\in I$, we can write $\Phi = \{\varphi_1,\dots,\varphi_n\}\subseteq T'$. Let $\theta = \bigwedge_{i=1}^n \varphi_i$, and note that $N\models \theta$. Thus $\lnot\theta\notin T$, so there is some $M_\Phi\in K$ such that $M_\Phi\models \theta$. Consider the ultraproduct $$M = \prod_{\Phi\in I} M_\Phi/U.$$ Since $K$ is closed under ultraproducts, $M\in K$. And for any sentence $\psi\in T'$, by construction $X_{\{\psi\}}\in U$, and for all $M_\Phi\in X_{\{\psi\}}$, $\psi\in \Phi$, so $M_\Phi\models \psi$. By Łoś's Theorem, $M\models T'$.

Great, now we have $M\in K$ with $M\equiv N$. By the Keisler-Shelah theorem, there is an ultrapower $M^*$ of $M$ and an ultrapower $N^*$ of $N$ such that $M\cong N$. Since $K$ is closed under ultraproducts, $M^*\in K$, and since $K$ is closed under isomorphisms, $N^*\in K$. But $N\notin K$, so this contradicts the hypothesis that the complement of $K$ is closed under ultraproducts.

Having shown that $K$ is an elementary class, we observe that the same argument shows that the complement of $K$ is an elementary class (since our assumptions on $K$ and its complement are symmetrical). It remains to show that both are finitely axiomatizable.

Let $T_{K}$ axiomatize $K$, and let $T'_{K}$ axiomatize the complement of $K$. Then $T_K\cup T'_K$ is inconsistent. By compactness, there is a finite set $\{\varphi_1,\dots,\varphi_n\}\subseteq T_K$ and a finite set $\{\psi_1,\dots,\psi_m\}\subseteq T_K'$ such that $\{\varphi_1,\dots,\varphi_n\}\cup \{\psi_1,\dots,\psi_m\}$ is inconsistent. But then $\{\varphi_1,\dots,\varphi_n\}$ axiomatizes $K$ and $\{\psi_1,\dots,\psi_m\}$ axiomatizes the complement of $K$.