A proper pseudo-elementary class whose complement is an elementary class Fix a first-order signature $L$. Is there a class of $L$-structures $K$ which is a pseudo-elementary class but not an elementary class, whose complement $K'$ is an elementary class?
 A: 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:

*

*Every pseudo-elementary class is closed under ultraproducts and isomorphisms, and

*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.
Edit: Here's a more direct proof of the claim for pseudo-elementary classes, using the Craig Interpolation Theorem.
Assume for contradiction that $K$ and its complement $K'$ are both pseudo-elementary. Let $L_1$ and $L_2$ be languages extending $L$, let $T_1$ be an $L_1$ theory such that $K$ is the class of $L$-reducts of models of $T_1$, and let $T_2$ be an $L_2$ theory such that $K'$ is the class of $L$-reducts of models of $T_2$. Note that we can assume without loss of generality that $L_1\cap L_2 = L$.
Then $T_1\cup T_2$ is inconsistent, since if $M\models T_1\cup T_2$, we have $M|_L \in K$ and $M|_L \in K'$. By compactness, there is an $L_1$-sentence $\varphi_1$, which is a finite conjunction of sentences in $T_1$, and an $L_2$-sentence $\varphi_2$, which is a finite conjunction of sentences in $T_2$, such that $\varphi_1\models \lnot \varphi_2$. By Craig Interpolation, there is an $L$-sentence $\theta$ such that $\varphi_1\models \theta$ and $\theta\models \lnot\varphi_2$.
I claim that $\theta$ axiomatizes $K$, and hence $\lnot \theta$ axiomatizes $K'$. If $M\in K$, then $M$ has an expansion to a model $M_1$ of $T_1$. Then $M_1\models \varphi_1$, and hence $M \models \theta$. If $M\notin K$, then $M\in K'$, so $M$ has an expansion to a model of $M_2$ of $T_2$. Then $M_2\models \varphi_2$, and hence $M\models \lnot \theta$.

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$.
