{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T13:45:35Z","timestamp":1772372735917,"version":"3.50.1"},"reference-count":11,"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":7132,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1994,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We construct a weak second-order theory of arithmetic which includes Weak K\u00f6nig's Lemma (WKL) for trees defined by bounded formulae. The provably total functions (with <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200019678_inline1\"\/>-graphs) of this theory are the polynomial time computable functions. It is shown that the first-order strength of this version of WKL is exactly that of the scheme of collection for bounded formulae.<\/jats:p>","DOI":"10.2307\/2275924","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T22:52:43Z","timestamp":1146955963000},"page":"1001-1011","source":"Crossref","is-referenced-by-count":24,"title":["A feasible theory for analysis"],"prefix":"10.1017","volume":"59","author":[{"given":"Fernando","family":"Ferreira","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200019678_ref011","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(86)90074-6"},{"key":"S0022481200019678_ref009","first-page":"338\u2013348","volume":"53","author":"Sieg","year":"1988","journal-title":"Hilbert's Program sixty years later"},{"key":"S0022481200019678_ref007","doi-asserted-by":"publisher","DOI":"10.1090\/psapm\/038\/1020810"},{"key":"S0022481200019678_ref003","first-page":"51\u201355","volume-title":"Contemporary Mathematics","volume":"106","author":"Buchholz","year":"1990"},{"key":"S0022481200019678_ref001","unstructured":"Buss S. , Bounded arithmetic, Ph.D. Dissertation, Princeton University, Princeton, New Jersey, 1985, rev. version, Bibliopolis, Naples, 1986."},{"key":"S0022481200019678_ref002","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1987-0894442-1"},{"key":"S0022481200019678_ref004","unstructured":"Ferreira F. , Polynomial time computable arithmetic and conservative extensions, Ph.D. Dissertation, Pennsylvania State University, University Park, Pennsylvania, 1988."},{"key":"S0022481200019678_ref006","volume-title":"Portugaliae Mathematica","author":"Ferreira"},{"key":"S0022481200019678_ref005","first-page":"137\u2013156","volume-title":"Contemporary Mathematics","volume":"106","author":"Ferreira","year":"1990"},{"key":"S0022481200019678_ref010","first-page":"432\u2013446","volume-title":"Proof theory","author":"Simpson","year":"1987"},{"key":"S0022481200019678_ref008","first-page":"35\u201356","article-title":"classes and degrees of theories","volume":"173","author":"Jockusch","year":"1972","journal-title":"Transactions of the American Mathematical Society"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200019678","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T03:16:33Z","timestamp":1557890193000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200019678\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,9]]},"references-count":11,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1994,9]]}},"alternative-id":["S0022481200019678"],"URL":"https:\/\/doi.org\/10.2307\/2275924","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,9]]}}}