en>David Eppstein: templatize two refs

2014-01-25T23:40:31Z

templatize two refs

New page

In [[mathematics]], the '''Tarski–Seidenberg theorem''' states that a set in (''n'' + 1)-dimensional space defined by [[Polynomial#Polynomial_equations|polynomial equations]] and [[inequality (mathematics)|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 connectors ∨ (''or''), ∧ (''and''), ¬ (''not'') and quantifiers ∀ (''for all''), ∃ (''exists'') is equivalent with a similar formula without quantifiers.

==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
:<math>p(x_1,\ldots,x_n)=0\,</math>
and
:<math>q(x_1,\ldots,x_n)>0\,</math>
for polynomials ''p'' and ''q''. We define a projection map ''π'' : '''R'''''n''+1 → '''R'''''n'' by sending a point (''x''1,...,''x''''n'',''x''''n''+1) to (''x''1,...,''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 set]]s rather than ''semi''algebraic sets. For these sets the theorem fails. As a simple example consider the circle in '''R'''2 defined by the equation
:<math>x^2+y^2-1=0.\,</math>
This is a perfectly good algebraic set, but project it down by sending (''x'',''y'') in '''R'''2 to ''x'' in '''R''' and we have the set of points satisfying -1 ≤ ''x'' ≤ 1. This is a semialgebraic set as we would expect from the theorem, but it is not an algebraic set.

==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''1 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 this holds if ''S''''n'' is the set of semialgebraic sets in '''R'''''n''.

==External links==
{{planetmath reference|id=8998|title=Tarski–Seidenberg theorem}}

==References==
* L. van den Dries, ''Tame topology and o-minimal structures'', London Mathematical Society Lecture Note Series. 248, Cambridge University Press 1998.

{{DEFAULTSORT:Tarski-Seidenberg theorem}}
[[Category:Real algebraic geometry]]
[[Category:Theorems in algebraic geometry]]

Multiplicative calculus - Revision history

en>David Eppstein: templatize two refs