A representation of convex semilinear sets (Q987186)

Let \(F\) be an ordered field, \(n\) a positive integer. A subset of \(F^n\) is called \(F\)-semilinear if it is a finite Boolean combination of translates of closed subspaces, that is, subsets of the form \(\{x \in F^n \, : \, \sum_{i=1}^n a_i x_i \geq b \}\) with the \(a_i\) and \(b\) in \(F\). Andradas, Rubio and Vélez showed that closed (open) convex semilinear sets of \(F^n\) are finite intersections of translates of closed (open) halfspaces. However, there exist convex \(F\)-semilinear subsets that are neither closed nor open. The paper under review provides a simple and nice representation of arbitrary convex \(F\)-semilinear sets, referring to the ordered field \(F(\theta)\) with \(\theta\) a positive infinitesimal. In fact, it is shown that the convex \(F\)-semilinear subsets \(S\) of \(F^n\) are just the intersections with \(F^n\) of the closed convex \(F(\theta)\)-semilinear subsets of \(F(\theta)^n\), hence the finite intersections of sets of the form \(\{ x \in F^n \, : \, \sum_{i=1}^n a_i(\theta) x_i \geq b(\theta) \}\), where the \(a_i(\theta)\) and \(b(\theta)\) come from \(F[\theta]\). A sharp bound of \(n\) on the degrees of the \(a_i(\theta)\) and \(b(\theta)\) is also provided. In particular, it turns out that the bounded convex \(F\)-semilinear sets of \(F^n\) are exactly the intersections with \(F^n\) of the convex hulls in \(F(\theta)^n\) of finitely many points of \(F[\theta]^n\). The author also examines the intersections with \(F^n\) of subsets of \(F[\theta]^n\) definable in a more complex way, involving arbitrary connectives and quantifiers. Here \(F[\theta]^n\) is viewed as an ordered module over itself. A suitable language \(C\) is introduced to support this approach. Basically, \(C\) expands the usual language of ordered \(F[\theta]\)-modules by a binary relation \(\leq_a\) for every \(a \in F[\theta]\) (to be interpreted by the relation \[ x \leq_a y \quad \Leftrightarrow \quad \exists x \, (x \leq az \leq y)). \] The author analyzes in this setting first the structure of projections of finite intersections of solution sets of weak inequalities, and then arbitrary definable sets. A more expressive two-sorted language is also considered, with a valuation assigning to every non-zero \(a \in F[\theta]\) the greatest natural number \(k\) such that \(\theta^k\) divides \(a\) (and \(\infty\) to \(0\)). All these results are compared with earlier quantifier elimination theorems for abelian groups and modules.