
Fol 13
Enderton 2.2.19
An $\displaystyle \exists_2$ formula is one of the form $\displaystyle \exists x_1 \cdots x_n \theta$, where $\displaystyle \theta$ is universal.
(a) Show that if an $\displaystyle \exists_2$ sentence in a language not containing function symbols (not even constant symbols) is true in $\displaystyle A$, then it is true in some finite substructure of $\displaystyle A$.
(b) Conclude that $\displaystyle \forall x \exists y Pxy$ is not logically equivalent to any $\displaystyle \exists_2$ sentence.
========================
(a) We have $\displaystyle \models_A \theta[s(x_1d_1)(x_2d_2)\ldots(x_nd_n)]$ for some $\displaystyle d_1, d_2, \ldots, d_n \in A$ by assumption. We have to show that there are some finite substructure $\displaystyle B$ of $\displaystyle A$ such that
$\displaystyle \models_B \theta[s(x_1d_1)(x_2d_2)\ldots(x_nd_n)] $ for the above $\displaystyle d_1, d_2, \ldots, d_n \in B$.
How do I proceed from here?
Thanks.

Re: Fol 13
How about taking a substructure B with $\displaystyle B=\{d_1,\dots,d_n\}$ and using problem 2.2.18 from your previous post? If the language had functional symbols, then the substructure generated by a finite number of elements may still have an infinite domain. E.g., the substructure of natural numbers with the successor function that contains 0 still has to contain all natural numbers.
For (b), consider again natural numbers where $\displaystyle Pxy$ is $\displaystyle x<y$.