Semialgebraic set

A semialgebraic set in \mathbb{R}^n is a subset defined as a finite union of sets of the form \{x \in \mathbb{R}^n \mid f_i(x) = 0 \ (i \in I), \, g_j(x) > 0 \ (j \in J)\}, where the f_i and g_j are polynomials with real coefficients and I, J are finite index sets.^[1] Equivalently, semialgebraic sets are the subsets of \mathbb{R}^n obtained by finite Boolean combinations (unions, intersections, and complements) of sets defined by polynomial equalities P(x) = 0 or strict inequalities P(x) > 0, where P has real coefficients; this class is the smallest containing the basic sets \{x \in \mathbb{R}^n \mid P(x) = 0\} and \{x \in \mathbb{R}^n \mid P(x) > 0\} and closed under finite unions, intersections, and complements.^[2] Semialgebraic sets form a fundamental class in real algebraic geometry, encompassing algebraic varieties (defined by equalities alone) as well as more general regions delimited by polynomial inequalities, such as polyhedra or spectrahedra in optimization.^[1] They are stable under key operations: the projection of a semialgebraic set onto a coordinate subspace is semialgebraic (by the Tarski-Seidenberg theorem, also known as quantifier elimination for real closed fields), and they are closed under images and inverse images under polynomial maps.^[2] Every semialgebraic set admits a cell decomposition into finitely many cells, each semialgebraically homeomorphic to an open cube (0,1)^d for some d, implying that semialgebraic sets have finitely many connected components and a well-defined dimension as the maximum d over such decompositions.^[3] These properties underpin algorithmic developments in real algebraic geometry, enabling effective computation of topological invariants like Betti numbers and roadmaps (curves meeting every connected component) for semialgebraic sets defined by polynomials of degree at most d and involving s polynomials in \mathbb{R}^n, with complexities bounded singly exponentially in the input size.^[4] Semialgebraic sets also play a central role in o-minimal structures, where they tame the complexity of definable sets in analysis and geometry, facilitating applications in robotics, control theory, and quantifier elimination over the reals.^[1]

Definition and Examples

Formal Definition

A semialgebraic set is a subset of \mathbb{R}^n for some nonnegative integer n, generated by polynomial conditions with real coefficients. Specifically, the class of semialgebraic sets in \mathbb{R}^n is the smallest family of subsets closed under finite unions, finite intersections, and complements, and containing all sets of the form \{x \in \mathbb{R}^n \mid P(x) = 0\} and \{x \in \mathbb{R}^n \mid P(x) > 0\}, where P \in \mathbb{R}[x_1, \dots, x_n].^[3] A basic semialgebraic set is defined as a finite intersection of sets specified by polynomial equalities and inequalities:

\{x \in \mathbb{R}^n \mid f_1(x) = 0, \dots, f_s(x) = 0, \, g_1(x) > 0, \dots, g_t(x) > 0 \},

or variants using non-strict inequalities g_j(x) \geq 0, where each f_i, g_j is a polynomial with real coefficients in n variables.^[3]^[5] Equivalently, a basic semialgebraic set can be expressed using sign conditions on polynomials, such as \operatorname{sgn}(f_{i,j}(x)) = s_{i,j} for signs s_{i,j} \in \{-1, 0, 1\}.^[5] In general, a semialgebraic set is a finite union of basic semialgebraic sets, or more broadly, the set of points in \mathbb{R}^n satisfying a quantifier-free first-order formula over the reals involving polynomials:

S = \{ x \in \mathbb{R}^n \mid \phi(x_1, \dots, x_n) = \mathrm{True} \},

where \phi is built from atoms P_i(x) = 0 and Q_j(x) \geq 0 (or > 0) using Boolean connectives \land, \lor, \lnot.^[3]^[5] This generative structure via Boolean combinations of zero sets \{P_i = 0\} and positive sets \{Q_j > 0\} underscores their role in real algebraic geometry.^[3] Distinctions among semialgebraic sets include open variants, defined solely by strict polynomial inequalities g_j(x) > 0; closed variants, incorporating equalities f_i(x) = 0 and non-strict inequalities g_j(x) \geq 0; and basic sets as intersections without unions or complements. These forms highlight the topological flexibility within the semialgebraic framework.^[3]^[5]

