I am working through some exercises from Marker's Model Theory in self-study and I am stuck at Exercise 3.4.1 as I do not know how to formally prove that a theory has quantifier elimination. I am aware of the definitions and possible checks but I cannot come up with a formal proof or an intuitive way to check if they do not have quantifier elimination.
Can someone help me by guiding me through the exercise? I would appreciate the effort as I am really trying to learn. Thank you very much.
Let $L = \{E\}$ where $E$ is a binary relation symbol. For each of the following theories either prove that they have quantifier elimination or give an example showing that they do not have quantifier elimination and a natural $L'\supset L$ in which they do have quantifier elimination.
a) E has infinitely many equivalence classes all of size $2$.
b) $E$ has infinitely many equivalence classes classes all of which are infinite.
c) $E$ has infinitely many equivalence classes of size $2$, infinitely many classes of size $3$, and every class has size $2$ or $3$.
d) $E$ has exactly one equivalence class of size $n$ for each $n < \omega$.
Hint: For the negative results, note that the set of elements whose classes have $n$ elements for a fixed finite $n$ is definable, but often not quantifier-free definable. On the other hand, after you make these sets quantifier-free definable, you can just prove q.e. directly, like in this example.