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

Question

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.

Answer 1

$\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!

Answer 2

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.

Answer 3

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