Basic Examples

A basic semialgebraic set in \mathbb{R}^2 is the closed unit disk \{(x,y) \in \mathbb{R}^2 \mid x^2 + y^2 \leq 1\}, defined by the single polynomial inequality x^2 + y^2 - 1 \leq 0.^[2]^[4] This set is closed and bounded, with a single connected component.^[6] Another example is the open set \{(x,y) \in \mathbb{R}^2 \mid xy > 0\}, which consists of the two opposite quadrants where x and y have the same sign; this is the union of the basic open sets \{x > 0, y > 0\} and \{x < 0, y < 0\}.^[2]^[3] It has two connected components, corresponding to the branches of the hyperbola xy = 0.^[6] To illustrate more complex Boolean combinations aligned with the formal definition of semialgebraic sets, consider the set in \mathbb{R}^2 defined implicitly by the existence of a nonnegative z satisfying z^2 = x^2 + y^2 - 1 and z \geq 0; this is the closed exterior of the unit disk \{(x,y) \in \mathbb{R}^2 \mid x^2 + y^2 \geq 1\}, which is semialgebraic (as confirmed by projection theorems discussed later) and has one connected component.^[4]^[2] In contrast, the set of rational numbers \mathbb{Q} \subset \mathbb{R} is not semialgebraic, as semialgebraic subsets of \mathbb{R} are finite unions of points and open intervals, leading to finitely many connected components, whereas \mathbb{Q} has infinitely many.^[2]^[3]^[4]

Fundamental Properties

Topological Properties

Semialgebraic sets in Euclidean space possess a tame topology, characterized by several fundamental properties that distinguish them from more general subsets. A central feature is the finiteness of their connected components: every semialgebraic set has finitely many connected components, and each such component is itself a semialgebraic set.^[3] Moreover, semialgebraic sets are locally connected, meaning that every point has a local basis of connected neighborhoods, and each connected component is path-connected via continuous paths lying within the set.^[3] The closure of any semialgebraic set is semialgebraic, as is its interior, preserving the class under these standard topological operations.^[7] Semialgebraic sets are also locally compact, with every point admitting a compact neighborhood within the set, and they are Borel measurable, belonging to the Borel σ-algebra generated by the open sets in \mathbb{R}^n.^[8] The family of closed semialgebraic subsets of \mathbb{R}^n induces a Noetherian topology on \mathbb{R}^n, in which there are no infinite strictly descending chains of closed sets; this follows from the finite complexity of semialgebraic decompositions.^[9] For illustration, consider the semialgebraic set S = \{x \in \mathbb{R} \mid x^2 < 1\} \cup \{x \in \mathbb{R} \mid x > 2\}. This set consists of two connected components: the open interval (-1, 1) and the ray (2, \infty), demonstrating the finiteness property in one dimension, where semialgebraic sets are finite unions of points and intervals.^[3]

Geometric Properties

