×

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

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)
PDFBibTeX XMLCite
Full Text: DOI

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 · doi:10.1007/BF01448914
[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 · 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 · doi:10.1016/S0022-0000(74)80051-6
[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 · doi:10.1002/malq.19600060105
[12] DOI: 10.1007/BF01979647 · Zbl 0534.03020 · doi:10.1007/BF01979647
[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 · doi:10.1016/S0019-9958(66)80013-X
[21] Introduction to automata theory, languages, and computation (1979) · Zbl 0426.68001
[22] DOI: 10.1016/S0019-9958(81)90663-X · Zbl 0478.03020 · doi:10.1016/S0019-9958(81)90663-X
[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 · doi:10.1007/BF01351676
[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)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.