Quantifier elimination over rationals.

416 Views Asked by At

My question is concerned with a statement in Marker's Model Theory. The statement is that for formula $\phi(a,b,c)=\exists x(ax^2+bx+c=0)$, we cannot have a quantifier free formula $\phi'$ such that $\mathbb{Q} \models \phi \leftrightarrow \phi'$. I am not able to comprehend the validity of this statement since I can produce a formula $\phi'= (a\neq 0 \wedge b^2-4ac =0) \vee (a=0 \wedge b\neq 0)\vee(c=0)$ which is equivalent to $\phi$.

EDIT: I was wrong in saying the equivalence of two formulas holds. I would like to know whether one can show that there is no quantifier free formula equivalent to $\phi$ as above. Our language is that of a ring with 1 and theory is that of fields. We do not have the order relation.

3

There are 3 best solutions below

0
On BEST ANSWER

Thanks to such hypothetic formula $\phi'(a,b,c,\overline{d})$ where $\overline{d}$ is a tuple of rationnal numbers, you can define without quantifiers the fact that a rationnal number is a square:

$\mathbb{Q} \vDash \forall x(x$ is a square $\leftrightarrow \phi'(-1,0,x,\overline{d}))$. This is impossible:

$\phi'(-1,0,x,\overline{d})$ is a boolean combination of atomic $\left\langle +,-,.,0,1 \right\rangle$-formulas $\theta_i(x,\overline{d})$ of the form $\sum \limits_{k=0}^{n_i} q_{i,k}x^k = 0$ where $q_k$ are rationnal numbers.

All the sets $\{x \ | \ \mathbb{Q} \vDash \theta_i(x,\overline{d})\}$ are finite or cofinite depending on whether all $q_{i,k},0 \leq k \leq n_i$ are zero or not. Being finite or cofinite is preserved by boolean combination so $\{x \in \mathbb{Q} \ | \ \mathbb{Q} \vDash \phi'(-1,0,x,\overline{d})\} = \{x^2 \ | \ x \in \mathbb{Q}\}$ must be finite or cofinite, but it isn't.

You can adapt the end of the proof to show that $<$ and many other sets aren't quantifier-free definable in $(\mathbb{Q},+,-,.,0,1)$. I don't think there is a quantifier-free $\left\langle +,-,.,0,1,<\right\rangle$-formula equivalent to $\phi(a,b,c)$ in $\mathbb{Q}$ either, but it seems to be a much deeper result.

0
On

With $a=1,b=0,c= -1$, you have that $\phi'$ is false and $\phi$ is true, so $\phi'$ is not equivalent to $\phi$.

1
On

For the quadratic formula "argument" to make sense, you would need the first piece need to be $a \neq 0 \wedge b^2-4ac \text{ is the square of a rational number}$. I don't think the "perfect square" part can be made quantifier-free.