Sentencia de primer orden que implica a sólo una relación binaria simétrica con infinitos modelos de sólo

Question

Es conocido que existen sentencias de la lógica de primer orden, que sólo cuentan con modelos infinitos, incluso si nuestro lenguaje se compone sólo de una relación binaria $R$. Un ejemplo de tal sentencia es

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

Lo que me interesa es si todavía hay frases con sólo modelos infinitos cuando nos mandato que nuestra relación binaria ser simétrica?

La frase de la pregunta formalmente, considere la posibilidad de un primer orden lenguaje $\mathcal{L} = \{R^{2}\}$ (sin igualdad). Deje $\phi$ denotar la fórmula

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

Hay una frase $\psi$ $\mathcal{L}$ tal que $\phi \wedge \psi$ tiene una infinita modelo, pero no finito de modelos?

Answer 1

Definamos las fórmulas: $$\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$ ser la conjunción de las frases: #% $ $$\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)$% la #% $ claramente, $$\forall x\exists y(\alpha(x)\to\sigma(x,y))$ no tiene ningún modelo finito. Por otra parte, es un ejercicio sencillo para construir un modelo infinito de $\psi$

Answer 2

Para la formalización de Stephen A. Meigs sugerencia de definir:

$$\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}) \(\sigma (y_{1},y_{2}) \v \sigma (y_{2},y_{3}) \v \sigma (y_{1},y_{3}))) \\ \lambda(x) = \existe y(Rxy \wedge \forall z(Rxz \a \sigma(y,z))) $$

A continuación, vamos a $\psi$ ser la conjunción de:

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