Decidability and undecidability of theories with a predicate for the primes. (English) Zbl 0785.03002

Bateman, P. T.; Jockusch, C. G.; Woods, A. R.

J. Symb. Log. 58, No. 2, 672-687 (1993).

Summary: It is shown, assuming the linear case of Schinzel’s hypothesis, that the first-order theory of the structure \(\langle \omega;+,P\rangle\), 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 \(\langle \omega;S,P\rangle\) 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.

MSC:

03B25	Decidability of theories and sets of sentences
11U05	Decidability (number-theoretic aspects)

Keywords:

linear case of Schinzel’s hypothesis; primes; multiplication of natural numbers; monadic second-order theory; successor function; decidability

References:

[1]	Izvestiya Akademii Nauk SSSR Seriya Mathematicheskaya 47 pp 623– (1983)
[2]	Decidability of monadic theories 176 pp 162– (1984)
[3]	DOI: 10.1007/BF01448914 · Zbl 0006.10402
[4]	Sieve methods (1974)
[5]	Decidability and undecidability of second (first) order theory of (generalized) successor 31 pp 169– (1966)
[6]	DOI: 10.1090/S0002-9947-1961-0139530-9
[7]	Messenger of Mathematics 33 pp 155– (1904)
[8]	DOI: 10.1016/S0022-0000(74)80051-6 · Zbl 0292.02033
[9]	Definability in the monadic second-order theory of successor 34 pp 166– (1969) · Zbl 0209.02203
[10]	Logic, Methodology, and Philosophy of Science, Proceedings of the 1960 Congress pp 1–
[11]	DOI: 10.1002/malq.19600060105 · Zbl 0103.24705
[12]	DOI: 10.1007/BF01979647 · Zbl 0534.03020
[13]	Acta Arithmetica 7 pp 1– (1961)
[14]	Acta Arithmetica 4 pp 185– (1958)
[15]	Automata on infinite objects and Church’s problem (1972) · Zbl 0315.02037
[16]	Transactions of the American Mathematical Society 141 pp 1– (1969)
[17]	Decidability and essential undecidability 22 pp 39– (1957)
[18]	Comptes Rendus du Ier Congrès des Mathématiciens des Pays Slaves pp 92– (1929)
[19]	Switching circuit theory and logical design: proceedings of the fourth annual symposium pp 3– (1963)
[20]	DOI: 10.1016/S0019-9958(66)80013-X · Zbl 0212.33902
[21]	Introduction to automata theory, languages, and computation (1979) · Zbl 0426.68001
[22]	DOI: 10.1016/S0019-9958(81)90663-X · Zbl 0478.03020
[23]	On the bounded monadic theory of well-ordered structures 45 pp 334– (1980) · Zbl 0437.03005
[24]	DOI: 10.1007/BF01351676 · Zbl 0369.02025
[25]	Automaten-theorie und formate Sprachen 3 pp 441– (1970)
[26]	On certain extensions of the arithmetic of addition of natural numbers, Mathematics of the USSR–Izvestiya 15 pp 401– (1980)