Publisher： Cambridge University Press
E-ISSN： 1943-5886|62|1|123-130
ISSN： 0022-4812
Source： The Journal of Symbolic Logic, Vol.62, Iss.1, 1997-03, pp. : 123-130
Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.
Abstract
We show here that the first order theory of the positive integers equipped with multiplication remains decidable when one adds to the language the usual order restricted to the prime numbers. We see moreover that the complexity of the latter theory is a tower of exponentials, of height
Related content
A complete, decidable theory with two decidable models
The Journal of Symbolic Logic, Vol. 44, Iss. 3, 1979-09 ,pp. :
Access to resources
Recommend
New Results on the Most Significant Bit of Integer Multiplication
By Bollig Beate
Theory of Computing Systems, Vol. 48, Iss. 1, 2011-01 ,pp. :
Decidable fragments of first-order modal logics
The Journal of Symbolic Logic, Vol. 66, Iss. 3, 2001-09 ,pp. :
On countable chains having decidable monadic theory
The Journal of Symbolic Logic, Vol. 77, Iss. 2, 2012-06 ,pp. :
DECIDABILITY AND CLASSIFICATION OF THE THEORY OF INTEGERS WITH PRIMES
The Journal of Symbolic Logic, Vol. 82, Iss. 3, 2017-09 ,pp. :