Hostname: page-component-78c5997874-t5tsf Total loading time: 0 Render date: 2024-11-19T20:54:06.619Z Has data issue: false hasContentIssue false
  • English
  • Français

THE DIOPHANTINE PROBLEM FOR ADDITION AND DIVISIBILITY OVER SUBRINGS OF THE RATIONALS

Published online by Cambridge University Press:  08 September 2017

LEONIDAS CERDA-ROMERO  and
CARLOS MARTINEZ-RANERO
LEONIDAS CERDA-ROMERO
Affiliation:
DEPARTAMENTO DE MATEMÁTICA UNIVERSIDAD DE CONCEPCIÓN CASILLA 160-C, CONCEPCIÓN CHILE E-mail: [email protected] ESCUELA SUPERIOR POLITÉCNICA DE CHIMBORAZO RIOBAMBA, ECUADOR E-mail: [email protected]
CARLOS MARTINEZ-RANERO
Affiliation:
DEPARTAMENTO DE MATEMÁTICA UNIVERSIDAD DE CONCEPCIÓN CASILLA 160-C, CONCEPCIÓN CHILE E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

It is shown that the positive existential theory of the structure (ℤ[S−1]; =, 0, 1, + , |), where S is a nonempty finite set of prime numbers, is undecidable. This result should be put in contrast with the fact that the positive existential theory of (ℤ; =, 0, 1, + |) is decidable.

Keywords

11U05positive-existential definabilityS-integerssmall rings
Type
Articles
Information
The Journal of Symbolic Logic , Volume 82 , Issue 3 , September 2017 , pp. 1140 - 1149
Copyright
Copyright © The Association for Symbolic Logic 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Bel’tyukov, A. P., Decidability of the universal theory of natural numbers with addition and divisibility . Journal of Soviet Mathematics, vol. 14 (1980), no. 5, pp. 1436–1444.CrossRefGoogle Scholar
Davis, M., Hilbert’s tenth problem is unsolvable . The American Mathematical Monthly, vol. 80 (1973), no. 3, pp. 233–269.CrossRefGoogle Scholar
Denef, J., The diophantine problem for polynomial rings of positive characteristic , Logic Colloquium 78 (Boffa, M., van Dalen, D., and McAloon, K., editors), Elsevier, North-Holland, 1979, pp. 131–154.Google Scholar
Lipshitz, L., Undecidable existential problem for addition and divisibility in algebraic number rings II . Proceedings of the American Mathematical Society, vol. 64 (1977), no. 1, pp. 122–128.CrossRefGoogle Scholar
Lipshitz, L., The diophantine problem for addition and divisibility . Transactions of the American Mathematical Society, vol. 235 (1978), pp. 271–283.CrossRefGoogle Scholar
Lipshitz, L., Undecidable existential problem for addition and divisibility in algebraic number rings . Transactions of the American Mathematical Society, vol. 241 (1978), pp. 121–128.CrossRefGoogle Scholar
Marker, D., Model Theory: An Introduction. Graduate Text in Mathematics, vol. 127, 2002.Google Scholar
Pappalardi, F., On the r-rank Artin conjecture . Mathematics of Computation, vol. 66 (1997), no. 218, pp. 853–868.CrossRefGoogle Scholar
Pheidas, T., The diophantine problem for addition and divisibility in polynomial rings, Thesis, Purdue University, Springer-Verlag, New York, 1985.Google Scholar
Pheidas, T., Undecidability result for power series rings of positive characteristic. II . Proceedings of the American Mathematical Society, vol. 100 (1987), no. 3, pp. 526–530.CrossRefGoogle Scholar
Poonen, B., Hilbert’s tenth problem and Mazur’s conjecture for large subrings of ℚ. Journal of the American Mathematical Society, vol. 16 (2003), no. 4, pp. 981–990.CrossRefGoogle Scholar
Robinson, J., Definability and decision problems in arithmetic, this Journal, vol. 14 (1949), pp. 98–114.Google Scholar
Shlapentokh, A., Defining integers . Bulletin of Symbolic Logic, vol. 17 (2011), no. 2, pp. 230–251.CrossRefGoogle Scholar
Sirokofskich, A., Decidability of sub-theories of polynomials over a finite field , Mathematical Theory and Computational Practice, Lecture Notes in Computer Science, vol. 5635, Springer, Berlin, 2009, pp. 437–446.CrossRefGoogle Scholar