{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T02:38:03Z","timestamp":1648953483077},"reference-count":7,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":7041,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1994,12]]},"abstract":"<jats:p>H. Friedman proved that the following sentence SWQO(<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200019198_inline1\" \/>) is true but not provable in the theory <jats:bold>ATR<jats:sub>0<\/jats:sub><\/jats:bold> (cf. [S]; <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200019198_inline1\" \/> \u2254 the set of finite rooted trees, \u2223<jats:italic>T<\/jats:italic>\u2223 \u2254 the cardinality of <jats:italic>T<\/jats:italic> \u2208 <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200019198_inline1\" \/>).<\/jats:p><jats:p><jats:disp-quote><jats:p>For every <jats:italic>k<\/jats:italic> &gt; 0 there is an <jats:italic>n<\/jats:italic> so large that for any <jats:italic>T<\/jats:italic><jats:sub>0<\/jats:sub>, <jats:italic>T<\/jats:italic><jats:sub>1<\/jats:sub>,\u2026, <jats:italic>T<jats:sub>n<\/jats:sub><\/jats:italic> \u2208 <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200019198_inline1\" \/> with \u2200<jats:italic>i<\/jats:italic> \u2264 <jats:italic>n<\/jats:italic>(\u2223<jats:italic>T<jats:sub>i<\/jats:sub><\/jats:italic>\u2223 \u2264 <jats:italic>k<\/jats:italic> \u00b7 (<jats:italic>i<\/jats:italic> + 1)) there are <jats:italic>i<\/jats:italic> &lt; <jats:italic>j<\/jats:italic> \u2264 <jats:italic>n<\/jats:italic> such that <jats:italic>T<jats:sub>i<\/jats:sub><\/jats:italic> is homeomorphically embeddable into <jats:italic>T<jats:sub>j<\/jats:sub><\/jats:italic>.<\/jats:p><\/jats:disp-quote><\/jats:p><jats:p>Since <jats:bold>ATR<jats:sub>0<\/jats:sub><\/jats:bold> is stronger than <jats:bold>PA<\/jats:bold>, SWQO(<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200019198_inline1\" \/>) is not provable in <jats:bold>PA<\/jats:bold>, either. Furthermore, SWQO(<jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200019198_inline1\" \/>) is proof-theoretically stronger than <jats:bold>PA<\/jats:bold>. A similar sentence whose proof-theoretical strength is exactly that of <jats:bold>PA<\/jats:bold> was obtained by replacing finite trees by finite sequences of bounded natural numbers under the embeddability with H. Friedman's asymmetrical gap-condition (see [SS]). The latter sentence was modified by using the weaker symmetrical gap-condition (see the corresponding particular case in [Gl]). Further improvement is indicated in [G2, Corollary 4.5]. Namely, the assertion \u2223<jats:italic>X<jats:sub>i<\/jats:sub><\/jats:italic>\u2223 \u2264 <jats:italic>k<\/jats:italic> \u00b7 (<jats:italic>i<\/jats:italic> + 1) as in SWQO(<jats:italic>J<\/jats:italic>), above, can be weakened to<\/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=\"S0022481200019198_eqnU1\" \/><\/jats:disp-formula>.<\/jats:p><jats:p>(in fact, to wt(<jats:italic>X<jats:sub>i<\/jats:sub><\/jats:italic>) \u2264 <jats:italic>k<\/jats:italic> + <jats:italic>\u03b5<\/jats:italic> \u00b7 <jats:italic>i<\/jats:italic> for an arbitrary fixed <jats:italic>\u03b5<\/jats:italic> = <jats:italic>l<\/jats:italic><jats:sup>\u22121<\/jats:sup>, <jats:italic>l<\/jats:italic> &lt; 0, where wt(<jats:italic>X<\/jats:italic>) is the weight of the \u201cword\u201d <jats:italic>X<\/jats:italic>).<\/jats:p>","DOI":"10.2307\/2275697","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T18:53:29Z","timestamp":1146941609000},"page":"1154-1157","source":"Crossref","is-referenced-by-count":2,"title":["A modified sentence unprovable in <b>PA<\/b>"],"prefix":"10.1017","volume":"59","author":[{"given":"L.","family":"Gordeev","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200019198_ref006","doi-asserted-by":"publisher","DOI":"10.1007\/BF02007558"},{"key":"S0022481200019198_ref005","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(09)70156-9"},{"key":"S0022481200019198_ref003","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)71130-3"},{"key":"S0022481200019198_ref001","first-page":"100","volume":"54","author":"Gordeev","year":"1989","journal-title":"Generalizations of the one-dimensional version of the Kruskal-Friedman theorems"},{"key":"S0022481200019198_ref002","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/147\/01194"},{"key":"S0022481200019198_ref007","volume-title":"Proof theory","author":"Takeuti","year":"1987"},{"key":"S0022481200019198_ref004","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1112\/blms\/14.4.285","article-title":"Accessible independence results for Peano arithmetic","volume":"14","author":"Paris","year":"1982","journal-title":"Bulletin of the London 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\/S0022481200019198","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,14]],"date-time":"2019-05-14T20:40:44Z","timestamp":1557866444000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200019198\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,12]]},"references-count":7,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1994,12]]}},"alternative-id":["S0022481200019198"],"URL":"https:\/\/doi.org\/10.2307\/2275697","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,12]]}}}