Abstract
If F is an ordered field, a subset of n-space over F is said to be semilinear just in case it is a finite Boolean combination of translates of closed halfspaces, where a closed halfspace is the set of all points obeying a homogeneous weak linear inequality with coefficients from F. Andradas, Rubio, and Vélez have shown that closed (open) convex semilinear sets are finite intersections of translates of closed (open) halfspaces (an open halfspace is defined as before, but with a strict inequality). This paper represents arbitrary convex semilinear sets in a manner analogous to that of Andradas, Rubio, and Vélez.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Andradas, C., Rubio, R., Vélez, M.P.: An algorithm for convexity of semilinear sets over ordered fields. Real Algebraic and Analytic Geometry Preprint Server, No. 12, submitted 1/31/06
Conrad P.: Embedding theorems for Abelian groups with valuations. Amer. J. Math. 75, 1–29 (1953)
Eaves B.C., Rothblum U.G.: Dines-Fourier-Motzkin quantifier elimination and an application of corresponding transfer principles over ordered fields. Math. Programming 53, 307–321 (1992)
Gantmacher F.R.: The theory of matrices (vol. 1). Transl. by K.A. Hirsch. Chelsea Publishing Co., New York (1977)
Hodges W.: Model theory. Encylopedia of Mathematics and its Applications No. 42. Cambridge University Press, Cambridge (1993)
Knight J., Pillay A., Steinhorn C.: Definable sets in ordered structures. II. Trans. Amer. Math. Soc. 295, 593–605 (1986)
Robinson R.: Undecidable rings. Trans. Amer. Math. Soc. 70, 137–159 (1951)
Scowcroft P.: A note on definable Skolem functions. J. Symbolic Logic 53, 905–911 (1988)
Scowcroft P.: Nonnegative solvability of linear equations in certain ordered rings. Trans. Amer. Math. Soc. 358, 3535–3570 (2006)
Scowcroft, P.: Nonnegative solvability of linear equations in ordered Abelian groups. In: Z. Chatzidakis, D. Macpherson, A. Pillay, and A. Wilkie, eds., Model Theory with Applications to Algebra and Analysis, Vol. 2, pp. 273–313. LMS Lecture Note Series No. 350, Cambridge University Press, Cambridge (2008)
Scowcroft P.: Generalized halfspaces in dimension groups. Ann. Pure Appl. Logic 154, 8–26 (2008)
Stoer, J., Witzgall, C.: Convexity and Optimization in Finite Dimensions I. Grundlehren der mathematischen Wissenschaften Bd. 163, Springer-Verlag, Berlin (1970)
Weispfenning V.: Elimination of quantifiers for certain ordered and lattice-ordered Abelian groups. Bull. Soc. Math. Belg. Sér. B. 33, 131–155 (1981)
Weispfenning V.: The complexity of linear problems in fields. J. Symbolic Computation 5, 3–27 (1988)
Author information
Authors and Affiliations
Corresponding author
Additional information
Presented by J. Martinez.
In memory of Paul F. Conrad
Rights and permissions
About this article
Cite this article
Scowcroft, P. A representation of convex semilinear sets. Algebra Univers. 62, 289–327 (2009). https://doi.org/10.1007/s00012-010-0056-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00012-010-0056-5