# Infinite domains and nested quantification

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?

• Any sentence of the form $\forall x_1\ldots\forall x_n\Phi(x_1,\ldots, x_n)$ (where $\Phi$ contains no quantor) that is true in some domain is also true in every subdomain. Jul 9 '18 at 21:51
• @HagenvonEitzen - Perhaps I'm too dense (or perhaps my question is unclear), but I don't see the relevance of your comment. Can you expand? Jul 9 '18 at 21:52
• That implies that without $\exists$ you cannot enforce infinite domain. And even if there are some $\exists$, but all are outmost (i.e., there is no $\forall \exists$, only $\exists\ldots \exists \forall\ldots \forall$), then the we can get rid of these and add finitely many constants - and still cannot enforce infinite domain. Jul 9 '18 at 21:57

## 1 Answer

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.

• Thanks, this is exactly what I was looking for. Jul 9 '18 at 21:58