1
$\begingroup$

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.

$\endgroup$
0

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I was wondering the same thing. Can one show this. $\endgroup$ Jul 13, 2015 at 10:06
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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