Timeline for Does model-complete in a language with a constant symbol imply EQ?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 1, 2012 at 15:02 | comment | added | Emil Jeřábek | A belated comment: as for simpler but still interesting theories that are model-complete but do not admit quantifier elimination, one can take the real field itself (in the language of rings, i.e., without an ordering symbol), or Presburger’s arithmetic (in various variants: the theory of $(\mathbb N,+)$, or $(\mathbb N,+,\le)$, or $(\mathbb Z,+,\le)$, with or without constants $0,1$ or subtraction). | |
| Dec 30, 2011 at 18:42 | vote | accept | atonaltensor | ||
| Dec 29, 2011 at 20:31 | comment | added | Dave Marker | A couple of comments: In 3.1.4 the constant is needed if we want our new formula to have the same free variables as the old formula. This is only an issue if the original formula is a sentence and there are no quantifier free sentences in the language. One consequence of model completeness is that the theory has a $\forall\exists$ axiomatization. For the reals with exponentiation it is wide open (even assuming Schanuel's Conjecture) what this axiomatization is. | |
| Dec 29, 2011 at 12:22 | comment | added | Emil Jeřábek | A corollary of the two characterizations is that a universal theory is model-complete iff it has elimination of quantifiers. | |
| Dec 29, 2011 at 10:46 | comment | added | Goldstern |
A simpler (and less interesting) theory which is model complete yet does not admit elimination of quantifiers is the theory of this model $N$ with universe $\mathbb N$: The constant 0 is interpreted as 0, and the relation $R(x,y)$ holds iff $x=1$ and $y>1$. Then the property $x=1$ can be expressed as $\exists y (R(x,y))$, or $x\not=0 \wedge \forall z(\lnot R(z,x))$, but not without quantifiers. With $A=\{0,5\}$, you could imagine a model $M$ containing $A$, where $5$ plays the role of $1$ (i.e., satisfies the formula "$x=1$" given above).
|
|
| Dec 29, 2011 at 3:45 | history | edited | Ed Dean | CC BY-SA 3.0 |
added 428 characters in body
|
| Dec 29, 2011 at 3:00 | history | answered | Ed Dean | CC BY-SA 3.0 |