1. ## Fol 12

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.

2. ## Re: Fol 12

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

Originally Posted by logics
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]$.
This makes sense.

Originally Posted by logics
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.
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 $\displaystyle \models_A \phi[s]$ is such a universal statement. By this I don't mean that $\displaystyle \phi$ is a string of characters that starts with $\displaystyle \forall$; rather, I mean that the whole claim $\displaystyle \models_A \phi[s]$, when you unfold some definitions, starts with the words "for all."