{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T15:53:57Z","timestamp":1767196437997,"version":"build-2238731810"},"reference-count":13,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":13890,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1976,3]]},"abstract":"In [1] Gandy established the following selection theorem for recursion in type-2 objects.<\/jats:p>\n \n Theorem.\n \n Let\n F<\/jats:bold>\n be a normal type-2 object. Then it is possible to select (uniformly and effectively in\n F<\/jats:bold>\n ) an integer from each nonempty set of integers semirecursive in\n F<\/jats:bold>\n <\/jats:italic>\n .\n <\/jats:p>\n \n Notice that this really asserts that the predicates semirecursive in\n \n F<\/jats:bold>\n <\/jats:italic>\n are closed under existential quantification over type-0. Moschovakis [6] has essentially proven this theorem for\n \n F<\/jats:italic>\n <\/jats:bold>\n of arbitrary type.\n <\/jats:p>\n In [2] Grilliot stated a powerful generalization of Gandy's result, namely:<\/jats:p>\n \n Grilliot's Selection Theorem.\n \n Let\n F<\/jats:bold>\n be a normal type-(n + 2) object (n an arbitrary integer). Then it is possible to select (uniformly and effectively in\n F<\/jats:bold>\n ) a nonempty recursive in\n F<\/jats:bold>\n subset of each nonempty semirecursive in\n F<\/jats:bold>\n set oftype-(n \u2212 1) objects\n <\/jats:italic>\n .\n <\/jats:p>\n \n Notice again that this actually says that predicates semirecursive in\n \n F<\/jats:bold>\n <\/jats:italic>\n are closed under quantification over type-(\n n<\/jats:italic>\n \u2212 1) objects.\n <\/jats:p>\n Despite the similarity of these two results, Gandy and Grilliot proposed rather different methods of proof. Furthermore, the proof that Grilliot presented in [2] contains an error which cannot easily be corrected. (We will comment on the nature of this error at the end of \u00a71.) Fortunately, however, Grilliot's theorem is valid. We will present a proof of Grilliot's selection theorem which is a direct generalization of the proof of Gandy's theorem given in [6]. In fact, we will prove a general result (the theorem stated in \u00a72) which subsumes both Gandy's and Grilliot's results.<\/jats:p>","DOI":"10.2307\/2272954","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T17:40:11Z","timestamp":1146937211000},"page":"153-158","source":"Crossref","is-referenced-by-count":13,"title":["Selection in abstract recursion theory"],"prefix":"10.1017","volume":"41","author":[{"given":"L. A.","family":"Harrington","sequence":"first","affiliation":[]},{"given":"D. B.","family":"Macqueen","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200051847_bib008","first-page":"427","article-title":"Abstract first order computability. I, II","volume":"138","author":"Moschovakis","year":"1969","journal-title":"Transactions of the American Mathematical Society"},{"key":"S0022481200051847_bib007","first-page":"24","volume-title":"Mathematical logic and foundations of set theory","author":"Moschovakis","year":"1970"},{"key":"S0022481200051847_bib010","volume-title":"Elementary induction on abstract structures","author":"Moschovakis","year":"1974"},{"key":"S0022481200051847_bib009","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)70581-0"},{"key":"S0022481200051847_bib006","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1967-0236010-2"},{"key":"S0022481200051847_bib005","unstructured":"MacQueen, D. B. , Post's problem for recursion in higher types, Ph.D. Dissertation, M.I.T., 1972."},{"key":"S0022481200051847_bib003","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1971-0304141-5"},{"key":"S0022481200051847_bib013","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)70598-6"},{"key":"S0022481200051847_bib001","volume-title":"General recursive functionate of finite type and hierarchies of functions","author":"Gandy","year":"1962"},{"key":"S0022481200051847_bib012","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1968-0263626-0"},{"key":"S0022481200051847_bib011","unstructured":"Moschovakis, Y. N. , On nonmonotone inductive definitions (to appear)."},{"key":"S0022481200051847_bib002","first-page":"225","article-title":"Selection functions for recursive functionate","volume":"10","author":"Grilliot","year":"1969","journal-title":"Notre Dante Journal of Formal Logic"},{"key":"S0022481200051847_bib004","first-page":"1","article-title":"Recursive functionate and quantifiers of finite type. I, II","volume":"91","author":"Kleene","year":"1959","journal-title":"Transactions of the American Mathematical Society"}],"container-title":["The Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200051847","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,22]],"date-time":"2023-03-22T06:39:58Z","timestamp":1679467198000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200051847\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1976,3]]},"references-count":13,"aliases":["10.1017\/s0022481200051847"],"journal-issue":{"issue":"1","published-print":{"date-parts":[[1976,3]]}},"alternative-id":["S0022481200051847"],"URL":"https:\/\/doi.org\/10.2307\/2272954","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1976,3]]}}}