Enderton 2.2.18

A universal ($\displaystyle \forall_1$) formula is one of the form $\displaystyle \forall x_1 \cdots \forall x_n \theta$, where $\displaystyle \theta$ is a quantifier free. An existential ($\displaystyle \exists_1$) formula is of the dual form $\displaystyle \exists x_1 \cdots \exists x_n \theta$. Let $\displaystyle A$ be a substructure of $\displaystyle B$, and let $\displaystyle s:V \rightarrow |A|$.

(a) Show that if $\displaystyle \models_A \psi[s]$ and $\displaystyle \psi$ is existential, then $\displaystyle \models_B \psi[s]$. And if $\displaystyle \models_B \phi[s]$ and $\displaystyle \phi$ is universal, then $\displaystyle \models_A \phi[s]$.

(b) Conclude that the sentence $\displaystyle \exists Px$ is not logically equivalent to any universal sentence, nor $\displaystyle \forall x Px$ to any existential sentence.

=============================

(a) Since $\displaystyle A$ is a substructure of $\displaystyle B$, we have an identity map $\displaystyle i$ from $\displaystyle A$ into $\displaystyle B$.

Suppose $\displaystyle \models_A \exists x_1 \cdots \exists x_n \theta[s]$. Then, there are some $\displaystyle d_1, d_1, \ldots, d_n \in |A| $ such that $\displaystyle \models_A \theta[s(x_1|d_1)(x_2|d_2) \ldots (x_n |d_n)]$. By homomorphism theorem, we have $\displaystyle \models_A \theta[s]$ iff $\displaystyle \models_B\theta[i \circ s]$. Therefore, $\displaystyle \models_B \theta[s(x_1|d_1)(x_2|d_2) \ldots (x_n |d_n)]$ for $\displaystyle d_1, d_1, \ldots, d_n \in |B| $, i.e., $\displaystyle \models_B \exists x_1 \cdots \exists x_n \theta[s]$.

Now, to prove,

"If $\displaystyle \models_B \phi[s]$ and $\displaystyle \phi$ is universal, then $\displaystyle \models_A \phi[s]$".

For any $\displaystyle d_1, d_2, \ldots, d_n \in B$, we have

$\displaystyle \models_B \theta[s(x_1|d_1)(x_2|d_2) \ldots (x_n |d_n)]$ by assumption. If $\displaystyle d_1, d_2, \ldots, d_n$ in $\displaystyle |B|$ are also in $\displaystyle |A|$, then I may use the similar method to the above. But it does not look O.K to assume $\displaystyle d_1, d_2, \ldots, d_n \in |A|$ as well.

Any help will be appreciated.