This is related to a previous question on first-order logic without equality. In that question, I asked what the axioms for equality relations are in first-order logic without equality, with a single binary relation $R$. They are the same as the axioms for equivalence relations. In this questions, I want to ask what the theory of diversity relations, that is, the complement of equality, is, in first-order logic without equality. I suspect that the axioms are the same as apartness relations:
- $\forall x \,\neg xRx$
- $\forall x \forall y (xRy \rightarrow yRx)$
- $\forall x \forall y \forall z(xRy \rightarrow xRz \lor yRz)$
Is this correct?
Yes, this is correct.
One way to see this is using the result you mention. Suppose $\varphi$ is any sentence in the language $\{R\}$ true in every structure in which $R$ is interpreted as $\not=$. Consider a new binary relation symbol $S$ and let $\psi$ be the sentence gotten from $\varphi$ by replacing each subformula of the form "$xRy$" in $\varphi$ with "$\neg xSy$." Then $\psi$ is true in every structure in which $S$ is interpreted as $=$, hence is a consequence of the axioms for equivalence relations. But then the original $\varphi$ is a consequence of the axioms for complements of equivalence relations, and it's easy to check that what you've written down is in fact an axiomatization of complements of equivalence relations.
And here's a self-contained argument (which also establishes the result about equality). In first-order logic without equality, any surjection $f:M\rightarrow N$ which preserves and reflects atomic formulas is in fact fully elementary; this is a straightforward proof by induction on formula complexity. Now just note that whenever $M$ is an $\{R\}$-structure in which $R$ is interpreted as the complement of an equivalence relation, modding out by the complement of $R$ gives such a map $M\rightarrow N$ with $R^N$ being $\not=$.