Semialgebraic set

In mathematics, a basic semialgebraic set is a set defined by polynomial equalities and polynomial inequalities, and a semialgebraic set is a finite union of basic semialgebraic sets. A semialgebraic function is a function with a semialgebraic graph. Such sets and functions are the main object of study of real algebraic geometry the part of algebraic geometry devoted to points with real coordinates.

Tarski–Seidenberg theorem implies that the semialgebraic sets are exactly those sets that can be defined by a well-formed formula built with quantifiers ⁠∀ , ∃ {\displaystyle \forall ,\exists }⁠, logical connectives ⁠∧ , ∨ , ¬ {\displaystyle \land ,\lor ,\lnot }⁠, basic arithmetic operators ⁠+ , − , × , / {\displaystyle +,-,\times ,/}⁠, equality and inequality signs ⁠= , < , ≤ {\displaystyle =,<,\leq }⁠, integers, and variables representing real numbers.

Definition

Let R {\displaystyle \mathbb {R} } be the field of real numbers, or, more generally, any real closed field.

A basic semialgebraic set in ⁠R n {\displaystyle \mathbb {R} ^{n}}⁠ is the set of the common solutions of a finite number of polynomial equations and inequalities of the form P ( x 1 , … , x n ) = 0 {\displaystyle P(x_{1},\ldots ,x_{n})=0} or Q ( x 1 , … , x n ) > 0 , {\displaystyle Q(x_{1},\ldots ,x_{n})>0,} whee ⁠P {\displaystyle P}⁠ and ⁠Q {\displaystyle Q}⁠ are polynomial coefficients

A semialgebraic set in ⁠R n {\displaystyle \mathbb {R} ^{n}}⁠ is a finite union of basic semialgebraic sets.

Tarski–Seidenberg theorem and basic rules of Boolean algebra and algebra imply that semialgebra sets are exactly those subsets of ⁠R n {\displaystyle \mathbb {R} ^{n}}⁠ that can be defined by a well-formed formula built from the quantifiers ⁠∀ , ∃ {\displaystyle \forall ,\exists }⁠, the logical connectives ⁠∧ , ∨ , ¬ {\displaystyle \land ,\lor ,\lnot }⁠, the arithmetic operators ⁠+ , − , × , / {\displaystyle +,-,\times ,/}⁠, integers, and the variables ⁠x 1 , … , x n {\displaystyle x_{1},\ldots ,x_{n}}⁠.

So, the definition of semialgebraic sets may be viewed as a kind of normal form for this general class of first-order formulas.

Dimension 1

In ⁠R {\displaystyle \mathbb {R} }⁠, a semialgebraic set is the union a finite number of intervals whose end points are algebraic numbers; this includes zero-length intervals that are each reduced to a single algebraic number. Conversely, such an union is a always a semialgebraic set.

For proving this we define first some special basic semialgebraic sets. Then we prove that every basic algebraic sset is a disjoint union of such special sets and that this implies the result.

By definition of an algebraic number, an algebraic number ⁠α {\displaystyle \alpha }⁠ is a root of a square-free polynomial ⁠P ( x ) {\displaystyle P(x)}⁠ with integer coefficients and positive leading coefficient (the square-free condition implies that the polynomial changes of sign at each root). Real-root isolation provides algorithms for computing two rational numbers ⁠a {\displaystyle a}⁠ and ⁠b {\displaystyle b}⁠ such that ⁠a < α < b {\displaystyle a<\alpha <b}⁠ and there is no other root of ⁠P {\displaystyle P}⁠ in the interval ⁠[ a , b ] {\displaystyle [a,b]}⁠. So, the singleton { α } = { x ∣ P ( x ) = 0 ∧ x − a > 0 ∧ b − x > 0 } {\displaystyle \{\alpha \}=\{x\mid P(x)=0\land x-a>0\land b-x>0\}} is a basic semialgebraic set.

With the same notation, if ⁠α {\displaystyle \alpha }⁠ is the largest root of ⁠P {\displaystyle P}⁠, the open interval ⁠( α , + ∞ ) {\displaystyle (\alpha ,+\infty )}⁠ a basic semialgebraic set, since ( α , + ∞ ) = { x ∣ P ( x ) > 0 ∧ x − a > 0 } . {\displaystyle (\alpha ,+\infty )=\{x\mid P(x)>0\land x-a>0\}.}

Similarly, if ⁠α {\displaystyle \alpha }⁠ is the smallest root, one has the basic semialgebraic set ( − ∞ , α ) = { x ∣ P ( a ) P ( x ) > 0 ∧ b − x > 0 } . {\displaystyle (-\infty ,\alpha )=\{x\mid P(a)P(x)>0\land b-x>0\}.}

If ⁠α < β {\displaystyle \alpha <\beta }⁠ are two consecutive roots of ⁠P {\displaystyle P}⁠, real-root isolation provides three rational numbers ⁠a {\displaystyle a}⁠, ⁠b {\displaystyle b}⁠ and ⁠c {\displaystyle c}⁠ such that ⁠a < α < b < β < c {\displaystyle a<\alpha <b<\beta <c}⁠ and the interval ⁠[ a , b ] {\displaystyle [a,b]}⁠ does not contain any other root of ⁠P {\displaystyle P}⁠. In this case, ( α , β ) = { x ∣ P ( b ) P ( x ) > 0 ∧ c − x > 0 ∧ x − a > 0 } {\displaystyle (\alpha ,\beta )=\{x\mid P(b)P(x)>0\land c-x>0\land x-a>0\}} expresses ⁠( α , β ) {\displaystyle (\alpha ,\beta )}⁠ as a basic algebraic set.

Now, given a basic semialgebraic set, there are two cases: firstly if its definition contains at least one equation ⁠P ( x ) = 0 {\displaystyle P(x)=0}⁠, the set consists of a subset of the roots of ⁠P {\displaystyle P}⁠, and is thus the union of above special basic sets.

If there is no equation in the definition of the basic algebraic set, it has the form S = { x ∣ P 1 ( x ) > 0 ∧ ⋯ ∧ P k ( x ) > 0 } . {\displaystyle S=\{x\mid P_{1}(x)>0\land \cdots \land P_{k}(x)>0\}.} Since each ⁠P i {\displaystyle P_{i}}⁠ has a constant sign in each open interval delimited by two consecutive roots of the product ⁠P = P 1 ⋯ P k {\displaystyle P=P_{1}\cdots P_{k}}⁠, the set ⁠S {\displaystyle S}⁠ is the union of some ot these intervals, and thus a union of special basic semialgebraic sets.

The final result follows since a finite union of singletons and open intervals is also a disjoint union of points nd intervals.

Properties

Similarly to algebraic subvarieties, finite unions and intersections of semialgebraic sets are still semialgebraic sets. Furthermore, unlike subvarieties, the complement of a semialgebraic set is again semialgebraic. Finally, and most importantly, the Tarski–Seidenberg theorem says that they are also closed under the projection operation: in other words a semialgebraic set projected onto a linear subspace yields another semialgebraic set (as is the case for quantifier elimination). These properties together mean that semialgebraic sets form an o-minimal structure on R.

A semialgebraic set (or function) is said to be defined over a subring A of R if there is some description, as in the definition, where the polynomials can be chosen to have coefficients in A.

On a dense open subset of the semialgebraic set S, it is (locally) a submanifold. One can define the dimension of S to be the largest dimension at points at which it is a submanifold. It is not hard to see that a semialgebraic set lies inside an algebraic subvariety of the same dimension.

Semialgebraic set

Definition

Dimension 1

Properties

See also

External links