{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,12]],"date-time":"2024-08-12T18:35:34Z","timestamp":1723487734681},"reference-count":28,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":7589,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1993,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>It is shown, assuming the linear case of Schinzel's Hypothesis, that the first-order theory of the structure \u3008\u03c9; +, <jats:italic>P<\/jats:italic>\u3009, where <jats:italic>P<\/jats:italic> 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 \u3008\u03c9 <jats:italic>S<\/jats:italic>, <jats:italic>P<\/jats:italic>\u3009 is decidable, where <jats:italic>S<\/jats:italic> is the successor function. The latter result is proved using a general result of A. L. Sem\u00ebnov on decidability of monadic theories, and a proof of Sem\u00ebnov's result is presented.<\/jats:p>","DOI":"10.2307\/2275227","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T22:48:26Z","timestamp":1146955706000},"page":"672-687","source":"Crossref","is-referenced-by-count":9,"title":["Decidability and undecidability of theories with a predicate for the primes"],"prefix":"10.1017","volume":"58","author":[{"given":"P. T.","family":"Bateman","sequence":"first","affiliation":[]},{"given":"C. G.","family":"Jockusch","sequence":"additional","affiliation":[]},{"given":"A. R.","family":"Woods","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S002248120002140X_ref009","volume-title":"Sieve methods","author":"Halberstam","year":"1974"},{"key":"S002248120002140X_ref005","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80051-6"},{"key":"S002248120002140X_ref025","doi-asserted-by":"publisher","DOI":"10.1007\/BF01351676"},{"key":"S002248120002140X_ref001","doi-asserted-by":"publisher","DOI":"10.1007\/BF01979646"},{"key":"S002248120002140X_ref026","first-page":"334","volume":"45","author":"Thomas","year":"1980","journal-title":"On the bounded monadic theory of well-ordered structures"},{"key":"S002248120002140X_ref021","first-page":"401","volume":"15","author":"Sem\u00ebnov","year":"1980","journal-title":"On certain extensions of the arithmetic of addition of natural numbers, Mathematics of the USSR\u2014Izvestiya"},{"key":"S002248120002140X_ref004","first-page":"166","volume":"34","author":"B\u00fcchi","year":"1969","journal-title":"Definability in the monadic second-order theory of successor"},{"key":"S002248120002140X_ref013","doi-asserted-by":"publisher","DOI":"10.1109\/SWCT.1963.8"},{"key":"S002248120002140X_ref007","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1961-0139530-9"},{"key":"S002248120002140X_ref019","doi-asserted-by":"publisher","DOI":"10.4064\/aa-7-1-1-8"},{"key":"S002248120002140X_ref017","doi-asserted-by":"publisher","DOI":"10.1090\/cbms\/013"},{"key":"S002248120002140X_ref020","doi-asserted-by":"publisher","DOI":"10.1007\/BF01448914"},{"key":"S002248120002140X_ref008","first-page":"169","volume":"31","author":"Elgot","year":"1966","journal-title":"Decidability and undecidability of second (first) order theory of (generalized) successor"},{"key":"S002248120002140X_ref022","first-page":"623","article-title":"Logical theories of one-place functions on the set of natural numbers","volume":"47","author":"Sem\u00ebnov","year":"1983","journal-title":"Izvestiya Akademii Nauk SSSR Seriya Mathematicheskaya"},{"key":"S002248120002140X_ref016","first-page":"1","article-title":"Decidability of second-order theories and automata on infinite trees","volume":"141","author":"Rabin","year":"1969","journal-title":"Transactions of the American Mathematical Society"},{"key":"S002248120002140X_ref002","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19600060105"},{"key":"S002248120002140X_ref006","first-page":"155","article-title":"A new extension of Dirichlet's theorem on prime numbers","volume":"33","author":"Dickson","year":"1904","journal-title":"Messenger of Mathematics"},{"key":"S002248120002140X_ref024","first-page":"441","article-title":"Decidable extensions of monadic second order successor arithmetic","volume":"3","author":"Siefkes","year":"1970","journal-title":"Automaten-theorie und formate Sprachen"},{"key":"S002248120002140X_ref023","first-page":"162","volume-title":"Decidability of monadic theories","volume":"176","author":"Sem\u00ebnov","year":"1984"},{"key":"S002248120002140X_ref028","unstructured":"[W] Woods A. R. , Some problems in logic and number theory, and their connections, Ph.D. thesis , University of Manchester, Manchester, 1981."},{"key":"S002248120002140X_ref027","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(81)90663-X"},{"key":"S002248120002140X_ref015","first-page":"39","volume":"22","author":"Putman","year":"1957","journal-title":"Decidability and essential undecidability"},{"key":"S002248120002140X_ref003","first-page":"1","volume-title":"Logic, Methodology, and Philosophy of Science, Proceedings of the 1960 Congress","author":"B\u00fcchi"},{"key":"S002248120002140X_ref018","doi-asserted-by":"crossref","first-page":"185","DOI":"10.4064\/aa-4-3-185-208","article-title":"Sur certaines hypoth\u00e8ses concernant les nomhres premiers","volume":"4","author":"Schinzel","year":"1958","journal-title":"Acta Arithmetica"},{"key":"S002248120002140X_ref012","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(66)80013-X"},{"key":"S002248120002140X_ref011","unstructured":"[Mc1] McNaughton R. , review of [B1], this Journal, vol. 28 (1963), pp. 100\u2013102."},{"key":"S002248120002140X_ref010","volume-title":"Introduction to automata theory, languages, and computation","author":"Hopcroft","year":"1979"},{"key":"S002248120002140X_ref014","first-page":"92","volume-title":"Comptes Rendus du Ier Congr\u00e8s des Math\u00e9maticiens des Pays Slaves","author":"Presburger","year":"1929"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S002248120002140X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T22:56:21Z","timestamp":1557960981000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S002248120002140X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,6]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1993,6]]}},"alternative-id":["S002248120002140X"],"URL":"https:\/\/doi.org\/10.2307\/2275227","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,6]]}}}