Infinite domains and nested quantification

Question

It is not difficult to exhibit a sentence $\phi$ with nested quantification such that $\phi$ is true only in infinite domains. Say, let $\phi$ be $\forall x \neg Rxx \wedge \forall x \exists y Rxy \wedge \forall x \forall y \forall z (Rxy \wedge Ryz \rightarrow Rxz)$. Note, however, that this sentence employs nested quantification in the second conjunct, specifically, a $\forall \exists$ alternation. Question: is there any sentence without nested quantification and without function symbols which is only true in infinite domains?

Answer 1

If you allow function symbols, then the answer is yes. Consider the language $\Sigma$ consisting of a binary function symbol $f$ and a binary relation symbol $R$, and let $\varphi$ be the $\Sigma$-sentence

$$\mbox{$R$ is a strict linear order and for all distinct $x$ and $y$, $f(x,y)$ is $R$-between $x$ and $y$.}$$

---

With only relation symbols, the answer is no: any subset of a $\Sigma$-structure $\mathcal{M}$ is also a substructure of $\mathcal{M}$ if $\Sigma$ is relational; this means that any satisfiable $\Sigma$-sentence of the form $\forall x_1,...,x_n\psi(x_1,...,x_n)$ with $\psi$ quantifier-free has a finite model (take any finite substructure of any model of $\psi$). Meanwhile it's not hard to show that any satisfiable $\Sigma$-sentence of the form $\exists x_1,...,x_n\psi(x_1,...,x_n)$ with $\psi$ quantifier-free has a finite model (pick an arbitrary model, and look at a finite substructure containing the witnesses to the sentence).

Note that the argument of the last sentence also shows that no sentence of the form $\exists y_1,..., y_m\forall x_1,...,x_n\psi(y_1,..., y_n, x_1,...,x_n)$ with $\psi$ quantifier-free. So "$\forall \exists$" is really where all the necessary complexity is, if we disallow function symbols.