Can equivalence relations be axiomatized using just one elementary sentence?

Question

Equivalence relations are traditionally axiomatized by the Reflexivity, Symmetry, and Transitivity axioms. However, they can also be axiomatized by Reflexivity and Circularity. (Circularity is this axiom: $(xRy \land yRz) \rightarrow zRx$). I am wondering if we can make do with just one elementary sentence. By elementary sentence, I mean either an atomic formula, or a negated atomic formula, or finite disjunctions of the previous two. For example, Circularity can be rewritten as $(\neg xRy \vee \neg yRz \vee zRx)$, which is an elementary sentence by my definition. If it can't be axiomatized by just one elementary sentence, I want to see a proof that it can't be so axiomatized.

Answer 1

The answer to your question is: this is not possible.

I'll assume that our non-logical vocabulary is exactly $\{R\}$.

Let $F$ denote the always-false binary relation and $T$ denote the always true binary relation.

Lemma 101: If $\varphi$ is negation-free, then $\varphi$ cannot require $R$ to be transitive without requiring it to be $T$.

Suppose $\varphi$ is negation-free.

If $\varphi$ is of the form $xRx$, then $R$ must be a superset of the identity relation. This does not require $R$ to be transitive.

If $\varphi$ is of the form $xRy$, then $R$ must be $T$. This requires $R$ to be transitive, but misses out on the identity relation, which is a potential equivalence relation that we need to allow.

For the general case, if $\varphi$ is negation-free, then, for any $S$ satisyfing $\varphi$ any superset $S' \supset S$ will also satisfy $\varphi$. Therefore, all the relations satisyfing $\varphi$ are transitive if any only if the only relation satisyfing $\varphi$ is $T$.

End of Lemma 101.

Lemma 102: If $\varphi$ contains negation, then it allows $F$

Suppose $\varphi$ contains at least one negated clause $\lnot xRy$ where $x$ and $y$ are not necessarily distinct.

If $R$ is $F$, then $xRy$ will always be false and hence $\varphi$ will vacuously be true.

End of Lemma 102.

Theorem: Equivalence Relations cannot be axiomatized using an elementary sentence.

No elementary sentence can be both negation-free and contain a negation, however, by Lemmas 101 and 102, we need both kinds of sentences in order to insist on transitivity without insisting that we have $T$ and to rule out $F$.

---

EDIT 2023-04-09: Correcting the addendum.

The sentence $\forall x \forall y \; (f(x) = f(y) \to xRy)$ does NOT axiomatize an equivlance relation.

For example, consider:

• $f = \{(0, 0), (1, 1)\}$ i.e. $f$ is like the identity function
• $R = \{(0, 0), (0, 1), (1, 1)\}$ i.e. $R$ is like material implication.

I meant to say $\forall x \forall y \; (f(x) = f(y) \leftrightarrow xRy)$ with a biconditional, but expressing this requires two elementary sentences not one.

I don't know whether a single elementary sentence in the language with signature $(R, f)$ can axiomatize equivalence relations or not.