Nonnegative solvability of linear equations in certain ordered rings

Scowcroft, Philip

doi:10.1090/S0002-9947-06-03978-X

Nonnegative solvability of linear equations in certain ordered rings
HTML articles powered by AMS MathViewer

by Philip Scowcroft PDF

Trans. Amer. Math. Soc. 358 (2006), 3535-3570 Request permission

Abstract:

In the integers and in certain densely ordered rings that are not fields, projections of the solution set of finitely many homogeneous weak linear inequalities may be defined by finitely many congruence inequalities, where a congruence inequality combines a weak inequality with a system of congruences. These results extend well-known facts about systems of weak linear inequalities over ordered fields and imply corresponding analogues of Farkas’ Lemma on nonnegative solvability of systems of linear equations.

References

C. C. Chang and H. J. Keisler, Model theory, Studies in Logic and the Foundations of Mathematics, Vol. 73, North-Holland Publishing Co., Amsterdam-London; American Elsevier Publishing Co., Inc., New York, 1973. MR 0409165
George B. Dantzig, Linear programming and extensions, Reprint of the 1968 corrected edition, Princeton Landmarks in Mathematics, Princeton University Press, Princeton, NJ, 1998. MR 1658673
Lou van den Dries, Some applications of a model theoretic fact to (semi-) algebraic geometry, Nederl. Akad. Wetensch. Indag. Math. 44 (1982), no. 4, 397–401. MR 683527, DOI 10.1016/1385-7258(82)90033-6
J. Farkas, Theorie der einfachen Ungleichungen, J. Reine Angew. Math. $\mathbf {124}$ (1902), 1–27.
Robert W. Gilmer, Multiplicative ideal theory, Queen’s Papers in Pure and Applied Mathematics, No. 12, Queen’s University, Kingston, Ont., 1968. MR 0229624
J. H. Grace and A. Young, The algebra of invariants, University Press, Cambridge, 1903.
Philipp Rothmaler, Some model theory of modules. II. On stability and categoricity of flat modules, J. Symbolic Logic 48 (1983), no. 4, 970–985 (1984). MR 727787, DOI 10.2307/2273662
Volker Weispfenning, Elimination of quantifiers for certain ordered and lattice-ordered abelian groups, Bull. Soc. Math. Belg. Sér. B 33 (1981), no. 1, 131–155. MR 620968
Volker Weispfenning, Model theory of abelian $l$-groups, Lattice-ordered groups, Math. Appl., vol. 48, Kluwer Acad. Publ., Dordrecht, 1989, pp. 41–79. MR 1036073
V. Weispfenning, Existential equivalence of ordered abelian groups with parameters, Arch. Math. Logic 29 (1990), no. 4, 237–248. MR 1062728, DOI 10.1007/BF01651327
H. Weyl, The elementary theory of convex polyhedra, Contributions to the Theory of Games, Annals of Mathematics Studies, no. 24, Princeton University Press, Princeton, N.J., 1950, pp. 3–18. MR 0038088