Consider theory T = Th(M, ~, =). Show that T has quantifier elimination 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. 
 A: 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:


*

*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)$.

*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)$.

*If both $I_1$ and $I_3$ are empty, then $\exists x \varphi(x,\bar y)$ always holds.

A: 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.
