{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T13:32:49Z","timestamp":1773149569320,"version":"3.50.1"},"reference-count":27,"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":13068,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1978,6]]},"abstract":"<jats:p>In his celebrated paper of 1931 [7], Kurt G\u00f6del proved the existence of sentences undecidable in the axiomatized theory of numbers. G\u00f6del's proof is constructive and such a sentence may actually be written out. Of course, if we follow G\u00f6del's original procedure the formula will be of enormous length.<\/jats:p><jats:p>Forty-five years have passed since the appearance of G\u00f6del's pioneering work. During this time enormous progress has been made in mathematical logic and recursive function theory. Many different mathematical problems have been proved recursively unsolvable. Theoretically each such result is capable of producing an explicit undecidable number theoretic predicate. We have only to carry out a suitable arithmetization. Until recently, however, techniques were not available for carrying out these arithmetizations with sufficient efficiency.<\/jats:p><jats:p>In this article we construct an explicit undecidable arithmetical formula,<jats:italic>F(x, n)<\/jats:italic>, in prenex normal form. The formula is explicit in the sense that it is written out in its entirety with no abbreviations. The formula is undecidable in the recursive sense that there exists no algorithm to decide, for given values of<jats:italic>n<\/jats:italic>, whether or not<jats:italic>F(n, n)<\/jats:italic>is true or false. Moreover<jats:italic>F(n, n)<\/jats:italic>is undecidable in the formal (axiomatic) sense of G\u00f6del [7]. Given any of the usual axiomatic theories to which G\u00f6del's Incompleteness Theorem applies, there exists a value of<jats:italic>n<\/jats:italic>such that<jats:italic>F(n, n)<\/jats:italic>is unprovable and irrefutable. Thus G\u00f6del's Incompleteness Theorem can be \u201cfocused\u201d into the formula<jats:italic>F(n, n)<\/jats:italic>. Thus some substitution instance of<jats:italic>F(n, n)<\/jats:italic>is undecidable in Peano arithmetic, ZF set theory, etc.<\/jats:p>","DOI":"10.2307\/2272832","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T21:47:35Z","timestamp":1146952055000},"page":"335-351","source":"Crossref","is-referenced-by-count":8,"title":["Three universal representations of recursively enumerable sets"],"prefix":"10.1017","volume":"43","author":[{"given":"James P.","family":"Jones","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200049689_ref027","volume-title":"Diophantische Gleichungen","author":"Skolem","year":"1938"},{"key":"S0022481200049689_ref026","first-page":"21","volume-title":"Nachrichten der Akademie Wissenschaften in G\u00f6ttingen. II. Mathematische-Physikalische Klasse","author":"Siegel","year":"1972"},{"key":"S0022481200049689_ref025","first-page":"572","volume":"37","author":"Robinson","year":"1972","journal-title":"Some representations of Diophantine sets"},{"key":"S0022481200049689_ref023","doi-asserted-by":"publisher","DOI":"10.1090\/pspum\/020\/0316234"},{"key":"S0022481200049689_ref022","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1952-0048374-2"},{"key":"S0022481200049689_ref017","first-page":"77","article-title":"Arithmetical representation of enumerable sets with a small number of quantifiers","volume":"32","author":"Matijasevi\u010d","year":"1972","journal-title":"Zapiski Nau\u010dnyh Seminarov Leningradskogo Otdelenija Matemati\u010deskogo Instituta im. V. A. Steklova Akademii Nauk SSSR"},{"key":"S0022481200049689_ref018","first-page":"112","volume-title":"Theory of algorithms and mathematical logic","author":"Matijasevi\u010d","year":"1974"},{"key":"S0022481200049689_ref016","first-page":"185","article-title":"Diophantine sets","volume":"27","author":"Matijasevi\u010d","year":"1972","journal-title":"Uspehi Matemati\u010deskih Nauk"},{"key":"S0022481200049689_ref013","first-page":"49","article-title":"On Diophantine representation of the sequence of solutions of Pell's equation","volume":"20","author":"Kosovski\u012d","year":"1971","journal-title":"Zapiski Nau\u010dnyh Seminarov Leningradskogo Otdelenija Matemati\u010deskogo Instituta im. V. A. Steklova Akademii Nauk SSSR"},{"key":"S0022481200049689_ref010","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1080\/00150517.1976.12430566","article-title":"Diophantine representation of the Lucas numbers","volume":"14","author":"Jones","year":"1976","journal-title":"Fibonacci Quarterly"},{"key":"S0022481200049689_ref006","first-page":"323","volume-title":"Proceedings of the Conference on the Hilbert Problems, Dekalb, Illinois, May 1974","author":"Davis","year":"1976"},{"key":"S0022481200049689_ref005","doi-asserted-by":"publisher","DOI":"10.2307\/1970289"},{"key":"S0022481200049689_ref002","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1973.11993265"},{"key":"S0022481200049689_ref001","first-page":"185","article-title":"Diophantine predicates","volume":"25","author":"\u010cudnovski\u00ef","year":"1970","journal-title":"Uspehi Matemati\u010deskih Nauk"},{"key":"S0022481200049689_ref015","first-page":"3","article-title":"Diophantine representation of enumerable predicates","volume":"35","author":"Matijasevi\u010d","year":"1971","journal-title":"lzvestija Akademii Nauk SSSR, Serija Matematika"},{"key":"S0022481200049689_ref011","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1976.11994142"},{"key":"S0022481200049689_ref020","doi-asserted-by":"publisher","DOI":"10.4064\/aa-27-1-521-553"},{"key":"S0022481200049689_ref019","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(09)70352-0"},{"key":"S0022481200049689_ref024","first-page":"162","volume":"21","author":"Robinson","year":"1956","journal-title":"Arithmetical representation of recursively enumerable sets"},{"key":"S0022481200049689_ref004","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.3160240205"},{"key":"S0022481200049689_ref003","volume-title":"Computability and unsolvabittty","author":"Davis","year":"1958"},{"key":"S0022481200049689_ref012","volume-title":"Acta Arithmetica","author":"Jones"},{"key":"S0022481200049689_ref007","doi-asserted-by":"publisher","DOI":"10.1007\/BF01700692"},{"key":"S0022481200049689_ref014","first-page":"279","article-title":"Enumerable sets are Diophantine","volume":"191","author":"Matijasevi\u010d","year":"1970","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"S0022481200049689_ref009","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1080\/00150517.1975.12430693","article-title":"Diophantine representation of the Fibonacci numbers","volume":"13","author":"Jones","year":"1975","journal-title":"Fibonacci Quarterly"},{"key":"S0022481200049689_ref008","first-page":"253","volume-title":"Vortrag, gehalten auf dem intemationalen Mathematiker-Kon-gress zu Paris 1900, Nachrichten der Akademie der Wissenschaften in Gbttingen. II. Mathematische-Physikalische Klasse","author":"Hilbert","year":"1900"},{"key":"S0022481200049689_ref021","first-page":"220","volume":"25","author":"Putnam","year":"1960","journal-title":"An unsolvable problem in number theory"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200049689","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,8]],"date-time":"2025-01-08T21:14:24Z","timestamp":1736370864000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200049689\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1978,6]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1978,6]]}},"alternative-id":["S0022481200049689"],"URL":"https:\/\/doi.org\/10.2307\/2272832","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1978,6]]}}}