Want to show Quantifier elimination and completeness of this set of axioms…

Let $\Sigma_\infty$ be a set of axioms in the language $\{\sim\}$ (where $\sim$ is a binary relation symbol) that states:

(i) $\sim$ is an equivalence relation;
(ii) every equivalence class is infinite;
(iii) there are infinitely many equivalence classes.

Show that $\Sigma_{\infty}$ admits QE and is complete. (It is given that it is also possible to use Vaught's test to prove completeness.)

I think I have shown that $\Sigma_\infty$ admits QE, but am not sure how to show completeness. There is a theorem, however, that states that if a set of sentences $\Sigma$ has a model and admits QE, and there exists an $L$-structure that can be embedded in every model of $\Sigma$, then $\Sigma$ is complete.

Thanks.

-
thanks for the edit martini. – Jmaff Dec 6 '12 at 21:41
The theory has no finite models and is countably categorical (there is only one model of cardinality $\omega$ up to isomorphism), so it has to be complete even ignoring quantifier elimination. – Carl Mummert Dec 7 '12 at 2:03
@CarlMummert I believe this is what he refers to as Vaught's test. A theory is complete if all models are infinite and the theory is categorical for some infinite cardinal bigger than the language. – Deven Ware Dec 7 '12 at 2:05

$\Sigma_{\infty}$ has a model is not too bad: Just take any quotient with infinitely many equivalence classes of infinite size, such as $\mathbb{R}/\mathbb{Q}$.

For the second part, notice that the $\mathcal{L}$-structure embedding into these models need not be a model of $\Sigma_{\infty}$! So you can just use a singleton $\{a\}$ with $a \sim a$ for your $\mathcal{L}$ structure!

-

According to the last sentence in your question, all you need is an $L$-structure that can be embedded into every model of $\Sigma_\infty$. In fact, $\Sigma_\infty$ has a "smallest" model, one that embeds into all other models of $\Sigma_\infty$. I think this should be enough of a hint to enable you to find the model in question --- just make it as small as the axioms of $\Sigma_\infty$ permit.

-
sounds good. Thanks – Jmaff Dec 7 '12 at 1:58

Your quantifier elimination procedure will transform any sentence in the language into an equivalent quantifier-free formula whose truth value can be calculated (as either true or false).

-