{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T11:03:42Z","timestamp":1725879822392},"publisher-location":"Cham","reference-count":54,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319418414"},{"type":"electronic","value":"9783319418421"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-41842-1_5","type":"book-chapter","created":{"date-parts":[[2017,2,1]],"date-time":"2017-02-01T17:01:15Z","timestamp":1485968475000},"page":"107-149","source":"Crossref","is-referenced-by-count":1,"title":["Hyperarithmetical Sets"],"prefix":"10.1007","author":[{"given":"Yiannis N.","family":"Moschovakis","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,1,31]]},"reference":[{"key":"5_CR1","unstructured":"Addison, J. W. (1959). Separation principles in the hierarchies of classical and effective descriptive set theory. Fundamenta Methematicae, 46:123\u2013135."},{"key":"5_CR2","unstructured":"Church, A. (1935). An unsolvable problem in elementary number theory. Bulletin of the American Mathematical Society, 41:332\u2013333. This is an abstract of [3]."},{"key":"5_CR3","doi-asserted-by":"crossref","unstructured":"Church, A. (1936). An unsolvable problem in elementary number theory. American Journal of Mathematics, pages 345\u2013363. An abstract of this paper was published in [52].","DOI":"10.2307\/2371045"},{"key":"5_CR4","unstructured":"Davis, M. (1950a). On the theory of recursive unsolvability. PhD thesis, Princeton University."},{"key":"5_CR5","unstructured":"Davis, M. (1950b). Relatively recursive functions and the extended Kleene hierarchy. page 723. Proceedings of the International Congress of Mathematicians, Cambridge, Mass, 1950."},{"key":"5_CR6","unstructured":"Davis, M. (1965). The undecidable. Raven Press."},{"key":"5_CR7","doi-asserted-by":"crossref","unstructured":"Enderton, H. B., and Putnam, H. (1970). A note on the hyperarithmetical hierarchy. The Journal of Symbolic Logic, 35:429\u2013430.","DOI":"10.2307\/2270699"},{"key":"5_CR8","unstructured":"Feferman, S. (1965). Some applications of forcing and generic sets. Fundamenta Methematicae, 56:325\u2013345."},{"key":"5_CR9","unstructured":"Gandy, R., Kreisel, G., and Tait, W. (1960). Set existence. Bulletin of the Polish Academy of Sciences, Series in Science, Mathematics and Astronomy, 8:577\u2013582."},{"key":"5_CR10","unstructured":"Gandy, R. O. (1960). Proof of Mostowski\u2019s conjecture. Bulletin de l\u2019Academie Polonaise des Sciences, S\u00e9rie des sciences math\u00e9matiques, astronomiques et physiques, 8:571\u2013575."},{"key":"5_CR11","doi-asserted-by":"crossref","unstructured":"G\u00f6del, K. (1931). \u00dcber formal unentscheidbare S\u00e4tze der Principia Mathematica and verwandter Systeme, I. Monatshefte f\u00fcr Mathematik und Physik, pages 173\u2013198. English translations in [53] and [54].","DOI":"10.1007\/BF01700692"},{"key":"5_CR12","doi-asserted-by":"crossref","unstructured":"Kechris, A.\u00a0S. and Moschovakis, Y.\u00a0N. (1977). Recursion in higher types. In Barwise, J., editor, Handbook of Mathematical Logic, Studies in Logic, No. 90, pages 681\u2013737. North Holland, Amsterdam.","DOI":"10.1016\/S0049-237X(08)71119-4"},{"key":"5_CR13","doi-asserted-by":"crossref","unstructured":"Kleene, S. C. (1936). General recursive functions of natural numbers. Mathematische Annalen, 112:727\u2013742.","DOI":"10.1007\/BF01565439"},{"key":"5_CR14","doi-asserted-by":"crossref","unstructured":"Kleene, S. C. (1938). On notation for ordinal numbers. Journal of Symbolic Logic, 3:150\u2013155.","DOI":"10.2307\/2267778"},{"key":"5_CR15","doi-asserted-by":"crossref","unstructured":"Kleene, S. C. (1943). Recursive predicates and quantifiers. Transactions of the American Mathematical Society, 53:41\u201373.","DOI":"10.1090\/S0002-9947-1943-0007371-8"},{"key":"5_CR16","unstructured":"Kleene, S. C. (1950). A symmetric form of G\u00f6del\u2019s theorem. Konin. Neder. Akad. van Weten. te Amst. Proc. of the Section of Sciences, 53:800\u2013802."},{"key":"5_CR17","volume-title":"Introduction to metamathematics","author":"SC Kleene","year":"1952","unstructured":"Kleene, S. C. (1952). Introduction to metamathematics. North Holland Co: D. Van Nostrand Co."},{"key":"5_CR18","unstructured":"Kleene, S.\u00a0C. (1953). Arithmetical predicates and function quantifiers. Journal of Symbolic Logic, 18:190. abstract of a talk presented at a meeting of the Association for Symbolic Logic on December 29, 1952."},{"key":"5_CR19","doi-asserted-by":"crossref","unstructured":"Kleene, S. C. (1955a). \u00e5Arithmetical predicates and function quantifiers. Transactions of the American Mathematical Society, 79:312\u2013340.","DOI":"10.1090\/S0002-9947-1955-0070594-4"},{"key":"5_CR20","doi-asserted-by":"crossref","unstructured":"Kleene, S. C. (1955b). On the form of predicates in the theory of constructive ordinals (second paper). American Journal of Mathematics, 77:405\u2013428.","DOI":"10.2307\/2372632"},{"key":"5_CR21","doi-asserted-by":"crossref","unstructured":"Kleene, S. C. (1955c). Hierarchies of number theoretic predicates. Bulletin of the American Mathematical Society, 61:193\u2013213.","DOI":"10.1090\/S0002-9904-1955-09896-3"},{"key":"5_CR22","unstructured":"Kleene, S. C. (1959a). Quantification of number-theoretic functions. Compositio Mathematica, 14:23\u201340."},{"key":"5_CR23","doi-asserted-by":"crossref","unstructured":"Kleene, S. C. (1959b). Recursive functionals and quantifiers of finite types I. Transactions of the American Mathematical Society, 91:1\u201352.","DOI":"10.2307\/1993145"},{"key":"5_CR24","unstructured":"Kondo, M. (1938). Sur l\u2019uniformization des complementaires analytiques et les ensembles projectifs de la second classe. Japanese Journal of Mathematics, 15:197\u2013230."},{"key":"5_CR25","doi-asserted-by":"crossref","unstructured":"Kreider, D. L., and Rogers, H, Jr. (1961). Constructive versions of ordinal number classes. Transactions of the American Mathematical Society, 100:325\u2013369.","DOI":"10.1090\/S0002-9947-1961-0151396-X"},{"key":"5_CR26","unstructured":"Kreisel, G. (1961). Set theoretic problems suggested by the notion of potential totality. Infinitistic methods (pp. 103\u2013140). Pergamon, New York."},{"key":"5_CR27","doi-asserted-by":"crossref","unstructured":"Kreisel, G. (1962). The axiom of choice and the class of hyperarithmetic functions. Indagationes Mathematicae, 24:307\u2013319.","DOI":"10.1016\/S1385-7258(62)50029-2"},{"key":"5_CR28","unstructured":"Lebesgue, H. (1905). Sur les fonctions repres\u00e9ntables analytiquement. Journal de Math\u00e9matiques 6 $$^{\\rm {e}}$$ e \u00a0serie, 1:139\u2013216."},{"key":"5_CR29","unstructured":"Markov, A.\u00a0A. (1947). On the impossibility of certain algorithms in the theory of associative systems. Coptes rendus (Doklady) de l\u2019Academie des Sciences de USSR, 55:583\u2013586."},{"key":"5_CR30","doi-asserted-by":"crossref","unstructured":"Markwald, W. (1954). Zur Theorie der konstruktiven Wohlordnungen. Mathematischen Annalen, 127:135\u2013149.","DOI":"10.1007\/BF01361115"},{"key":"5_CR31","doi-asserted-by":"crossref","unstructured":"Moschovakis, Y. N. (1966). Many-one degrees of the predicates $$H_a(x)$$ H a ( x ) . Pacific Journal of Mathematics, 18:329\u2013342.","DOI":"10.2140\/pjm.1966.18.329"},{"key":"5_CR32","unstructured":"Moschovakis, Y. N. (1968). Review of four papers on Church\u2019s Thesis. The Journal of Symbolic Logic, 33:471\u2013472."},{"key":"5_CR33","doi-asserted-by":"crossref","unstructured":"Moschovakis, Y. N. (1969). Abstract first order computability II. Transactions of the American Mathematical Society, 138:465\u2013504.","DOI":"10.1090\/S0002-9947-69-99947-4"},{"key":"5_CR34","unstructured":"Moschovakis, Y.\u00a0N. (1974). Elementary Induction on Abstract Structures. North Holland, Amsterdam. Studies in Logic, No. 77. Republished by Dover Publications, Mineola, NY, 2008, with a correction to 8.3."},{"key":"5_CR35","doi-asserted-by":"crossref","unstructured":"Moschovakis, Y.\u00a0N. (2009). Descriptive set theory, Second edition, volume 155 of Mathematical Surveys and Monographs. American Mathematical Society.","DOI":"10.1090\/surv\/155"},{"key":"5_CR36","doi-asserted-by":"crossref","unstructured":"Moschovakis, Y. N. (2010a). Classical descriptive set theory as a refinement of effective descriptive set theory. Annals of Pure and Applied Logic, 162:243\u2013255.","DOI":"10.1016\/j.apal.2010.09.010"},{"key":"5_CR37","doi-asserted-by":"crossref","unstructured":"Moschovakis, Y. N. (2010b). Kleene\u2019s amazing second recursion theorem. The Bulletin of Symbolic Logic, 16:189\u2013239.","DOI":"10.2178\/bsl\/1286889124"},{"key":"5_CR38","unstructured":"Mostowski, A. (1947). On definable sets of positive integers. Fundamenta Methematicae, 34:81\u2013112."},{"key":"5_CR39","unstructured":"Mostowski, A. (1951). A classification of logical systems. Studia Philosophica, 4:237\u2013274."},{"key":"5_CR40","doi-asserted-by":"crossref","unstructured":"Myhill, J. (1955). Creative sets. Zeitschrifft f\u00fcr Mathematische Logik und Grundlagen der Mathematik, 1:97\u2013108.","DOI":"10.1002\/malq.19550010205"},{"key":"5_CR41","unstructured":"Nelson, G. C. (1974). Many-one reducibility within the Turing degrees of the hyperarithmetic sets $$Ha(x)$$ H a ( x ) . Transactions of the American Mathematical Society, 191:1\u201344."},{"key":"5_CR42","doi-asserted-by":"crossref","unstructured":"Post, E. L. (1944). Recursively enumerable sets of positive integers and their decision problems. Bulletin of the American Mathematical Society, 50:284\u2013316.","DOI":"10.1090\/S0002-9904-1944-08111-1"},{"key":"5_CR43","doi-asserted-by":"crossref","unstructured":"Post, E. L. (1947). Recursive unsolvability of a problem of Thue. The Journal of Symbolic Logic, 12:1\u201311.","DOI":"10.2307\/2267170"},{"key":"5_CR44","unstructured":"Putnam, H. (1961). Uniqueness ordinals in higher constructive number classes. Essays on the foundations of mathematics, pages 190\u2013206. Magnes Press, Hebrew University, Jerusalem."},{"key":"5_CR45","unstructured":"Rogers, Jr., H. (1967). Theory of recursive functions and effective computability. McGraw-Hill."},{"key":"5_CR46","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-12013-2","volume-title":"Higher Recursion Theory","author":"GE Sacks","year":"1990","unstructured":"Sacks, G. E. (1990). Higher Recursion Theory. Perspectives in Mathematical Logic: Springer."},{"key":"5_CR47","doi-asserted-by":"crossref","unstructured":"Spector, C. (1955). Recursive wellorderings. Journal of Symbolic Logic, 20:151\u2013163.","DOI":"10.2307\/2266902"},{"key":"5_CR48","doi-asserted-by":"crossref","unstructured":"Spector, C. (1956). On degress of recursive unsolvability. Annals of Mathematics, 64:581\u2013582.","DOI":"10.2307\/1969604"},{"key":"5_CR49","unstructured":"Spector, C. (1960). Hyperarithmetical quantifiers. Fundamenta Methematicae, 48:313\u2013320."},{"key":"5_CR50","unstructured":"Spector, C. (1961). Inductively defined sets of natural numbers. Infinitistic methods, pages 97\u2013102. Pergamon, New York."},{"key":"5_CR51","doi-asserted-by":"crossref","unstructured":"Steel, J. R. (1978). Forcing with tagged trees. Annals of Mathematical Logic, 15:55\u201374.","DOI":"10.1016\/0003-4843(78)90026-8"},{"key":"5_CR52","unstructured":"Suslin, M. (1917). Sur une definition des ensembles measurables B sans nombres transfinis. Comptes Rendus Acad. Sci. Paris, 164:88\u201391."},{"key":"5_CR53","unstructured":"Turing, A.\u00a0M. (1936). On computable numbers with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 42:230\u2013265. A correction, ibid. volume 43 (1937), pp. 544\u2013546."},{"key":"5_CR54","unstructured":"Van Heijenoort, J., editor (1967). From Frege to G\u00f6del, a source book in mathematical logic, 1879\u20131931. Harvard University Press, Cambridge, Massachusetts, London, England."}],"container-title":["Outstanding Contributions to Logic","Martin Davis on Computability, Computational Logic, and Mathematical Foundations"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-41842-1_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,6,25]],"date-time":"2017-06-25T09:31:45Z","timestamp":1498383105000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-41842-1_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319418414","9783319418421"],"references-count":54,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-41842-1_5","relation":{},"ISSN":["2211-2758","2211-2766"],"issn-type":[{"type":"print","value":"2211-2758"},{"type":"electronic","value":"2211-2766"}],"subject":[],"published":{"date-parts":[[2016]]}}}