{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,25]],"date-time":"2024-07-25T16:02:15Z","timestamp":1721923335908},"reference-count":44,"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":"Abstract<\/jats:title>We investigate the theory I\u03940<\/jats:sub>+\u03a91<\/jats:sub> and strengthen [Bu86, Theorem 8.6] to the following: if NP \u2260 co-NP, then \u03a3-completeness for witness comparison foumulas is not provable in bounded arithmetic. i.e.,<\/jats:p><\/jats:disp-formula><\/jats:p>Next we study a \u201csmall reflection principle\u201d in bounded arithmetic. We prove that for all sentences \u03c6<\/jats:italic><\/jats:p><\/jats:disp-formula><\/jats:p>The proof hinges on the use of definable cuts and partial satisfaction predicates akin to those introduced by Pudl\u00e1k in [Pu86].<\/jats:p>Finally, we give some applications of the small reflection principle, showing that the principle can sometimes be invoked in order to circumvent the use of provable \u03a3-completeness for witness comparison formulas.<\/jats:p>","DOI":"10.2307\/2275908","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T22:52:43Z","timestamp":1146955963000},"page":"785-812","source":"Crossref","is-referenced-by-count":9,"title":["A small reflection principle for bounded arithmetic"],"prefix":"10.1017","volume":"59","author":[{"given":"Rineke","family":"Verbrugge","sequence":"first","affiliation":[]},{"given":"Albert","family":"Visser","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200019514_ref043","first-page":"143\u2013161","volume-title":"Logic, methodology and philosophy of science VIII","author":"Wilkie","year":"1989"},{"key":"S0022481200019514_ref040","first-page":"175\u2013209","volume-title":"Mathematical logic","author":"Visser","year":"1990"},{"key":"S0022481200019514_ref033","volume-title":"Proof theory","author":"Takeuti","year":"1975"},{"key":"S0022481200019514_ref039","volume-title":"Evaluation, provably deductive equivalence in Heyting's Arithmetic of substitution instances of propositional formulas","author":"Visser","year":"1985"},{"key":"S0022481200019514_ref029","unstructured":"Solovay R. M. , On interpretability in set theories , manuscript, 1976."},{"key":"S0022481200019514_ref028","doi-asserted-by":"publisher","DOI":"10.1007\/BF02757006"},{"key":"S0022481200019514_ref023","first-page":"667\u2013671","article-title":"A definition of exponentiation by a bounded arithmetical formula","volume":"24","author":"Pudl\u00e1k","year":"1983","journal-title":"Commentationes Mathematicae Universitatis Carolinae"},{"key":"S0022481200019514_ref025","first-page":"165\u2013196","volume-title":"Logic colloquium \u201984","author":"Pudl\u00e1k","year":"1986"},{"key":"S0022481200019514_ref016","doi-asserted-by":"publisher","DOI":"10.1007\/BF00370387"},{"key":"S0022481200019514_ref019","doi-asserted-by":"publisher","DOI":"10.1007\/BF01633984"},{"key":"S0022481200019514_ref012","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-22156-3"},{"key":"S0022481200019514_ref032","first-page":"986\u2013999","volume":"48","author":"\u0160vejdar","year":"1983","journal-title":"Modal analysis of generalized Rosser sentences"},{"key":"S0022481200019514_ref011","first-page":"217\u2013232","volume-title":"Logic colloquium \u201883","volume":"2","author":"H\u00e1jek","year":"1983"},{"key":"S0022481200019514_ref010","doi-asserted-by":"publisher","DOI":"10.1016\/0003-4843(79)90017-2"},{"key":"S0022481200019514_ref041","doi-asserted-by":"publisher","DOI":"10.1007\/BF00370389"},{"key":"S0022481200019514_ref007","volume-title":"Bounded arithmetic","author":"Buss","year":"1986"},{"key":"S0022481200019514_ref006","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(93)90199-N"},{"key":"S0022481200019514_ref038","first-page":"263\u2013295","article-title":"On the completeness principle","volume":"22","author":"Visser","year":"1982","journal-title":"Annals of Mathematical Logic"},{"key":"S0022481200019514_ref005","volume-title":"On bimodal provability logics for \u220f1-axiomatized extensions of arithmetical theories","author":"Beklemishev","year":"1991"},{"key":"S0022481200019514_ref002","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(93)90196-K"},{"key":"S0022481200019514_ref017","doi-asserted-by":"publisher","DOI":"10.1007\/BF00370388"},{"key":"S0022481200019514_ref020","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(78)90044-2"},{"key":"S0022481200019514_ref030","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(89)90048-1"},{"key":"S0022481200019514_ref014","doi-asserted-by":"publisher","DOI":"10.1007\/BF00370381"},{"key":"S0022481200019514_ref042","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(87)90066-2"},{"key":"S0022481200019514_ref034","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(88)90046-2"},{"key":"S0022481200019514_ref021","doi-asserted-by":"publisher","DOI":"10.1515\/9781400858927"},{"key":"S0022481200019514_ref018","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90076-7"},{"key":"S0022481200019514_ref013","doi-asserted-by":"publisher","DOI":"10.1007\/BF00370380"},{"key":"S0022481200019514_ref044","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90062-1"},{"key":"S0022481200019514_ref003","volume-title":"Structural complexity I","author":"Balc\u00e1zar","year":"1987"},{"key":"S0022481200019514_ref037","unstructured":"Visser A. , Aspects of diagonalization & provability, Ph.D. thesis, University of Utrecht, Utrecht, 1981."},{"key":"S0022481200019514_ref035","unstructured":"Verbrugge L. C. , Does Solovay's completeness theorem extend to bounded arithmetic?, Master's Thesis, University of Amsterdam, Amsterdam, 1988."},{"key":"S0022481200019514_ref009","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0062837"},{"key":"S0022481200019514_ref001","doi-asserted-by":"publisher","DOI":"10.4064\/fm-136-3-133-145"},{"key":"S0022481200019514_ref022","first-page":"494\u2013508","author":"Parikh","year":"1971","journal-title":"Existence and feasibility in arithmetic"},{"key":"S0022481200019514_ref026","first-page":"309\u2013332","volume-title":"Logic and combinatorics","volume":"35","author":"Pudl\u00e1k","year":"1987"},{"key":"S0022481200019514_ref015","volume-title":"Intensional logic","author":"de Jongh","year":"1988"},{"key":"S0022481200019514_ref004","doi-asserted-by":"publisher","DOI":"10.1070\/IM1990v035n02ABEH000701"},{"key":"S0022481200019514_ref031","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90061-X"},{"key":"S0022481200019514_ref027","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-8601-8"},{"key":"S0022481200019514_ref008","doi-asserted-by":"publisher","DOI":"10.4064\/fm-49-1-35-92"},{"key":"S0022481200019514_ref036","volume-title":"\u03a3-completeness and bounded arithmetic","author":"Verbrugge","year":"1989"},{"key":"S0022481200019514_ref024","first-page":"423\u2013441","volume":"50","author":"Pudl\u00e1k","year":"1985","journal-title":"Cuts, consistency statements and interpretations"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200019514","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T03:15:36Z","timestamp":1557890136000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200019514\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,9]]},"references-count":44,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1994,9]]}},"alternative-id":["S0022481200019514"],"URL":"https:\/\/doi.org\/10.2307\/2275908","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,9]]}}}