[Note: In spite of the term "elimination of quantifiers" in the title, this post does NOT involve mathematical logic--or at least, no more so than, e.g., the distinction between continuity and uniform continuity.]
[Prerequisite: Familiarity with the main theorem of elimination theory, in the form that the projection
takes Zariski-closed sets to Zariski-closed sets. Related theorems, such as Chevalley's theorem, are also helpful.]
There are, roughly speaking, two ways in which elimination theory is typically described: a “theoretical” version, such as the statement above; and a more “applied” or “elementary” version, which is about systems of equations and “elimination of variables.” Both statements are important. However, I have found the “elimination of variables” statement confusing and difficult to remember, much less apply.
Recently, I happened upon a way of thinking about elimination theory that seems to make it much easier to “translate” between the “applied” description and the “theoretical” description. The key is to think about elimination theory in terms of elimination of quantifiers, rather than elimination of variables.
Often, in algebraic geometry, we encounter conditions like the following condition on :
where is an algebraic condition on and . We might have and ranging over finite-dimensional vector spaces and , respectively. ( and might be more general varieties, also.) We would like to turn this into a purely algebraic condition on .
Here is the key insight (which, like so many “key insights”, is logically trivial): Let be the set of all ordered pairs such that holds. The statement that “ is an algebraic condition” is, presumably, a statement that is a nice set from an algebro-geometric point of view (e.g., Zariski closed, or possibly Zariski open, or locally closed, or constructible). The statement above is precisely equivalent to the statement that
lies in the image of under the projection .
We are interested in knowing whether this image can be described by a purely algebraic condition; and this is precisely the sort of question that the “theoretical” version of elimination theory is good at answering.
I give three examples to illustrate this technique. The first, showing that injectivity is an open condition on a space of linear maps, is very much a toy example: there is a more direct proof using determinants that is, I think, a better proof for any purpose other than illustrating the use of elimination theory. The third example has a direct proof using resultants. I don’t know a direct proof for the second example, but I would not be at all surprised to learn that there is one. (Incidentally, if you do know one, please let me know about it.)
Example 1: Let and be finite-dimensional vector spaces over an infinite field . Consider the set consisting of those linear maps which are injective. I will use elimination theory to show that is a Zariski-open subset of the vector space .
Proof: Let be an element of . Then is injective iff
The first issue is that the quantifier here is , whereas the quantifier we can handle with elimination theory is . We can solve this by replacing by the equivalent , where denotes “not”:
Now, to make this a statement regarding projective space, note that for any , we have that if and only if . Thus, the above is equivalent to
In other words, the complement of is the image of under the projection . By the main theorem of elimination theory, this image is closed. Hence, its complement, , is open.
Example 2: Let denote a finitely generated, graded -algebra, with the degree-zero part being precisely . Let . Then is a Zariski-closed subset of the -vector space .
Proof: The statement is equivalent to the statement that
This, in turn, is equivalent to
where we write if for some . The condition is closed in all variables and homogeneous in , so by the main theorem of elimination theory, the set of all pairs for which such an exists is closed.
Example 3: With the same notation as above, but allowing , the set is closed.
Clearly, . Thus, it suffices to show that is closed. Now, if and only if
We just showed, in Example 2, that and are closed conditions; hence, their conjunction is also closed. Furthermore, this condition is clearly homogeneous in . Hence, by the main theorem of elimination theory, is closed.
Thoughts: In these examples, I have focused specifically on the use of the main theorem of elimination theory. However, there are other, related theorems that can also be useful. For instance, if and are schemes of finite type over , then the projection is necessarily open. This follows from the fact that flat, finite-type morphisms of Noetherian schemes are open, although there is probably a more elementary proof.
Chevalley’s Theorem, stating that the image of a constructible set under a finite-type morphism is constructible (assuming all schemes Noetherian), can also be useful here. The “elimination-theoretic” version states that if you write out any condition like the ones above (using things like , , , “and”, “or”, and “implies” at will), then as long as the “innermost conditions” are open or closed, the resulting condition will be constructible. Since the hypotheses are quite weak, the conclusion in this case is not terribly strong; however, it can still be useful. For instance, suppose you can write a set as the intersection of an infinite collection of open sets. If you can describe the same set using finitely many “constructible” conditions, then the set is necessarily open. [Proof: an arbitrary intersection of open sets is stable under generization. If a constructible set is closed under generization, then it is open.]