Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


share|cite|improve this question
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
up vote 1 down vote accepted

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

share|cite|improve this answer

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.

share|cite|improve this answer
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).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.