Show formula which does not have quantifier elimination in theory of infinite equivalence relations.

Question

Let $T^-$ be theory which fulfills following axioms:

(i) $\sim$ is an equivalence relation;
(ii) every equivalence class is infinite;

Find formula which is not $T^-$-equivalent to any formula without quantifiers.

I cannot work out such formula.

Answer 1

There is a feature of $T^-$ which is quite useful here: it is incomplete. In a complete theory, every sentence is either provable from the theory or disprovable from the theory, hence equivalent (over the theory) to either $\top$ or $\perp$. Because of this, if you want to show that a certain complete theory does not have quantifier elimination, you need to work with formulas with free variables - this amounts to analyzing the definable sets of an arbitrary model, and can often be quite complicated.

With an incomplete theory, however, we have a potentially simpler (at least, intuitively simpler) opportunity: we can look for a sentence which is not equivalent (over the theory) to any quantifier-free sentence. Specifically, we'll be done if we can do the following two things:

• Show that any two models of our theory have the same parameter-free quantifier-free theory.

• Show that there are two models of our theory which are not elementarily equivalent.

Analyzing the parameter-free quantifier-free sentences is generally much easier than looking at arbitrary formulas with free variables. In particular, it's often the case - as it is here - that the language of the theory we're studying simply doesn't allow for many quantifier-free sentences:

What are the quantifier-free sentences in the language of $T^-$? (There won't be very many, even if you allow "$\top$" and "$\perp$" as logical constants - which is a minor point of inconsistency between presentations of the subject.)

And the second bulletpoint is just the fact that our theory is incomplete, which in this case is easy:

Two countable models of $T^-$ are determined entirely by the number of equivalence classes; conversely, any number (from $1$ to $\omega$) of equivalence classes is allowed by $T^-$. So can you find a sentence which distinguishes (say) the two-class model from the one-class model?