Semialgebraic sets possess a well-defined dimension that captures their geometric complexity, analogous to the dimension in algebraic geometry. The dimension of a semialgebraic set S \subset \mathbb{R}^n is defined as the maximum k such that S contains a k-dimensional semialgebraic cell in some decomposition of S, where the dimension of a cell is the dimension of the Euclidean space it is homeomorphic to.^[10] This definition aligns with the Krull dimension of the associated ideal in the polynomial ring for algebraic subsets, ensuring that the dimension of an algebraic set viewed as a semialgebraic set coincides with its classical algebraic dimension.^[10] More formally, \dim(S) = \max \{ k \mid \text{there exists a } k\text{-dimensional semialgebraic [cell](/page/Cell) in a [decomposition](/page/Decomposition) of } S \}.^[3] A key geometric feature is that every semialgebraic set admits a finite Whitney stratification, partitioning it into finitely many semialgebraic strata (cells) of varying dimensions, where each cell is a smooth Nash manifold homeomorphic to an open ball (0,1)^k in \mathbb{R}^k or a point (for k=0).^[3] This stratification satisfies the Whitney conditions (a) and (b), ensuring local triviality and regularity of the tangent spaces across strata boundaries.^[8] The cells form a cellular decomposition, with the closure of each higher-dimensional cell being a union of cells of equal or lower dimension, providing a controlled way to understand the set's structure.^[3] Compact semialgebraic sets further admit a semialgebraic triangulation, where the set is homeomorphic via a semialgebraic map to a simplicial complex, with the images of the open simplices forming part of the Whitney stratification.^[3] This triangulation preserves the dimension, as the highest-dimensional simplices correspond to the maximal cells in the decomposition. The dimension of a semialgebraic set S equals the dimension of its Zariski closure \overline{S}_Z, an algebraic set whose dimension coincides with the algebraic (Krull) dimension.^[10]

Key Theorems

Tarski-Seidenberg Theorem

The Tarski-Seidenberg theorem states that the image of a semialgebraic set under a polynomial map is semialgebraic. More precisely, if S \subset \mathbb{R}^{n+m} is semialgebraic and \pi: \mathbb{R}^{n+m} \to \mathbb{R}^n is the linear projection onto the first n coordinates, given by \pi(x,y) = x where x \in \mathbb{R}^n and y \in \mathbb{R}^m, then

\pi(S) = \{ x \in \mathbb{R}^n \mid \exists y \in \mathbb{R}^m \text{ such that } (x,y) \in S \}

is semialgebraic. This result extends to images under arbitrary polynomial maps f: \mathbb{R}^{n+m} \to \mathbb{R}^n, where f(S) remains semialgebraic.^[4]^[11] The theorem was originally proved by Alfred Tarski in the 1930s during his investigations into the decidability of the first-order theory of real closed fields, with the full exposition appearing in his 1951 monograph. An alternative, purely algebraic proof was provided by Abraham Seidenberg in 1954, avoiding some of the logical machinery in Tarski's approach while confirming the same structural preservation.^[12]^[13] A key implication is that the class of semialgebraic sets is closed under projections, images, and preimages with respect to polynomial maps; for instance, the preimage f^{-1}(S) for a polynomial f: \mathbb{R}^n \to \mathbb{R}^k and semialgebraic S \subset \mathbb{R}^k can be expressed using existential quantifiers over the defining polynomials, reducing to a projection that remains semialgebraic by the theorem. This closure property underpins the Boolean structure of semialgebraic sets, ensuring that operations like elimination of variables preserve the semialgebraic nature without introducing non-polynomial conditions.^[4] For example, consider the semialgebraic set \{(x,y) \in \mathbb{R}^2 \mid y^2 = x^3 - x\}, which defines the real points of the elliptic curve y^2 = x(x-1)(x+1). The projection onto the x-axis is the set \{x \in \mathbb{R} \mid x^3 - x \geq 0\}, equivalent to (-\infty, -1] \cup [0, +\infty), a finite union of semialgebraic basic sets (intervals), thus semialgebraic as guaranteed by the theorem. This illustrates how projections reveal the "discriminant locus" where real fibers exist, maintaining the semialgebraic structure.^[4]

Quantifier Elimination and Cell Decomposition

