Does the theory of equivalence relations have quantifier elimination?

888 Views Asked by At

I am aware that the theory of equivalence relations with infinitely many classes, all of which infinite, has quantifier elimination, as can be seen from the answer to this question. However, does the theory which consists only of the axioms stating that $E$ is reflexive, transitive, and symmetric, have quantifier elimination (in a first-order logic with equality)? I'm inclined to say no, but I don't really know how even to begin the proof either way. Any hint would be appreciated.

1

There are 1 best solutions below

6
On BEST ANSWER

Let $X = \{a,b,c\}$ and let $E$ be the equivalence relation on $X$ with classes $\{a\}$ and $\{b,c\}$. Then $a$ and $b$ satisfy the same quantifier-free formulas in one free variable (the induced substructures on $\{a\}$ and $\{b\}$ are isomorphic). But $b$ satisfies the formula $\exists x\, [xEy\wedge x\neq y]$, while $a$ does not. So this formula is not equivalent to any quantifier-free formula.