Consider theory T = Th(M, ~, =). Show that T has quantifier elimination

Question

Consider theory $\tau = Th(M,\sim, =)$, where $M$ is an infinite set, $=$ is the equality relation, and $\sim$ is an equivalence relation over $M$ with infinitely many equivalence classes (i.e. $\{\{n|m \sim n\}|m \in M\}$ is infinite) that are all infinite (i.e. $\{n|m\sim n\}$ is infinite for every $\{m \in M\}$) . Show that $\tau$ has quantifier elimination.

Any hint/help would be appreciated!!!

Update: I read this post here I Need Help Understanding Quantifier Elimination but I still don't have a clear idea on how to get a start on this problem.

Answer 1

Alternatively, you can just check it directly.

To prove quantifier elimination, it is enough to show that every formula of the form $\exists x \varphi(x,\bar y)$, where $\varphi$ is quantifier-free, is either equivalent to a quantifier-free formula with free variables $\bar y$ or it is simply always false or true.

Since $\exists$ distributes over disjunctions, it is enough to show this for the case when $\varphi$ is a conjunction of atomic formulas and their negations. It is easy see that you can also drop any atomic formulas in which $x$ is not actually used. In this case, this tells you that $\varphi$ is equivalent to a formula of the form $$ \left(\bigwedge_{i\in I_1} x=y_i\right)\land \left(\bigwedge_{i\in I_2} x\neq y_i\right) \land \left(\bigwedge_{i\in I_3} x\sim y_i\right)\land \left(\bigwedge_{i\in I_4} x\not\sim y_i\right). $$ Now:

1. If $I_1$ is nonempty and ${i_0}\in I_1$, then $\exists x \varphi(x,\bar y)$ is equivalent to $\varphi(y_{i_0},\bar y)$.
2. Otherwise, if $I_3$ is nonempty, then it is easy to check that $\exists x\varphi(x,\bar y)$ is equivalent to $\left(\bigwedge_{i_1,i_2\in I_3} y_{i_1}\sim y_{i_2}\right)\land \left(\bigwedge_{i_1\in I_3,i_2\in I_4} y_{i_1}\not\sim y_{i_2}\right)$.
3. If both $I_1$ and $I_3$ are empty, then $\exists x \varphi(x,\bar y)$ always holds.

Answer 2

All you need is the following very usefull criterion :

Criterion A $\mathcal{L}$-theory $T$ has quantifier elimination iff for every models $\mathcal{M}, \mathcal{N}$ of $T$ that share a common substructure $A$, we have that for every $\bar{a} \in A$ and every quantifier free $\mathcal{L}$-formula $\varphi(x, \bar{y})$, we have $$\mathcal{M} \models \exists x \varphi(x, \bar{a}) \Longrightarrow \mathcal{N} \models \exists x \varphi(x, \bar{a})$$

In your case, evrything is very nice :

• Any subset $A$ of a model of $\tau$ is a substructure.
• A quantifier free formula is a boolean combination of formulas of the form $x = y$ and $x \sim y$.

Hint

You can wlog assume that the formula $\varphi$ is of the form $$\bigwedge_{i < |\bar{y}|} \neg^{p_i} (x \sim y_{i}) \wedge \bigwedge_{i < |\bar{y}|} x \neq y_i$$ where $p_i \in \{0, 1\}$. If you can boil things down to that, you're almost done.