5
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • $\begingroup$ Does first-order logic mean first-order logic with equality? We can use $=$ as well as $R?$ $\endgroup$ – bof Sep 27 '17 at 7:12
  • $\begingroup$ 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. $\endgroup$ – Carralpha Sep 27 '17 at 7:27
  • 2
    $\begingroup$ 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. $\endgroup$ – Carralpha Sep 27 '17 at 8:19
  • 2
    $\begingroup$ 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. $\endgroup$ – Stephen A. Meigs Sep 27 '17 at 14:05
3
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Providing an intuition behind the example would be also helpful $\endgroup$ – Fibo Kowalsky Mar 6 at 16:59
  • $\begingroup$ @FiboKowalsky I added an intuitive explanation to my example. $\endgroup$ – bof Mar 6 at 23:23
1
$\begingroup$

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) $$

|cite|improve this answer
$\endgroup$

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.