Tarski–Seidenberg theorem

Short description: Quantifier elimination for semi-algebraic sets

In mathematics, the Tarski–Seidenberg theorem is a theorem on semialgebraic sets, that is, subsets of real coordinate spaces that can be defined by a finite set of polynomial equations and polynomial inequalities. This theorem was proved by Alfred Tarski in 1930 in view of his proof that the theory of real closed fields is complete (every formula can be proved either as true or as false) and admits quantifier elimination. The theorem was later discovered indepedently by Abraham Seidenberg in the context of constructive mathematics.

The theorm states that, given a set S in the (n + 1)-dimensional space, which is defined by polynomial equations and inequalities involving (n + 1) variables, the projecion eliminating one of the variables can be defined similarly. In other words, if ${ℱ}(y,x_1,\dots ,x_n)$ is the formula defining S, there exists a formula ${𝒢}(x_1,\dots ,x_n)$ that define the same set as $\mathrm{\exists }y\mid {ℱ}(y,x_1,\dots ,x_n)$.

Although the original proof of the theorem was constructive, the resulting algorithm is galactic, that is, it has a computational complexity that is far too high for using the method on a computer. George E. Collins introduced the algorithm of cylindrical algebraic decomposition, which allows quantifier elimination over the reals in double exponential time. This complexity is optimal, as there are examples where the output has a double exponential number of connected components. Collins's algorithm is therefore fundamental and widely used in computational algebraic geometry.

First order formulas

A formula of the first-order theory of the real numbers is a well-formed formula involved only the quantifier $\mathrm{\forall },\mathrm{\exists }$, the logical connectives $\wedge ,\vee ,\mathrm{\neg }$, real numbers and variables representing real numbers, equality and inequality signs $=,<,\le$, and the basic arithmetic operators $+,-,\times ,/$.

A formula is quantifier free if does not involve any quantifier. Two formulas are equivalent if they evaluate to the same truth value for every choice of (real) values for the variables. In particular, a formula is true or false for every values of the variables if it is equivalent to $0=0$ or $1=0$

Elimination of quantifiers consists of providing an algorithm that, for every formula computes an equivalent quantifier-free formula. If quantifier elimination occurs, the theory is complete in the sense that one can decide whether a variable-free formula is true of false.

Tarski–Seidenberg theorem is that quantifier elimination is possible in the first-order theory of the real numbers, and thus that this theory is complete

Semialgebraic sets

Main article: Semialgebraic set

A semialgebraic set is a set defined by a quantifier-free formula of the first-order theory of the real numbers. By standard logical (disjunctive normal form) and algebraic manipulations, it is straightforward to show that a semialgebraic set in Rⁿ is formed by taking a finite union of basic semialgebraic sets. A basic semialgebraic set is the set of all points that simultaneously satisfy a finite number of polynomial equations and inequalities of the form

$p(x_1,\dots ,x_n)=0$

and

$q(x_1,\dots ,x_n)>0$

for polynomials p and q.

For example, a basic semialgebraic set in $\mathbb{ℝ}$ either consists of a finite number of points or is a finite union of open intervals. Conversely a singleton formed by an algebraic number is a basic semialgebraic set, and every interval (open of not) is a semialgebraic set if its end points are algebraic numbers.

Method of proof

All known proofs of the theorem work by recurrence on the number of variables. For this purpose, one considers a projection map π : Rⁿ⁺¹ → Rⁿ that sends the point (x₁, ..., x_n, x_n+1) to (x₁, ..., x_n).

The main step of the proof of the theorem is to prove the fundamental property that, if Y is a semialgebraic set in Rⁿ⁺¹ for some n ≥ 1, then X = π(Y) is a semialgebraic set in Rⁿ.

Moreover, given a semialgebraic decomposition of X in disjoint basic semialgebraic sets $B_i$, one gets a decomposition of Y into basic semialgebraic sets of the for $B_i\cap C_{i,j}$, where each $C_{i,j}$ is a basic semialgebraic set in the single variable $x_{n+1}$ that is either a point or an open interval.

In the case of one variable, every semialgebraic set is the union of semialgebraic sets that are reduced to a single point or an open interval (see Real-root isolation). Using this, one can recursively suppose that all involved polynomials have a constant sign ($+,-$ or $0$) on each basic semialgebraic set appearing in the decomposition. So, one can test the truth of a quantified formula by testing it on a finite number of sample points, one for each basic semialgebraic point of the decomposition. This allows proving the theorem.

Failure with algebraic sets

If we only define sets using polynomial equations and not inequalities then we define algebraic sets rather than semialgebraic sets. For these sets the theorem fails, i.e. projections of algebraic sets need not be algebraic. As a simple example consider the hyperbola in R² defined by the equation

$xy-1=0.$

This is a perfectly good algebraic set, but projecting it down by sending (x, y) in R² to x in R produces the set of points satisfying x ≠ 0. This is a semialgebraic set, but it is not an algebraic set as the algebraic sets in R are R itself, the empty set and the finite sets.

This example shows also that, over the complex numbers, the projection of an algebraic set may be non-algebraic. Thus the existence of real algebraic sets with non-algebraic projections does not rely on the fact that the field of real numbers is not algebraically closed.

However, one often define quasialgebraic sets similarly as semialgebraic sets, simply by replacing "real" with "complex" and $>$ with $\ne$. Everything that is said above on semialgebraic sets remains true for quasialgebraic set, with much simpler proofs. In particular, the first-order theory of complex numbers is complete and has quantifier elimination, the projection of a quasialgebraic set is quasialgebraic, etc.

Forexample consider the hyperbola defined by the equation

$xy-1=0.$

Over the real numbers, its projection onto the x-axis is the union of the half lines (0, ∞) and (– ∞, 0), a semialgebraic set that is not an algebraic set. Over the complex, the projecion is the complement of 0, defined as $\{x\in \mathbb{ℂ}\mid x\ne 0\}$, which is a quasialgebraic set but not an algebrraic set.

Relation to structures

This result confirmed that semialgebraic sets in Rⁿ form what is now known as an o-minimal structure on R. These are collections of subsets S_n of Rⁿ for each n ≥ 1 such that we can take finite unions and complements of the subsets in S_n and the result will still be in S_n, moreover the elements of S₁ are simply finite unions of intervals and points. The final condition for such a collection to be an o-minimal structure is that the projection map on the first n coordinates from Rⁿ⁺¹ to Rⁿ must send subsets in S_n+1 to subsets in S_n. The Tarski–Seidenberg theorem tells us that this holds if S_n is the set of semialgebraic sets in Rⁿ.

See also

• Decidability of first-order theories of the real numbers

References

• van den Dries, L. (1998). Tame topology and o-minimal structures. London Mathematical Society Lecture Note Series. 248. Cambridge University Press. 
• Khovanskii, Askold G. (1991). Fewnomials. Translations of Mathematical Monographs. 88. Translated from the Russian by Smilka Zdravkovska. Providence, RI: American Mathematical Society. ISBN 0-8218-4547-0. 
• Neyman, Abraham (2003). "Real Algebraic Tools in Stochastic Games". Stochastic Games and Applications. Dordrecht: Kluwer. pp. 57–75. ISBN 1-4020-1492-9. https://books.google.com/books?id=iCZrCQAAQBAJ&pg=PA57. 

External links

• Tarski–Seidenberg theorem at PlanetMath.org