{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,2]],"date-time":"2026-03-02T11:19:28Z","timestamp":1772450368517,"version":"3.50.1"},"reference-count":16,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":15167,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1972,9]]},"abstract":"<jats:p>In this paper we discuss subsystems of number theory based on restrictions on induction in terms of quantifiers, and we show that all the natural formulations of \u2018<jats:italic>n<\/jats:italic>-quantifier induction\u2019 are reducible to one of two (for <jats:italic>n<\/jats:italic> \u2260 0) nonequivalent normal forms: the axiom of induction restricted to <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200079007_inline1\"\/> (or, equivalently, <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200079007_inline2\"\/>) formulae and the rule of induction restricted to <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200079007_inline2\"\/> formulae.<\/jats:p><jats:p>Let <jats:italic>Z<\/jats:italic><jats:sub>0<\/jats:sub> be classical elementary number theory with a symbol and defining equations for each Kalmar elementary function, and the rule of induction<\/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=\"S0022481200079007_eqnU1\"\/><\/jats:disp-formula><\/jats:p><jats:p>restricted to quantifier-free formulae. Given the schema<\/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=\"S0022481200079007_eqnU2\"\/><\/jats:disp-formula><\/jats:p><jats:p>let IA<jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> be the restriction of IA to formulae of <jats:italic>Z<\/jats:italic><jats:sub>0<\/jats:sub> with \u2264<jats:italic>n<\/jats:italic> nested quantifiers, IA<jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>\u2032 to formulae with \u2264<jats:italic>n<\/jats:italic> nested quantifiers, disregarding bounded quantifiers, <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200079007_inline3\"\/> the restriction to <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200079007_inline1\"\/> formulae, <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200079007_inline4\"\/> the restriction to <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200079007_inline2\"\/>, formulae. IR<jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>, IR<jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>\u2032, <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200079007_inline5\"\/>, <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200079007_inline6\"\/> are analogous.<\/jats:p><jats:p>Then, we show that, for every <jats:italic>n<\/jats:italic>, <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200079007_inline3\"\/>, <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200079007_inline4\"\/>, IA<jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>, and IA<jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>\u2032, are all equivalent modulo <jats:italic>Z<\/jats:italic><jats:sub>0<\/jats:sub>. The corresponding statement does not hold for IR. We show that, if <jats:italic>n<\/jats:italic> \u2260 0, <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200079007_inline6\"\/> is reducible to <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200079007_inline6\"\/>; evidently IR<jats:sub><jats:italic>n<\/jats:italic><\/jats:sub> is reducible to <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200079007_inline6\"\/>. On the other hand, IR<jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>\u2032 is obviously equivalent to IA<jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>\u2032 [10, Lemma 2].<\/jats:p>","DOI":"10.2307\/2272731","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T21:17:55Z","timestamp":1146950275000},"page":"466-482","source":"Crossref","is-referenced-by-count":58,"title":["On <i>n<\/i>-quantifier induction"],"prefix":"10.1017","volume":"37","author":[{"given":"Charles","family":"Parsons","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200079007_ref014","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)71195-9"},{"key":"S0022481200079007_ref009","first-page":"290","volume-title":"Constructivity in mathematics","author":"Kreisel","year":"1959"},{"key":"S0022481200079007_ref015","first-page":"361","volume":"36","author":"Parsons","year":"1971","journal-title":"Proof-theoretic analysis of restricted induction schemata"},{"key":"S0022481200079007_ref007","first-page":"284","volume":"24","author":"Kreisel","year":"1959","journal-title":"Inessential extensions of Heyting's arithmetic by means of functionals of finite type"},{"key":"S0022481200079007_ref006","first-page":"101","volume-title":"Constructivity in mathematics","author":"Kreisel","year":"1959"},{"key":"S0022481200079007_ref001","doi-asserted-by":"publisher","DOI":"10.1007\/BF01974150"},{"key":"S0022481200079007_ref002","first-page":"419","volume-title":"Intuitionism and proof theory","author":"Dreben","year":"1970"},{"key":"S0022481200079007_ref016","first-page":"587","volume":"36","author":"Parsons","year":"1971","journal-title":"On a number-theoretic choice schema. II"},{"key":"S0022481200079007_ref004","volume-title":"Introduction to metamathematics","author":"Kleene","year":"1952"},{"key":"S0022481200079007_ref012","doi-asserted-by":"publisher","DOI":"10.1007\/BF01342980"},{"key":"S0022481200079007_ref005","doi-asserted-by":"publisher","DOI":"10.4064\/fm-39-1-103-127"},{"key":"S0022481200079007_ref011","doi-asserted-by":"publisher","DOI":"10.1090\/pspum\/005\/0154801"},{"key":"S0022481200079007_ref013","first-page":"197","volume":"32","author":"Tait","year":"1967","journal-title":"Intensional interpretations of functionals of finite type. I"},{"key":"S0022481200079007_ref008","first-page":"321","volume":"33","author":"Kreisel","year":"1968","journal-title":"A survey of proof theory"},{"key":"S0022481200079007_ref003","first-page":"107","article-title":"Functional interpretation of bar induction by bar recursion","volume":"20","author":"Howard","year":"1968","journal-title":"Compositio Mathematica"},{"key":"S0022481200079007_ref010","first-page":"459","volume-title":"Intuitionism and proof theory","author":"Parsons","year":"1970"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200079007","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T20:57:47Z","timestamp":1559249867000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200079007\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1972,9]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1972,9]]}},"alternative-id":["S0022481200079007"],"URL":"https:\/\/doi.org\/10.2307\/2272731","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1972,9]]}}}