1
$\begingroup$

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?

$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$ Jul 9 '18 at 21:51
  • $\begingroup$ @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? $\endgroup$
    – Nagase
    Jul 9 '18 at 21:52
  • 2
    $\begingroup$ 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. $\endgroup$ Jul 9 '18 at 21:57
1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks, this is exactly what I was looking for. $\endgroup$
    – Nagase
    Jul 9 '18 at 21:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.