Tarski–Seidenberg Theorem

In mathematics, the Tarski–Seidenberg theorem states that a set in (''n'' + 1)-dimensional space defined by polynomial equations and inequalities can be projected down onto ''n''-dimensional space, and the resulting set is still definable in terms of polynomial identities and inequalities. The theorem—also known as the Tarski–Seidenberg projection property—is named after Alfred Tarski and Abraham Seidenberg. It implies that quantifier elimination is possible over the reals, that is that every formula constructed from polynomial equations and inequalities by logical connectives (''or''), (''and''), (''not'') and quantifiers (''for all''), (''exists'') is equivalent to a similar formula without quantifiers. An important consequence is the decidability of the theory of real-closed fields.

Although the original proof of the theorem was constructive, the resulting algorithm has a computational complexity that is 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. This algorithm is therefore fundamental, and it is widely used in computational algebraic geometry.

Statement

A semialgebraic set in R^''n'' is a finite union of sets defined by a finite number of polynomial equations and inequalities, that is by a finite number of statements of the form
:$p(x_1,\ldots,x_n)=0\,$
and
:$q(x_1,\ldots,x_n)>0\,$
for polynomials ''p'' and ''q''. We define a projection map ''π'' : R^''n''+1 → R^''n'' by sending a point (''x''₁, ..., ''x''_''n'', ''x''_''n''+1) to (''x''₁, ..., ''x''_''n''). Then the Tarski–Seidenberg theorem states that if ''X'' is a semialgebraic set in R^''n''+1 for some ''n'' ≥ 1, then ''π''(''X'') is a semialgebraic set in R^''n''.

Failure with algebraic sets

If we only define sets using polynomial equations and not inequalities then we define algebraic sets rather than ''semi''algebraic 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.

Another example is the parabola in R², which is defined by the equation
:$y^2-x=0.$
Its projection onto the ''x''-axis is the half-line intersections, unions, and set complement">int.html" ;"title=", ∞), a semialgebraic set that cannot be obtained from algebraic sets by (finite) intersection (set theory)">intersections, unions, and set complements.

Relation to structures

This result confirmed that semialgebraic sets in R^''n'' form what is now known as an o-minimal structure on R. These are collections of subsets ''S''_''n'' of R^''n'' 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^''n''+1 to R^''n'' 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^''n''.

See also

* Decidability of first-order theories of the real numbers

References

*
*
*

External links

Tarski–Seidenberg theorem
at PlanetMath.org

{{DEFAULTSORT:Tarski-Seidenberg theorem
Real algebraic geometry
Theorems in algebraic geometry