Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-05T14:28:12.686Z Has data issue: false hasContentIssue false
  • English
  • Français

Decidability and undecidability of theories with a predicate for the primes

Published online by Cambridge University Press:  12 March 2014

P. T. Bateman ,
C. G. Jockusch  and
A. R. Woods
P. T. Bateman
Affiliation:
Department of Mathematics, University of Illinois, Urbana, Illinois61801, E-mail: [email protected]
C. G. Jockusch
Affiliation:
Department of Mathematics, University of Illinois, Urbana, Illinois61801, E-mail: [email protected]
A. R. Woods
Affiliation:
Department of Mathematics, University of Western Australia, Nedlands, Western Australia 6009, Australia, E-mail: woods%[email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

It is shown, assuming the linear case of Schinzel's Hypothesis, that the first-order theory of the structure 〈ω; +, P〉, where P is the set of primes, is undecidable and, in fact, that multiplication of natural numbers is first-order definable in this structure. In the other direction, it is shown, from the same hypothesis, that the monadic second-order theory of 〈ω S, P〉 is decidable, where S is the successor function. The latter result is proved using a general result of A. L. Semënov on decidability of monadic theories, and a proof of Semënov's result is presented.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 58 , Issue 2 , June 1993 , pp. 672 - 687
Copyright
Copyright © Association for Symbolic Logic 1993

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

[BM] Belyakov, É. B. and Mart'yanov, V. I., Universal theories of integers and the extended Bliznetsov hypothesis, Algebra i Logika, vol. 22 (1983), pp. 26–34; English translation, Algebra and Logik, vol. 22 (1983), pp. 19–26.Google Scholar
[B1] Büchi, J. R., Weak second-order arithmetic and finite automata, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 6 (1960), pp. 66–92.CrossRefGoogle Scholar
[B2] Büchi, J. R., On a decision method in restricted second order arithmetic, Logic, Methodology, and Philosophy of Science, Proceedings of the 1960 Congress, Stanford University Press, Stanford, California, pp. 1–11.Google Scholar
[BL] Büchi, J. R. and Landweber, L., Definability in the monadic second-order theory of successor, this Journal, vol. 34 (1969), pp. 166–170.Google Scholar
[C] Choueka, Y., Theories of automata on ω-tapes: a simplified approach, Journal of Computer and System Sciences, vol. 8 (1974), pp. 117–141.CrossRefGoogle Scholar
[D] Dickson, L. E., A new extension of Dirichlet's theorem on prime numbers, Messenger of Mathematics, vol. 33 (1903–1904), pp. 155–161.Google Scholar
[E] Elgot, C. C., Decision problems of finite automata design and related arithmetics, Transactions of the American Mathematical Society, vol. 98 (1961), pp. 21–51.CrossRefGoogle Scholar
[ER] Elgot, C. C. and Rabin, M. O., Decidability and undecidability of second (first) order theory of (generalized) successor, this Journal, vol. 31 (1966), pp. 169–181.Google Scholar
[HR] Halberstam, H. and Richert, H. E., Sieve methods, Academic Press, Orlando, Florida, 1974.Google Scholar
[HU] Hopcroft, J. E. and Ullman, J. D., Introduction to automata theory, languages, and computation, Addison-Wesley, Reading, Massachusetts, 1979.Google Scholar
[Mc1] McNaughton, R., review of [B1], this Journal, vol. 28 (1963), pp. 100–102.Google Scholar
[Mc2] McNaughton, R., Testing and generating infinite sequences by a finite automaton, Information and Control, vol. 9 (1966), pp. 521–530.CrossRefGoogle Scholar
[Mu] Muller, D. E., Infinite sequences and finite machines, Switching circuit theory and logical design: proceedings of the fourth annual symposium, Institute of Electrical and Electronic Engineers, New York, 1963, pp. 3–16.Google Scholar
[Pr] Presburger, M., Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt, Comptes Rendus du Ier Congrès des Mathématiciens des Pays Slaves, Warszawa, 1929. pp. 92–101.Google Scholar
[Pu] Putman, H., Decidability and essential undecidability, this Journal, vol. 22 (1957), pp. 39–54.Google Scholar
[R1] Rabin, M. O., Decidability of second-order theories and automata on infinite trees, Transactions of the American Mathematical Society, vol. 141 (1969), pp. 1–35.Google Scholar
[R2] Rabin, M. O., Automata on infinite objects and Church's problem, Conference Board of the Mathematical Sciences Regional Conference Series in Mathematics, No. 13, American Mathematical Society, Providence, Rhode Island, 1972.CrossRefGoogle Scholar
[SS] Schinzel, A. and Sierpinski, W., Sur certaines hypothèses concernant les nomhres premiers, Acta Arithmetica, vol. 4 (1958), pp. 185–208 (see also ibid 5 (1959), p. 259 for a correction).CrossRefGoogle Scholar
[Schi] Schinzel, A., Remarks on the paper, “Sur certaines hypothèses concernant les nombres premiers”, Acta Arithmetica, vol. 7 (1961), pp. 1–8.CrossRefGoogle Scholar
[Schn] Schnirelmann, L., Über additive Eigenschaften von Zahlen, Mathematische Annalen, vol. 107 (1933), pp. 649–690.CrossRefGoogle Scholar
[Se1] Semënov, A. L., On certain extensions of the arithmetic of addition of natural numbers, Mathematics of the USSR—Izvestiya, vol. 15 (1980), pp. 401–419.Google Scholar
[Se2] Semënov, A. L., Logical theories of one-place functions on the set of natural numbers, Izvestiya Akademii Nauk SSSR Seriya Mathematicheskaya, vol. 47 (1983), pp. 623–658; English translation, Mathematics of the USSR—Izvestiya, vol. 22 (1984), pp. 587–618.Google Scholar
[Se3] Semënov, A. L., Decidability of monadic theories, Springer Lecture Notes in Computer Science, vol. 176, Springer-Verlag, Berlin, 1984, pp. 162–175.Google Scholar
[Si] Siefkes, D., Decidable extensions of monadic second order successor arithmetic, Automaten-theorie und formate Sprachen (Dörr, J. and Hotz, G., editors), Berichte aus dem mathematischen Forschungsinstitut Oberwolfach, vol. 3 (1970), pp. 441–472.Google Scholar
[T1] Thomas, W., The theory of successor with an extra predicate, Mathematische Annalen, vol. 237 (1978), pp. 121–132.CrossRefGoogle Scholar
[T2] Thomas, W., On the bounded monadic theory of well-ordered structures, this Journal, vol. 45 (1980), pp. 334–338.Google Scholar
[T3] Thomas, W., A combinatorial approach to the theory of ω-automata, Information and Control, vol. 48 (1981), pp. 261–283.CrossRefGoogle Scholar
[W] Woods, A. R., Some problems in logic and number theory, and their connections, Ph.D. thesis, University of Manchester, Manchester, 1981.Google Scholar