1. ## Fol 12

Enderton 2.2.18

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

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

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

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

(a) Since $A$ is a substructure of $B$, we have an identity map $i$ from $A$ into $B$.
Suppose $\models_A \exists x_1 \cdots \exists x_n \theta[s]$. Then, there are some $d_1, d_1, \ldots, d_n \in |A|$ such that $\models_A \theta[s(x_1|d_1)(x_2|d_2) \ldots (x_n |d_n)]$. By homomorphism theorem, we have $\models_A \theta[s]$ iff $\models_B\theta[i \circ s]$. Therefore, $\models_B \theta[s(x_1|d_1)(x_2|d_2) \ldots (x_n |d_n)]$ for $d_1, d_1, \ldots, d_n \in |B|$, i.e., $\models_B \exists x_1 \cdots \exists x_n \theta[s]$.

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

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

Any help will be appreciated.

2. ## Re: Fol 12

Originally Posted by logics
(a) Since $A$ is a substructure of $B$, we have an identity map $i$ from $A$ into $B$.
Rather, the identity map is a homomorphism.

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

Originally Posted by logics
Now, to prove,
"If $\models_B \phi[s]$ and $\phi$ is universal, then $\models_A \phi[s]$".

For any $d_1, d_2, \ldots, d_n \in B$, we have
$\models_B \theta[s(x_1|d_1)(x_2|d_2) \ldots (x_n |d_n)]$ by assumption. If $d_1, d_2, \ldots, d_n$ in $|B|$ are also in $|A|$, then I may use the similar method to the above. But it does not look O.K to assume $d_1, d_2, \ldots, d_n \in |A|$ as well.
You should start proving this statement as you would any other universal statement. Namely, one proves "for all x, P(x)" by fixing an arbitrary x and showing P(x). Here $\models_A \phi[s]$ is such a universal statement. By this I don't mean that $\phi$ is a string of characters that starts with $\forall$; rather, I mean that the whole claim $\models_A \phi[s]$, when you unfold some definitions, starts with the words "for all."