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.
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 example shows also that, over the complex numbers, the projection of an algebraic set may be non-algebraic.
This result confirmed that semialgebraic sets in Rn form what is now known as an o-minimal structure on R. These are collections of subsets Sn of Rn for each n ≥ 1 such that we can take finite unions and complements of the subsets in Sn and the result will still be in Sn, moreover the elements of S1 are simply finite unions of intervals and points.