The Theory of Integer Multiplication with Order Restricted to Primes is Decidable

Maurin, Francoise

J. Symbolic Logic, Tome 62 (1997) no. 1, p. 123-130 / Harvested from Project Euclid

Résumé

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 $O(n)$.

Publié le : 1997-03-14
Classification:

@article{1183745188,
     author = {Maurin, Francoise},
     title = {The Theory of Integer Multiplication with Order Restricted to Primes is Decidable},
     journal = {J. Symbolic Logic},
     volume = {62},
     number = {1},
     year = {1997},
     pages = { 123-130},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183745188}
}

Maurin, Francoise. The Theory of Integer Multiplication with Order Restricted to Primes is Decidable. J. Symbolic Logic, Tome 62 (1997) no. 1, pp.  123-130. http://gdmltest.u-ga.fr/item/1183745188/