{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,6,14]],"date-time":"2022-06-14T11:07:19Z","timestamp":1655204839878},"reference-count":21,"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":12703,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1979,6]]},"abstract":"<jats:p>Spector [21] proved that a relation <jats:italic>R<\/jats:italic> on \u03c9 is \u03a0<jats:sub arrange=\"stack\">1<\/jats:sub><jats:sup arrange=\"stack\">1<\/jats:sup> if and only if it is (positive elementary) inductive on the structure \u3008\u03c9, +, \u00b7\u3009; Kleene [8] showed that <jats:italic>R<\/jats:italic> is \u03a0<jats:sub arrange=\"stack\">1<\/jats:sub><jats:sup arrange=\"stack\">1<\/jats:sup> if and only if it is semirecursive in the type 2 object <jats:italic>E<\/jats:italic>. These two \u201cconstructive\u201d characterizations of the \u03a0<jats:sub arrange=\"stack\">1<\/jats:sub><jats:sup arrange=\"stack\">1<\/jats:sup> relations have led to the independent study of (positive elementary) induction and recursion in <jats:italic>E<\/jats:italic> on an arbitrary structure, as natural generalizations of the theory of \u03a0<jats:sub arrange=\"stack\">1<\/jats:sub><jats:sup arrange=\"stack\">1<\/jats:sup> relations on (\u03c9, +, \u00b7 \u3009.<\/jats:p><jats:p>The theory of (positive elementary) induction on an arbitrary structure was developed by Moschovakis in his book <jats:bold><jats:italic>Elementary induction on abstract structures (EIAS)<\/jats:italic><\/jats:bold>; one of the most important theorems there is a generalization of the classical theorem of Spector [20] and Gandy [3] about the \u03a0<jats:sub arrange=\"stack\">1<\/jats:sub><jats:sup arrange=\"stack\">1<\/jats:sup> relations on \u03c9: a relation <jats:italic>R<\/jats:italic> is inductive on an acceptable structure <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200048957_inline1\" \/>. if and only if there is a formula \u03c6(<jats:italic>Y, x<\/jats:italic>) of the language of <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200048957_inline1\" \/> such that:<\/jats:p><jats:p><jats:disp-formula><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" orientation=\"portrait\" mime-subtype=\"gif\" mimetype=\"image\" position=\"float\" xlink:type=\"simple\" xlink:href=\"S0022481200048957_eqnU1\" \/><\/jats:disp-formula><\/jats:p><jats:p>where HYP is the collection of hyperelementary relations on <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200048957_inline1\" \/>.<\/jats:p><jats:p>Moschovakis [17] and Kechris and Moschovakis [6] showed how to develop the theory of recursion in higher types as a chapter in the general theory of inductive definability. This approach to recursion in higher types makes it possible to use methods from the theory of inductive definability in studying recursion in <jats:italic>E<\/jats:italic>.<\/jats:p><jats:p>In this paper we establish some results about recursion in <jats:italic>E<\/jats:italic> on a structure which bolster the naturalness of this theory and contribute to its comparison with (positive elementary) induction.<\/jats:p>","DOI":"10.2307\/2273731","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T17:50:09Z","timestamp":1146937809000},"page":"235-259","source":"Crossref","is-referenced-by-count":3,"title":["Recursion in a quantifier vs. elementary induction"],"prefix":"10.1017","volume":"44","author":[{"given":"Phokion G.","family":"Kolaitis","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200048957_ref020","doi-asserted-by":"publisher","DOI":"10.4064\/fm-48-3-313-320"},{"key":"S0022481200048957_ref018","volume-title":"Imbedding of higher type theories","author":"Normann","year":"1974"},{"key":"S0022481200048957_ref017","volume-title":"Proceedings of the Fifth International Congress of Logic, Methodology and Philosophy of Science","author":"Moschovakis"},{"key":"S0022481200048957_ref016","first-page":"53","volume-title":"Generalized recursion theory","author":"Moschovakis","year":"1974"},{"key":"S0022481200048957_ref012","first-page":"464","article-title":"Abstract first order computability. II","volume":"138","author":"Moschovakis","year":"1969","journal-title":"Transactions of the American Mathematical Society"},{"key":"S0022481200048957_ref010","first-page":"103","volume-title":"Infinistic methods","author":"Kreisel","year":"1961"},{"key":"S0022481200048957_ref021","first-page":"97","volume-title":"Infinistic methods","author":"Spector","year":"1961"},{"key":"S0022481200048957_ref008","first-page":"1","article-title":"Recursive functionals and quantifiers of finite type. I","volume":"91","author":"Kleene","year":"1959","journal-title":"Transactions of the American Mathematical Society"},{"key":"S0022481200048957_ref005","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1969-0265161-3"},{"key":"S0022481200048957_ref001","doi-asserted-by":"publisher","DOI":"10.1007\/BF02798678"},{"key":"S0022481200048957_ref003","first-page":"571","article-title":"Proof of Mostowski's conjecture","volume":"8","author":"Gandy","year":"1960","journal-title":"Bulletin de l'Acad\u00e9mie Polonaise des Sciences. S\u00e9rie des Sciences Math\u00e9matique Astronomique et Physiques"},{"key":"S0022481200048957_ref004","first-page":"265","volume-title":"Generalized recursion theory","author":"Gandy","year":"1974"},{"key":"S0022481200048957_ref009","first-page":"23","article-title":"Quantification of number theoretic functions","volume":"14","author":"Kleene","year":"1959","journal-title":"Compositio Mathematica"},{"key":"S0022481200048957_ref013","first-page":"605","volume":"34","author":"Moschovakis","year":"1969","journal-title":"Abstract computability and invariant definability"},{"key":"S0022481200048957_ref015","volume-title":"Elementary induction on abstract structures","author":"Moschovakis"},{"key":"S0022481200048957_ref002","unstructured":"Aczel P. , Stage comparison theorems and game playing with inductive definitions, unpublished notes. 1972."},{"key":"S0022481200048957_ref014","doi-asserted-by":"publisher","DOI":"10.1215\/S0012-7094-70-03744-0"},{"key":"S0022481200048957_ref011","unstructured":"MacQueen D. B. , Post's problem for recursion in higher types, Ph.D. Thesis, Massachusetts Institute of Technology, 1972."},{"key":"S0022481200048957_ref019","volume-title":"Theory of recursive functions and effective computability","author":"Rogers","year":"1967"},{"key":"S0022481200048957_ref006","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)71119-4"},{"key":"S0022481200048957_ref007","unstructured":"Kirousis L. M. , A note on recursion in E, unpublished notes, 1976."}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200048957","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T17:20:45Z","timestamp":1558891245000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200048957\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1979,6]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1979,6]]}},"alternative-id":["S0022481200048957"],"URL":"https:\/\/doi.org\/10.2307\/2273731","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1979,6]]}}}