From model theory to algebraic geometry and back

Quantifier Elimination

Quantifier elimination is a staple of model theory. Suppose that {\phi(X,Y)} is a quantifier-free formula in some language {L}. Then one says a quantifier-free formula {\psi(Y)} is equivalent modulo a {L}-theory {T} to the (quantified ) formula {(\exists X) \phi(X,Y)}, if in every model {\mathcal{M}} of {T}, {\mathcal{M} \models (\forall Y) ((\exists X) \phi(X;Y) \Leftrightarrow \psi(Y))}.

Geometrically speaking, eliminating existential quantifiers corresponds to taking image under coordinate projection. The statement “{\mathcal{M} \models (\forall Y) ((\exists X) \phi(X;Y) \Leftrightarrow \psi(Y))}” is equivalent to “{\pi_Y(\phi(\mathcal{M})) = \psi(\mathcal{M})}”, where {\pi_Y: \mathcal{M}^{|X|} \times \mathcal{M}^{|Y|} \rightarrow \mathcal{M}^{|Y|}} is the projection map to the “{Y}-coordinates”, and we have used the standard model-thoretic notation to denote {\phi(\mathcal{M}) = { (x,y) \in \mathcal{M}^{|X|} \times \mathcal{M}^{|Y|} \mid \mathcal{M} \models \phi(x,y)}}, and {\psi(\mathcal{M}) = { y \in \mathcal{M}^{|Y|} \mid \mathcal{M} \models \psi(y)}}.


All the above is clear from the logical perspective. The trouble arises when one works at the boundary of model theory and algebraic geometry, and would like to interpret the above definitions in the language of algebraic geometry.

Schematic image, constructible sets and Chevalley’s theorem

Suppose {k} is a field. Denote by {\mathbb{A}^m_k = \mathrm{Spec}(k[X_1,\ldots,X_m])}, the {m}-dimensional affine space over {k}, and let {\pi: \mathbb{A}^m_k \times \mathbb{A}^n_k \rightarrow \mathbb{A}^n_k} the scheme-theoretic morphism, corresponding to the inclusion

\displaystyle k[Y_1,\ldots,Y_n] \hookrightarrow k[X_1,\ldots,X_m,Y_1,\ldots,Y_n] \cong k[X_1,\ldots,X_m] \otimes_k k[Y_1,\ldots,Y_n].


One calls a subset of the underlying topological space (Zariski topology) of the scheme {\mathbb{A}^n_k} to be constructible, if it is a finite union of subsets of the form {X - Y} where {X,Y} are the underlying topological spaces of closed subschemes of {\mathbb{A}^n_k}.


Now if {V \subset \mathbb{A}^m_k \times \mathbb{A}^n_k} is a subscheme, then its schematic image, {\pi(V)}, is a well defined subset of the underlying topological space of {\mathbb{A}^n_k}. What does one mean by the schematic image ? Suppose {\mathfrak{p} \in \mathrm{Spec}(k[Y_1,\ldots,Y_n]) = \mathbb{A}^n_k} is a point of {\mathbb{A}^n_k}.


Let {\pi|_{V}:V \rightarrow \mathbb{A}^n_k } denote the restriction to {V} of the morphism {\pi}, i.e. {\pi|_{V}} corresponds to the composition

\displaystyle f:k[Y_1,\ldots,Y_n] \hookrightarrow k[X_1,\ldots,X_m,Y_1,\ldots,Y_n] \twoheadrightarrow k[V].

