8
$\begingroup$

Let $\mathbb F$ be a field and let $a, b, c, d$ be fixed elements in the field $\mathbb F$. Consider the formulas

1) $\exists\;x\;\;:\;\;x^2=-1.$

2) $\exists\;x\;\;:\;\;(xa=c\land xb=d).$

Formula $(1)$ can be false in $\mathbb F$ but true in a field extension of $\mathbb F$. For exemple, formula $(1)$ is false in the reals $\mathbb R$ but true in the complex numbers $\mathbb C$.

The same does not happen with the formula $(2)$ since formula $(2)$ is true if and only if the matrix $$\left(\begin{array}{cc}a&b\\c&d\end{array}\right),$$ is singular, and it is well known that the singularity of a matrix is not changed by an extension of the field that contains the elements of the matrix.

My question is:

Is there any characterization of the formulas, in a field, whose validity does not change by an extension of the field?

Remark: I put this question yesterday in https://math.stackexchange.com/questions/561178/formulas-in-a-field-and-in-a-field-extension. But was not answered.

$\endgroup$
3
  • 1
    $\begingroup$ Waiting just one day between posting a question on the two sites is usually not a long enough waiting period. If you want you can instead have the moderators migrate the question from MSE to MO (in which case it may be closed and sent back to MSE). But cross-posting after just one day is unacceptable in most cases. $\endgroup$
    – Asaf Karagila
    Nov 11, 2013 at 8:37
  • 2
    $\begingroup$ A simpler explanation for why (2) is preserved under field extensions is that it is equivalent to $c\cdot a^{-1} = d \cdot b^{-1}$. $\endgroup$ Nov 11, 2013 at 9:50
  • $\begingroup$ Consider the formula (3) $\exists x, x^3+ax^2+bx+c == 0$ and $3x^2+2ax+b=0$. In other words, (3) says that $x^3+ax^2+bx+c$ has a double root. Then even if (3) looks like (1) at first glance, it behaves like (2): it is true in a field if and only if it is true in some extension, for its equivalent to the discriminant of the polynomial being 0. This formula, like (2), is equivalent to a formula without quantifier. Very naive question: is it possible to find a formula of the type of (2) (that is, whose truth is invariant by extension) which is not equivalent to a formula without quantifiers? $\endgroup$
    – Joël
    Nov 11, 2013 at 21:58

3 Answers 3

5
$\begingroup$

This is a major clean-up of my previous argument, thanks to the very helpful comments of Emil Jerabek.

I interpret the question as follows: Characterize all sentences in the language of fields that are preserved under field extensions.

Claim: A formula $\phi$ is preserved under field extensions if and only if the field axioms prove that $\phi$ is equivalent to an existential formula.

For definiteness, we take the language of fields to have operations for addition and multiplication, and distinguished elements for 0 and 1.

The main tool to establish the claim is the following

Lemma: Suppose $M$ is a structure in any old language, and $T$ is a theory in that language. Let $\forall(T)$ denote the set of universal consequences of $T$. If $M\models\forall(T)$ then $M$ extends to a model of $T$.

Proof-sketch: The diagram of $M$ cannot be inconsistent with $T$, because otherwise $T$ would imply the negation of some formula in the diagram of $M$, and therefore would imply the universal closure of the negation of that formula, contrary to the assumption $M\models\forall(T)$. But then any model of the diagram of $M$ plus $T$ will do the job we require.

Now we prove the Claim. The non-trivial part is to show that if the theory of fields (which we will henceforth call $T$) cannot prove the equivalence between $\phi$ and any existential sentence, then $\phi$ is not preserved under extensions.

But our premiss is equivalent to the statement that $T$ cannot prove the equivalence between $\neg\phi$ and any universal sentence. Let $S$ be the set of universal consequences of $T+\neg\phi$. Then $S+T\nvdash\neg\phi$. For otherwise, using the fact that $S$ is closed under conjunction (at least up to logical equivalence) we could argue that $\sigma+T\vdash\neg\phi$, for some sentence $\sigma\in S$. But this, together with $T+\neg\phi\vdash\sigma$ would imply that $T\vdash\sigma\longleftrightarrow \neg\phi$, contrary to the premiss of our argument.

We have shown that $S+T\nvdash\neg\phi$. Therefore there is a structure $k$ satisfying $S+T+\phi$. Evidently $k$ is a field. Recalling that $S$ is the set of universal consequences of $T+\neg\phi$, we can now use the Lemma to conclude that $k$ extends to a field $K$ satisfying $\neg\phi$. This proves that $\phi$ is not preserved under extensions.

I'd love some feedback on this!

