# Tag Info

## Hot answers tagged quantifier-elimination

Accepted

### Elimination of quantifiers for $\exists x\ x^2=y$

A quantifier-free assertion about $y$ in the language of $\{0,1,+,\cdot\}$ is a Boolean combination of polynomial equations in $y$ with natural number coefficients. Since every such equation has ...
• 44.6k

### Why is quantifier elimination desirable for a given theory?

You're quite right that we can "shoehorn in" quantifier elimination to any theory we want, by adding new predicates for all old formulas (this is called Morleyization if I recall correctly). So ...
• 251k

### How to show that $\mathbb{R}$ in the language of rings does not admit quantifier elimination?

Your idea of using a formula defining $\leq$ is a good one, but it will be easier to work with a similar formula that has only one free variable; I suggest $\exists x\,(x^2=y)$. I also think it's ...
• 73.3k
Accepted

### Quantifier elimination for $\mathbb Z$ as a group?

The complete theory of the structure $(\mathbb{Z}; 0,+,-,(n|)_{n\in \mathbb{Z}})$ , which is a definitional expansion of $(\mathbb{Z};+)$, has quantifier elimination. Of course, it already suffices to ...
• 80.1k
Accepted

### uniformity in quantifier elimination

No, it is not. Every completion of the empty theory in the empty language has quantifier elimination, but the empty theory itself doesn't. Why? Well, note that the only data missing from the empty ...
• 251k

### Counter-example of o-minimal structure but do not admit elimination of quantifiers

The classic example is $\mathbb{R}_{\text{exp}} = (\mathbb{R};<,+,-,\times,0,1,e^x)$. Wilkie showed that the complete theory of this structure is o-minimal and model complete, but does not admit ...
• 80.1k
Accepted

### How to show that $\mathbb{R}$ in the language of rings does not admit quantifier elimination?

I agree with Andreas Blass that the argument suggested in his answer is the most straightforward way to see that the theory of the real field does not have QE. But here's a way to see this using the ...
• 80.1k

### Quantifier elimination for $\mathbb Z$ as a group?

In his answer, Alex Kruckman points out the excellent reference: Eklof and Fischer, The elementary theory of abelian groups. Let me just spell out what can be gleaned from this. They recover Szmielew'...

### Can every theory $T$ be expanded to a theory with quantifier elimination in the same language?

Well, if $T$ is complete, then there's no nontrivial way to expand it, so any complete theory without quantifier elimination is a counterexample. Complete theories which have quantifier elimination ...
• 335k