Then, {\mathfrak{p}} belongs to the schematic image {\pi(V)} if and only if {\mathfrak{p} = f^{-1}(\mathfrak{q})} for some {\mathfrak{q} \in \mathrm{Spec}(k[V]}. (The schematic image of {V} only depends on the underlying topological space of {V}, and thus we can replace {V} by the corresponding reduced scheme {V_{\mathrm{red}}} ({V_{\mathrm{red}}} is the smallest closed subscheme of {\mathbb{A}^m_k \times \mathbb{A}^n_k} whose underlying space is equal to that of {V}) in the above description without changing {\pi(V)}.)


If {V,Z} are closed subschemes of {\mathbb{A}^m_k \times \mathbb{A}^n_k}, then so is {V \cap Z}. We define the schematic image, {\pi(V - Z)} of the constructible set {V - Z} to be {\pi(V) - \pi(V \cap Z)}, and more generally we define the schematic image of {\pi( \bigcup_{i=1}^k (V_i - Z_i))} by {\bigcup_{i=1}^k \pi(V_i - Z_i)}.

Example 1


The following standard example is helpful. Let {V} be the affine subscheme of {\mathbb{A}^2} defined by the single polynomial {XY - 1} i.e. {V = \mathrm{Spec} \; k[X,Y]/(XY -1)}. Let {\pi: \mathbb{A}^2 \rightarrow \mathbb{A}^1} be the projection (see picture).


Then each closed point {\mathfrak{p} \in \mathbb{A}^1_k = \mathrm{Spec}\; k[Y]}, other than the point {(Y)} is contained in the schematic image of {\pi|_V}. For example, {(Y-1) \in \mathrm{Spec} \ k[Y]} is in the image since {\overline{(Y-1)} \in \mathrm{Spec}\ k[X,Y]/(XY -1)}. However, there is no prime ideal {\mathfrak{q}} of {k[X,Y]/(XY -1)} whose inverse image under the composition {k[Y] \hookrightarrow k[X,Y] \twoheadrightarrow k[X,Y](XY -1)} is equal to {(Y)}. Note that the ideal generated by {\overline{Y}} in {k[X,Y]/(XY -1)} contains {\overline{1}} (i.e. corresponds to the generic element of {V}), and its inverse image in {k[Y]} is {k[Y]} itself, which corresponds to the generic element of {\mathbb{A}^1_k} (confirming the intuition that the generic element of {V} maps to the generic element of {\mathbb{A}^1}). But the schematic map {\pi|_V} is not surjective, since the closed point corresponding to the ideal {(Y)} is not in the image.

Chevalley’s theorem

Chevalley’s theorem states that the schematic image of a constructible set (as defined previously) is again constructible.

What’s the connection with model theory ?

There is the obvious temptation to identify constructible subsets of {\mathbb{A}^n_k} with definable subsets of {k^n}, for {k} a model of some theory {T} which extends the theory of fields. If {T} is the theory of algebraically closed fields, then {k} is algebraically closed, and each definable subset of {k^n} can be identified with the set of closed points of some constructible subset of {\mathbb{A}_k^n}. In this case the closed points also correspond to the {k}-rational points — and so the each definable subset of {k^n} is of the form, {\bigcup_{i=1}^{k} (V_i(k) - Z_i(k))}, for closed subschemes {V_i,Z_i} of {\mathbb{A}_k^n}. Chevalley’s theorem then immediately implies in particular that the theory of algebraically closed fields admits quantifier elimination.

1. What about non-algebraically closed fields ?

What if one considers some theory (still in the language of fields) of fields (for example, the theory of real closed fields, or the theory of {\mathbb{Q}_p}) which are not algebraically closed. Chevalley’s theorem still holds. But what breaks down now is that the definable subsets of {k^n} are no longer just the sets of the form {\bigcup_{i=1}^{k} (V_i(k) - Z_i(k))}, for closed subschemes {V_i,Z_i}. The class of the former can be strictly bigger. Moreover, even if one restricts to definable subsets of {k^m \times k^n} of the form {\bigcup_{i=1}^{k} (V_i(k) - Z_i(k))}, for closed subschemes {V_i,Z_i}, the {k}-points of the schematic image {\bigcup_{i=1}^{k} \pi(V_i - Z_i)} can be strictly larger than the image under the set-theoretic projection of the definable subset under consideration.

Example 2

Take for example the definable subset of {\mathbb{R} \times \mathbb{R}} defined by the one equation {X^2 + Y^2 -1 =0}. The image of the set theoretic projection to the {Y}-axis of the {\mathbb{R}}-points of the affine subscheme {V \subset \mathbb{A}^2} defined by {X^2+Y^2 -1} is obviously the real interval {[-1,1]} (which note is not a definable subset of {{\mathbb R}}). But if one takes the schematic image {\pi(V)}, and then considers the {\mathbb{R}}-points of {\mathbb{A}^1} contained in {\pi(V)}, then we get all of {\mathbb{R}}.


Thus, taking the {k}-points “upstairs” and then the set theoretic image, can produce a strictly smaller set, than first taking the schematic image and then the {k}-points of the image “downstairs”.


The above example shows that the theory of real closed fields does not admit quantifier elimination. The image under projection of a definable subset need not be definable. One can recover quantifier elimination by expanding the language (and thus also the definable subsets). For example, clearly one must include the subset {[-1,1] \subset \mathbb{R}^1} which occurs in the example above. One way is to expand the language and include the predicate {\mathbf{P}_2(X) := (\exists Y) (X = Y^2)} (often, abbreviated to {(X \geq 0)} (!)). The resulting theory in the expanded language does have quantifier elimination. This is the Tarski-Seidenberg theorem — while being still elementary — is harder to prove than Chevalley’s theorem. In the case of the theory of {\mathbb{Q}_p}, in order to get quantifier elimination one has to go further and include all the predicates {\mathbf{P}_n(X) := (\exists Y) (X = Y^n), n \geq 2} (Macintyre predicates).


The property of having quantifier-elimination in theories of non-alegebraically closed fields always involve some special property of the models of the theory in question (for example, the fact that real closed fields admit a unique ordering in the case of the reals).

Coming attraction

This post is a prelude to a longer post that I have been thinking about making on the connections between quantifier elimination, cohomology and complexity theory. A glimpse of this is available here:


Connectivity of joins, cohomological quantifier elimination, and an algebraic Toda’s theorem, Saugata Basu, Deepam Patel, Selecta Mathematica, volume 26, (2020).

References

All background material can be found in the two books shown below.

Standard disclaimer

It goes without saying that the views expressed are mine and may not reflect those of my co-authors/co-conspirators. The LaTeX to WordPress conversion was done using the latex2wp package written by Luca Trevisan.

Standard

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s