# First-order sentence involving only a symmetric binary relation with only infinite models

It's known that there are sentences of first-order logic which only have infinite models, even if our language consists only of a binary relation $R$. An example of such a sentence is

$$\forall x \exists y Rxy \wedge \forall x \forall y \forall z ((Rxy \wedge Ryz ) \to Rxz) \wedge \neg \exists x Rxx$$

What I'm curious about is whether there are still sentences with only infinite models when we mandate that our binary relation be symmetric?

To phrase the question formally, consider a first-order language $\mathcal{L} = \{R^{2}\}$ (without equality). Let $\phi$ denote the formula

$$\forall x \forall y (Rxy \to Ryx)$$

Is there a sentence $\psi$ of $\mathcal{L}$ such that $\phi \wedge \psi$ has an infinite model, but no finite models?

• Does first-order logic mean first-order logic with equality? We can use $=$ as well as $R?$ – bof Sep 27 '17 at 7:12
• The way I imagined the question, we can't use equality. However, if $\psi$ does exist when $\mathcal{L}$ includes equality but doesn't exist when $\mathcal{L}$ doesn't include equality, that would be interesting. – Carralpha Sep 27 '17 at 7:27
• With equality, is it correct that a sentence like "exactly one object has only one object it relates to; everything else relates to exactly two different objects; nothing relates to itself" works? It is satisfied by $\mathbb{N}$ with $Rxy$ interpreted as $| x - y | = 1$, but I believe by no finite models; you might have something simpler in mind. – Carralpha Sep 27 '17 at 8:19
• Seems maybe like Catalpha's elegant solution works even without equality if you allow $\forall{z} (xRz \leftrightarrow yRz)$ to take the place of $x = y$ when counting how many objects are related to x. – Stephen A. Meigs Sep 27 '17 at 14:05

Let us define the formulas: $$\kappa_3(x)=\exists u\exists v(Rxu\land Rxv\land Ruv)$$ $$\kappa_4(x)=\exists u\exists v\exists w(Rxu\land Rxv\land Rxw\land Ruv\land Ruw\land Rvw)$$ $$\alpha(x)=\neg\kappa_3(x)$$ $$\beta(x)=\kappa_3(x)\land\neg\kappa_4(x)$$ $$\gamma(x)=\kappa_4(x)$$ $$\sigma(x,y)=\alpha(x)\land\alpha(y)\land\exists u\exists v(Rxu\land Ruv\land Rvy\land\beta(u)\land\gamma(v))$$ Let $$\psi$$ be the conjunction of the sentences: $$\forall x\forall y\forall z(\sigma(x,y)\land\sigma(y,z)\to\sigma(x,z))$$ $$\forall x\neg\sigma(x,x)$$ $$\exists x\alpha(x)$$ $$\forall x\exists y(\alpha(x)\to\sigma(x,y))$$ Plainly, $$\psi$$ has no finite model. On the other hand, it is a straightforward exercise to construct an infinite model of $$\phi\land\psi.$$

Intuition behind this example. The (irreflexive) models of $$\phi$$ are just (undirected) graphs. The problem is to construct an asymmetric relation on an undirected graph. Given a vertex $$x$$ let $$f(x)$$ denote the maximum number of vertices in a clique containing $$x$$. For vertices $$x$$ and $$y$$, define $$x\lt y$$ to mean that $$f(x),f(y)\le2$$ and there is a path $$x,u,v,y$$ with $$f(u)=3$$ and $$f(v)\ge4$$. Then we can write a first order sentence in the language of graph theory which says that the relation $$\lt$$ restricted to the set $$\{x:f(x)\le2\}$$ is an irreflexive transitive relation with no greatest element.

• Providing an intuition behind the example would be also helpful – Fibo Kowalsky Mar 6 '19 at 16:59
• @FiboKowalsky I added an intuitive explanation to my example. – bof Mar 6 '19 at 23:23

To formalise Stephen A. Meigs's suggestion, define:

$$\sigma (x,y) = \forall z (Rxz \leftrightarrow Ryz) \\ \kappa (x) = \forall y_{1} \forall y_{2} \forall y_{3} ((Rxy_{1} \wedge Rxy_{2} \wedge Rxy_{3}) \to (\sigma (y_{1},y_{2}) \vee \sigma (y_{2},y_{3}) \vee \sigma (y_{1},y_{3}))) \\ \lambda(x) = \exists y(Rxy \wedge \forall z(Rxz \to \sigma(y,z)))$$

Then let $\psi$ be the conjunction of:

$$\forall x \kappa (x) \\ \exists x (\lambda (x) \wedge \forall y (\lambda (y) \to \sigma(y,x))) \\ \forall x \forall y \neg (\sigma(x,y) \wedge Rxy)$$