Hostname: page-component-586b7cd67f-vdxz6 Total loading time: 0 Render date: 2024-11-23T21:22:46.592Z Has data issue: false hasContentIssue false
  • English
  • Français

The theory of integer multiplication with order restricted to primes is decidable

Published online by Cambridge University Press:  12 March 2014

Françoise Maurin
Françoise Maurin*
Affiliation:
G.R.A.L., Mathématiques, Université de Caen, 14 032 Caen Cedex, France
Get access Rights & Permissions [Opens in a new window]

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

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 62 , Issue 1 , March 1997 , pp. 123 - 130
Copyright
Copyright © Association for Symbolic Logic 1997

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

[1]Büchi, J. R., Weak second-order arithmetic and finite automata, Zeitshrift für Math. Log. und Grundl. der Math., vol. 6 (1960), pp. 66–92.CrossRefGoogle Scholar
[2]Büchi, J. R., Transfinite automata recursions and weak second-order theory of ordinals, Notices of the American Mathematical Society, vol. 12 (1965), pp. 371–457.Google Scholar
[3]Cegielski, P., Matiyasevitch, Y., and Richard, D., Definability and decidability issues in extensions of the integers with the divisibility predicate, à paraître.Google Scholar
[4]Compton, K. J. and Henson, C. W., A uniform method for proving lower bounds on the computational complexity of logical theories, Annals of Pure and Applied Logic, vol. 48 (1990), pp. 1–79.CrossRefGoogle Scholar
[5]Feferman, S. and Vaught, R. L., The first order properties of products of algebraic systems, Fundamenta Mathematicae, vol. XLVII (1959), pp. 57–103.CrossRefGoogle Scholar
[6]Ferrante, J. and Rackoff, C., A decision procedure for the first order theory of real addition with order, SIAM Journal of Computation, vol. 4 (1975), pp. 69–76.CrossRefGoogle Scholar
[7]Ferrante, J. and Rackoff, C., The computational complexity of logical theories, Lecture Notes in Mathematics, vol. 718, Springer-Verlag, Berlin, 1979.CrossRefGoogle Scholar
[8]Fisher, M. and Rabin, M., Superexponential complexity of Presburger arithmetic, SIAM Proceedings, vol. 7 (1974), pp. 27–41.Google Scholar
[9]Maurin, F., Ehrenfeucht gantes and ordinal addition, preprint, 1994.Google Scholar
[10]Maurin, F., Exact complexity bounds for ordinal addition, preprint, 1995.CrossRefGoogle Scholar
[11]Meyer, A. R., Weak monadic second order theory of successor is not elementary-recursive, Boston Univ. Logic Colloquium Proc, Springer-Verlag, 1975, pp. 132–154.CrossRefGoogle Scholar
[12]Robinson, J., Definability and decision problems in arithmetic, this Journal, vol. 14 (1949), pp. 98–114.Google Scholar