Tarski's quantifier elimination theorem states that every first-order formula in the theory of real closed fields, built from polynomial inequalities using logical connectives and quantifiers, is equivalent to a quantifier-free formula in the same theory.^[14] This equivalence implies that the solution set of any such quantified formula defines a semialgebraic set, as quantifier-free formulas directly describe unions of basic semialgebraic sets.^[15] As a corollary, the theorem enables the projection of semialgebraic sets to remain semialgebraic, aligning with the Tarski-Seidenberg theorem by iteratively eliminating existential quantifiers one variable at a time.^[14] The proof of quantifier elimination provides effective bounds on the complexity, depending on the number of variables, the degrees of the polynomials, and the number of quantifiers. Specifically, the size of the equivalent quantifier-free formula and the running time of elimination procedures are doubly exponential in the number of variables.^[16] A key consequence of quantifier elimination is the existence of cell decompositions for semialgebraic sets. Every semialgebraic set in \mathbb{R}^n admits a finite partition into cells—such as points, open simplices, or more generally connected components where polynomials have constant sign—such that the partition is compatible with given polynomial maps, meaning the image of each cell under a polynomial is a finite union of cells. Each cell has a specified center (a point satisfying certain sign conditions) and consistent sign patterns for the defining polynomials. Algorithmically, cylindrical algebraic decomposition (CAD) realizes such partitions by recursively decomposing space into cylindrical cells aligned with the variable order, ensuring constant sign for polynomials within each cell and enabling quantifier elimination. Introduced by Collins, CAD constructs these decompositions explicitly, with complexity also doubly exponential in the number of variables, matching the inherent lower bounds from Tarski's theorem.^[16] For example, the formula \exists y \, (y^2 + x y + 1 > 0) eliminates to the quantifier-free condition that holds for all real x, since the quadratic in y is positive for some y everywhere (as its minimum value $1 - x^2/4 is finite and the parabola opens upwards).^[14] This reduction demonstrates how existential quantifiers over polynomials yield inequalities or Boolean combinations thereof in the free variables.

Applications

In Real Algebraic Geometry

Semialgebraic sets play a central role in real algebraic geometry by extending the classical notion of real algebraic varieties, which are defined solely as zero loci of polynomials, to incorporate polynomial inequalities, thereby capturing a broader class of geometrically significant subsets of Euclidean space. While real algebraic varieties focus on solution sets to equations f_1(x) = \cdots = f_k(x) = 0, semialgebraic sets are finite unions of intersections involving both equations and strict or non-strict inequalities, such as \{ x \in \mathbb{R}^n \mid g_i(x) > 0, h_j(x) \geq 0, p_\ell(x) = 0 \}. This generalization allows for the study of open and closed regions, complements, and projections that are essential for understanding the topology and geometry over the reals, where the ordered field structure of \mathbb{R} introduces phenomena absent in complex algebraic geometry.^[17] A key result highlighting the manifold-like behavior of semialgebraic sets is the Nash-Tognoli theorem, which states that every compact smooth manifold is diffeomorphic to a nonsingular real algebraic variety. Since nonsingular real algebraic varieties are a special class of semialgebraic sets, this theorem shows that compact smooth manifolds can be realized as semialgebraic sets. Originally conjectured by Nash in his work on real algebraic manifolds and proved by Tognoli using approximation theorems for smooth functions by polynomials, this theorem underscores the algebraic approximability of smooth geometry over the reals, bridging differential and algebraic perspectives. In the semialgebraic context, it implies that tame subsets of \mathbb{R}^n can model arbitrary compact manifolds up to diffeomorphism, facilitating the embedding of geometric problems into algebraic frameworks.^[18] The theory of semialgebraic sets forms an o-minimal structure on the real field, meaning the definable sets in this structure are precisely the semialgebraic sets, which exhibit tame topological properties such as finite cell decompositions and uniform bounds on the number of connected components. O-minimality ensures that every semialgebraic set in \mathbb{R}^n decomposes into finitely many cells—points, open simplices, or manifolds with boundary—providing bounds like at most s(2d+1)^n cells for sets defined by polynomials of degree at most d with s inequalities, where the topology remains controlled without pathological features like infinite branching. This tameness, established in foundational works on o-minimal expansions, enables effective dimension theory and stratification in real algebraic geometry. Semialgebraic sets relate closely to semianalytic sets, which generalize the construction using convergent power series or real analytic functions instead of polynomials, allowing local descriptions on analytic manifolds; however, semialgebraic sets are globally polynomial-bounded and form a proper subclass, as semianalytic sets can exhibit more intricate local behavior near singularities while sharing finiteness properties like those in Łojasiewicz's theorem on connected components. This distinction highlights the polynomial rigidity of semialgebraic geometry versus the analytic flexibility, with semialgebraic sets converging to semianalytic ones in the category of subanalytic spaces.^[17] An illustrative example of semialgebraic realization in real algebraic geometry is the real spectrum of a commutative ring A, denoted \mathrm{Sper}\, A, which consists of pairs (P, \sigma) where P is a prime ideal and \sigma an ordering on the residue field, equipped with a hull-kernel topology that makes it a spectral space; this abstract object realizes semialgebraic sets via coordinate rings, as the semialgebraic subsets of \mathbb{R}^n correspond to constructible sets in \mathrm{Sper}\, \mathbb{R}[x_1, \dots, x_n], providing a foundational framework for generalizing semialgebraic geometry beyond affine space.^[19]

