Decidable sentences over polynomial rings
HTML articles powered by AMS MathViewer
- by Shih Ping Tung
- Proc. Amer. Math. Soc. 102 (1988), 383-388
- DOI: https://doi.org/10.1090/S0002-9939-1988-0921004-0
- PDF | Request permission
Abstract:
Let $R$ be an algebraic number field or an algebraic integer ring. We prove that there is an algorithm to determine whether the sentence $\forall x\exists y\phi \left ( {x,y} \right )$, with $\phi \left ( {x,y} \right )$ a quantifier free formula over $R\left [ T \right ]$, is true in the polynomial ring $R\left [ T \right ]$ or not.References
- J. Denef, Hilbert’s tenth problem for quadratic rings, Proc. Amer. Math. Soc. 48 (1975), 214–220. MR 360513, DOI 10.1090/S0002-9939-1975-0360513-3
- J. Denef, The Diophantine problem for polynomial rings and fields of rational functions, Trans. Amer. Math. Soc. 242 (1978), 391–399. MR 0491583, DOI 10.1090/S0002-9947-1978-0491583-7
- J. Denef, Diophantine sets over algebraic integer rings. II, Trans. Amer. Math. Soc. 257 (1980), no. 1, 227–236. MR 549163, DOI 10.1090/S0002-9947-1980-0549163-X
- J. Denef and L. Lipshitz, Diophantine sets over some rings of algebraic integers, J. London Math. Soc. (2) 18 (1978), no. 3, 385–391. MR 518221, DOI 10.1112/jlms/s2-18.3.385
- Susan Landau, Factoring polynomials over algebraic number fields, SIAM J. Comput. 14 (1985), no. 1, 184–195. MR 774938, DOI 10.1137/0214015
- Henry B. Mann, Introduction to algebraic number theory, Ohio State University Press, Columbus, Ohio, 1955. With a chapter by Marshall Hall, Jr. MR 0072174
- Raphael M. Robinson, Undecidable rings, Trans. Amer. Math. Soc. 70 (1951), 137–159. MR 41081, DOI 10.1090/S0002-9947-1951-0041081-0
- Raphael M. Robinson, Arithmetical definitions in the ring of integers, Proc. Amer. Math. Soc. 2 (1951), 279–284. MR 41080, DOI 10.1090/S0002-9939-1951-0041080-4
- Andrzej Schinzel, Selected topics on polynomials, University of Michigan Press, Ann Arbor, Mich., 1982. MR 649775
- Shih Ping Tung, Provability and decidability of arithmetical universal-existential sentences, Bull. London Math. Soc. 18 (1986), no. 3, 241–247. MR 829580, DOI 10.1112/blms/18.3.241 —, Complexity of sentences over number rings, preprint.
Similar Articles
- Retrieve articles in Proceedings of the American Mathematical Society with MSC: 03B25,, 03C60,12L05
- Retrieve articles in all journals with MSC: 03B25,, 03C60,12L05
Bibliographic Information
- © Copyright 1988 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 102 (1988), 383-388
- MSC: Primary 03B25,; Secondary 03C60,12L05
- DOI: https://doi.org/10.1090/S0002-9939-1988-0921004-0
- MathSciNet review: 921004