$\endgroup$
10
  • $\begingroup$ But isn´t 1) in the OP an existential formula? I think you have a different notion of "preserved under field extensions" than the OP. $\endgroup$ Nov 12, 2013 at 11:20
  • $\begingroup$ You don’t need the extra operations, as (1) they are existentially definable in the language with $+$ and $\cdot$ only anyway, and (2) the criterion holds over an arbitrary first-order theory, it does not have to be universal. @Ramiro: Preserved under extensions here means that whenever $\phi$ holds in a field, it also holds in every its extension field. $\endgroup$ Nov 12, 2013 at 12:17
  • $\begingroup$ @Emil: If you look at the proof I supplied (after you wrote your comment) you will see that it makes essential use of the fact the theory of fields is universal. Do you know a way to prove the criterion without this assumption? $\endgroup$ Nov 12, 2013 at 12:46
  • 1
    $\begingroup$ @Emil: I supposed so. But I thought the OP wanted both uppward and downward preservation, as reflected by his sentence "whose validity does not change by an extension" and his example 1). $\endgroup$ Nov 12, 2013 at 16:14
  • 1
    $\begingroup$ @Ramiro: It's easy to deduce from my proof that downwards preserved formulas are precisely the universal ones. So upward and downward means simultaneously universal and existential $\endgroup$ Nov 12, 2013 at 18:56
7
$\begingroup$

These are exactly the formulas that are provably (in the theory of fields) equivalent to a formula without quantifiers.

The proof is that, in the theory of algebraically closed fields, they must be equivalent to a formula without quantifiers, because quantifier elimination holds in the theory of algebraically closed fields.

I claim the two formulas are also equivalent in the theory of fields. If not, there must be some field where one is true and the other is false, by Godel's completeness theorem. But if we pass to the algebraic closure of that field, each formula retains its truth value, which contradicts the fact that the two formulas are equivalent for algebraically closed fields.

$\endgroup$
5
  • 1
    $\begingroup$ What about the formula $\phi(y):\exists x\,\,y=x^2$. This is preserved under extensions, but what is the quantifier-free equivalent of $\phi(y)$ in the language of fields? $\endgroup$ Nov 12, 2013 at 4:38
  • 2
    $\begingroup$ @SJR: true in all fields, so provably equivalent to e.g. $1 = 1$, right? $\endgroup$ Nov 12, 2013 at 4:41
  • $\begingroup$ @QiaochuYuan, No. Quantifier elimination is about formulas with free variables, and whether they are all equivalent to a quantifier-free assertion about those variables. SJR is speaking of the formula $\phi(y)$, which has the free variable $y$. Certainly $\phi(y)$ is not true of every $y$ in every field, since for example it fails famously of $2$ in the rational field. $\endgroup$ Nov 12, 2013 at 15:17
  • 1
    $\begingroup$ This formula's validity changes in a field extension and is exactly what zacarias was trying to avoid - e.g. see the special case of it that is example 1). $\endgroup$
    – Will Sawin
    Nov 12, 2013 at 16:14
  • $\begingroup$ Will, I agree with you, and I like your argument. The OP is concerned with formulas $\phi$ for which both $\phi$ and $\neg\phi$ are preserved to field extensions. SJR's argument is about upward preservation only. Preservation of $\neg\phi$ upward amounts to downward preservation of $\phi$, so his argument (as he says) shows that the formulas preserved in both directions have both existential and universal equivalent forms. $\endgroup$ Nov 12, 2013 at 22:15
4
$\begingroup$

This was intended to be a comment to SJR's post, but was too long. Here is a proof that any formula that is preserved downwards in models of $T$ is equivalent in $T$ to a universal formula, from which we deduce that formulas preserved upwards are equivalent to existential formulas.

Let $T$ be an $\cal L$-theory. Suppose $\phi(\bar v)$ is preserved downwards in models of $T$. Let $\Gamma(\bar v)=\{\psi(\bar v): \psi$ is universal and $T\models \phi(\bar v)\rightarrow \psi(\bar v)\}$. We claim that $T+\Gamma(\bar v)\models \psi(\bar v)$. If that happens then there are $\psi_1,\dots,\psi_n\in\Gamma(\bar v)$ such that $T\models \phi(\bar v)\leftrightarrow (\psi_1(\bar v)\land\dots\land\psi_n(\bar v)$.

Suppose not. Then there is ${\cal M}\models T$ and $\bar a\in \cal M$ such that ${\cal M}\models \psi(\bar a)$ for $\psi\in\Gamma$ and ${\cal M}\models \neg\phi(\bar a)$.

Let $T_1= T+ \phi(\bar a) + $ atomic diagram of $\cal M$. If $T_1$ is satisfiable there is ${\cal N}\models T$ with ${\cal M}\subset {\cal N}$ and ${\cal N}\models \phi(\bar a)$, contradicting the fact that $\phi$ is preserved downward. Thus $T_1$ must be unsatisfiable. Thus there is a quantifier free formula $\theta(\bar v,\bar w)$ and $\bar b\in \cal M$ such that $$T\models \theta(\bar a,\bar b)\rightarrow \neg\phi(\bar a).$$ Since the parameters $\bar a$ and $\bar b$ don't occur in $T$, $$T\models \forall \bar v\ (\phi(\bar v)\rightarrow\forall \bar w\ \neg\theta(\bar v,\bar w))$$ But then $\forall \bar w\ \neg\theta(\bar v,\bar w)\in \Gamma$ contradicting the fact that ${\cal M}\models \theta(\bar a,\bar b)$.

$\endgroup$
1
  • $\begingroup$ I just saw your post, after doing a major re-write of mine. Thanks! $\endgroup$ Nov 12, 2013 at 17:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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