Authors
Citation
F. Maurin, THE THEORY OF INTEGER MULTIPLICATION WITH ORDER RESTRICTED TO PRIMES IS DECIDABLE, The Journal of symbolic logic, 62(1), 1997, pp. 123-130
Citations number
12
Categorie Soggetti
Mathematics, Pure",Mathematics
Journal title
ISSN journal
00224812
Volume
62
Issue
1
Year of publication
1997
Pages
123 - 130
Database
ISI
SICI code
0022-4812(1997)62:1<123:TTOIMW>2.0.ZU;2-1
Abstract
We show here that the first order theory of the positive integers equi
pped with multiplication remains decidable when one adds to the langua
ge the usual order restricted to the prime numbers. We see moreover th
at the complexity of the latter theory is a tower of exponentials, of
height O(n).