In Optimization and Control Theory

Semialgebraic sets play a crucial role in optimization by providing certificates for the positivity of polynomials over constrained domains. Schmüdgen's Positivstellensatz establishes that if a polynomial f is strictly positive on a compact basic closed semialgebraic set S = \{x \in \mathbb{R}^n \mid g_i(x) \geq 0, i=1,\dots,m\}, then f can be expressed as a sum of squares (SOS) of polynomials weighted by the generators g_i, specifically f = \sum_{I \subset } s_I \prod_{i \in I} g_i where each s_I is a sum of squares. This representation serves as a computational certificate verifiable via semidefinite programming (SDP). A variant by Putinar relaxes the compactness assumption to an Archimedean condition on the quadratic module generated by the g_i, allowing f > 0 on S to be certified as f = s_0 + \sum_{i=1}^m s_i g_i with SOS polynomials s_0, s_i, which is particularly useful for unbounded or non-basic semialgebraic sets. These Positivstellensätze underpin sum-of-squares hierarchies for solving nonconvex polynomial optimization problems over semialgebraic constraints. The Lasserre hierarchy constructs a sequence of SDP relaxations that approximate the minimum of a polynomial objective subject to semialgebraic inequalities by dualizing moment problems and enforcing SOS conditions on the dual certificates; the k-th level considers monomials up to degree $2k and converges asymptotically to the global optimum under compactness assumptions. For instance, the feasibility of a semialgebraic set defined by \{x \mid p(x) \geq 0, q(x) = 0\} can be checked by solving an SDP relaxation that seeks an SOS certificate of infeasibility, such as a polynomial combination proving a contradiction via the Positivstellensatz. This approach transforms hard combinatorial or global optimization tasks into tractable convex programs, with finite convergence guaranteed in many cases like quadratic objectives. In control theory, semialgebraic sets describe reachable sets for nonlinear polynomial dynamical systems, facilitating stability analysis. For a system \dot{x} = f(x, u) with polynomial f, the reachable set from an initial semialgebraic set over a finite horizon is itself semialgebraic, allowing exact representation via quantifier elimination, though computationally intensive; approximations via SOS methods enable practical verification. Stability can be certified using polynomial Lyapunov functions that are positive definite on semialgebraic invariant sets and whose derivatives are negative thereon, often found via SOS relaxations of the corresponding inequalities, ensuring asymptotic stability for polynomial systems.^[20] For robust control under parametric uncertainty, semialgebraic uncertainty sets are approximated by simpler polyhedral or ellipsoidal sets to enable tractable formulations. Polyhedral outer approximations can be obtained by linearizing the defining polynomials at critical points, while ellipsoidal approximations minimize volume subject to containing the semialgebraic set, often solved via SDP; these reduce robust optimization problems, such as worst-case controller design, to linear or second-order cone programs while preserving feasibility guarantees.