(a) Let $\sigma=\exists x_{1}\ldots\exists x_{n}\forall y_{1}\ldots\forall y_{m}\theta$ where $\theta$ is quantifier-free. Then $\vDash_{\mathfrak{A}}\exists x_{1}\ldots\exists x_{n}\forall y_{1}\ldots\forall y_{m}\theta$ iff for every $s:V\rightarrow|\mathfrak{A}|$ , $\vDash_{\mathfrak{A}}\exists x_{1}\ldots\exists x_{n}\forall y_{1}\ldots\forall y_{m}\theta[s]$ iff for every $s:V\rightarrow|\mathfrak{A}|$ , there are $d_{1},\ldots,d_{n}\in|\mathfrak{A}|$ s.t. $\vDash_{\mathfrak{A}}\forall y_{1}\ldots\forall y_{m}\theta[s(x_{i}|d_{i})_{i=1}^{n}]$ . So, fix some $s$ and $D=\{d_{1},\ldots,d_{n}\}$ so that the latter expression holds ($D$ may have less than $n$ distinct elements), and let $s':V\rightarrow|\mathfrak{A}|$ be defined as $$s'(x_{k})=\begin{cases} d_{k} & k\in\overline{1,n}\\ d_{1} & \mbox{otherwise} \end{cases}.$$ Then, $\vDash_{\mathfrak{A}}\forall y_{1}\ldots\forall y_{m}\theta[s(x_{i}|d_{i})_{i=1}^{n}]$ implies $\vDash_{\mathfrak{A}}\forall y_{1}\ldots\forall y_{m}\theta[s']$ (the only variables that can be free in $\forall y_{1}\ldots\forall y_{m}\theta$ are $x_{1},\ldots,x_{n}$ , so the values at all other variables do not matter, Theorem 22A). Consider $\mathfrak{A}'$ being the restriction of $\mathfrak{A}$ to $D$ . Well, here is where we have to assume that not only $\theta$ is constant- and function-free, but so is $\mathfrak{A}$ (that is the language as well). Otherwise, there might be, for example, a function that would not have any closed restriction to any finite subset, that is there would not be any finite substructure of $\mathfrak{A}$ at all. Since there are no constant or function symbols in our language, $\mathfrak{A}'$ with all the predicates restricted to $D$ is a substructure of $\mathfrak{A}$ . Hence, according to Exercise 18(a), by noting that the way we constructed $s'$ its range is exactly $D$ , we have $\vDash_{\mathfrak{A}'}\forall y_{1}\ldots\forall y_{m}\theta[s']$ . Now note, that $s'=s'(x_{i}|d_{i})_{i=1}^{n}$ , hence, $\vDash_{\mathfrak{A}'}\forall y_{1}\ldots\forall y_{m}\theta[s'(x_{i}|d_{i})_{i=1}^{n}]$ , and $\vDash_{\mathfrak{A}'}\exists x_{1}\ldots\exists x_{n}\forall y_{1}\ldots\forall y_{m}\theta[s']$ , i.e. $\vDash_{\mathfrak{A}'}\sigma[s']$ . Since $\sigma$ is a sentence, as long as it is true in $\mathfrak{A}'$ with one assignment $s'$ , it is true in $\mathfrak{A}'$ with any $s$ , i.e. $\vDash_{\mathfrak{A}'}\sigma$ where $\mathfrak{A}'$ is a finite substructure of $\mathfrak{A}$ .

(b) Let $\sigma=\forall x\exists yPxy$ . Then, $\mathfrak{A}=(\mathbb{N};<)$ is a model of $\sigma$ . If $\sigma$ is logically equivalent to an $\exists_{2}$ sentence $\tau$ , then $\mathfrak{A}$ is a model of $\tau$ as well. Note, that $\mathfrak{A}$ does not have any constant or function symbols, so that there is a finite subset $A$ of $\mathbb{N}$ , s.t. $\mathfrak{A}$ restricted to $A$ is a model $\mathfrak{A}'$ of $\tau$ (according to (a)). However, there is no finite substructure of $\mathfrak{A}$ such that $\sigma$ is true in it, as for any finite domain there would be the maximum element $m$ such that $\forall y\neg m<y$ , or logically equivalently, $\neg\exists ym<y$ , implying $\neg\forall x\exists yx<y$ , i.e. $\neg\sigma$ . In particular, $\mathfrak{A}'$ is not a model of $\sigma$ , and $\sigma$ and $\tau$ are not logically equivalent.