= Solution
Take a countable <elementary substructure> $\mathcal B'$ of $\mathcal A'$ containing the named constant, using the <Downward Lowenheim-Skolem theorem>. Its reduct $\mathcal B$ has infinitely many singleton and doubleton classes. In particular it contains the partner of each of its non-singleton elements, and its interpretation of $P$ is exactly the singleton-class predicate.
Choose new distinct elements $u,v\notin B$. Define
$$
C=B\cup\{u\},\qquad D=B\cup\{u,v\}.
$$
In $\mathcal C$, make $u$ a new singleton class. In $\mathcal D$, make $\{u,v\}$ a new doubleton class; keep every old class of $\mathcal B$ unchanged. All three reducts are <first-order models> of the <complete theory>, and $\mathcal B\subseteq\mathcal C\subseteq\mathcal D$.
Expand $\mathcal C,\mathcal D$ by interpreting $P$ as singleton-class membership and retaining the original named constant from $B$. The resulting countable <first-order structures> $\mathcal C',\mathcal D'$ are each isomorphic to $\mathcal B'$: all have infinitely many classes of each size, and the bijections of classes can be chosen to preserve the constant and its class. Hence they are <first-order models> of $\operatorname{Th}(\mathcal A')$. Both inclusions $\mathcal B'\subseteq\mathcal C'$ and $\mathcal B'\subseteq\mathcal D'$ are genuine <structure embeddings>, since no class meeting $B$ was changed. The given <quantifier elimination>, together with the preceding implication to <first-order model> completeness, yields
$$
\mathcal B'\preceq\mathcal C',\qquad\mathcal B'\preceq\mathcal D'.
$$
Taking reducts gives $\boxed{\mathcal B\preceq\mathcal C,\quad\mathcal B\preceq\mathcal D}$. But
$$
\mathcal C\models\neg\exists y(E(u,y)\land y\ne u),\qquad\mathcal D\models\exists y(E(u,y)\land y\ne u),
$$
so $\boxed{\mathcal C\npreceq\mathcal D}$. There is no conflict with <quantifier elimination> in the expanded language: $P(u)$ changes truth value, so $\mathcal C'$ is not a substructure of $\mathcal D'$.
Back to article page
