(a) $\forall x\forall y(x<y\rightarrow\exists z(x<z\wedge z<y))$ , true in $(\mathbb{R};<)$ but not in $(\mathbb{N};<)$ .

(b) This exercise is similar to 19(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{R}}\exists x_{1}\ldots\exists x_{n}\forall y_{1}\ldots\forall y_{m}\theta$ iff for every $s:V\rightarrow|\mathfrak{R}|=\mathbb{R}$ , $\vDash_{\mathfrak{R}}\exists x_{1}\ldots\exists x_{n}\forall y_{1}\ldots\forall y_{m}\theta[s]$ iff for every $s:V\rightarrow|\mathfrak{R}|$ , there are $d_{1},\ldots,d_{n}\in|\mathfrak{A}|$ s.t. $\vDash_{\mathfrak{R}}\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}\}=\{r_{0},\ldots,r_{q-1}\}$ , $r_{j}<r_{k}$ iff $j<k$ , so that the latter expression holds ($D$ may have less than $n$ distinct elements, so we sort all distinct values and name them $r_{i}$ ), and let $s':V\rightarrow|\mathfrak{R}|$ be defined as $$s'(x_{k})=\begin{cases} d_{k} & k\in\overline{1,n}\\ d_{1} & \mbox{otherwise} \end{cases}.$$ Then, $\vDash_{\mathfrak{R}}\forall y_{1}\ldots\forall y_{m}\theta[s(x_{i}|d_{i})_{i=1}^{n}]$ implies $\vDash_{\mathfrak{R}}\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{N}'$ being the restriction of $\mathfrak{R}$ to $D'=\{r_{i}\}_{i=0}^{\infty}$ where $r_{q+k}=r_{q-1}+1+k$ . Since there are no constant or function symbols in our language, $\mathfrak{R}'$ with $<^{\mathfrak{R}'}$ being $<^{\mathfrak{R}}$ restricted to $D'$ is a substructure of $\mathfrak{R}$ . Hence, according to Exercise 18(a), by noting that the way we constructed $s'$ its range is exactly $D\subset D'$ , we have $\vDash_{\mathfrak{R}'}\forall y_{1}\ldots\forall y_{m}\theta[s']$ . Now note, that $s'=s'(x_{i}|d_{i})_{i=1}^{n}$ , hence, $\vDash_{\mathfrak{R}'}\forall y_{1}\ldots\forall y_{m}\theta[s'(x_{i}|d_{i})_{i=1}^{n}]$ , and $\vDash_{\mathfrak{R}'}\exists x_{1}\ldots\exists x_{n}\forall y_{1}\ldots\forall y_{m}\theta[s']$ , i.e. $\vDash_{\mathfrak{R}'}\sigma[s']$ . Since $\sigma$ is a sentence, as long as it is true in $\mathfrak{R}'$ with one assignment $s'$ , it is true in $\mathfrak{R}'$ with any $s$ , i.e. $\vDash_{\mathfrak{R}'}\sigma$ . It remains to notice that $h:D'\rightarrow\mathbb{N}$ defined by $h(r_{k})=k$ is an isomorphism of $\mathfrak{R}'$ onto $\mathfrak{N}=(\mathbb{N};<)$ , as $r_{j}<r_{k}$ iff $j<k$ . Hence, according to the Homomorphism Theorem, $\vDash_{\mathfrak{N}}\sigma$ .