{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,2,10]],"date-time":"2023-02-10T10:53:01Z","timestamp":1676026381484},"reference-count":16,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":9142,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1989,3]]},"abstract":"<jats:p>The paper [Sch\u00fctte + Simpson] deals with the following one-dimensional case of Friedman's extension (see in [Simpson 1]) of Kruskal's theorem ([Kruskal]). Given a natural number <jats:italic>n<\/jats:italic>, let <jats:italic>S<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic>+1<\/jats:sub> be the set of all finite sequences of natural numbers &lt;<jats:italic>n<\/jats:italic> + 1. If <jats:italic>s<\/jats:italic><jats:sub>1<\/jats:sub> = (<jats:italic>a<\/jats:italic><jats:sub>0<\/jats:sub>,\u2026,<jats:italic>a<jats:sub>k<\/jats:sub><\/jats:italic>) <jats:italic>\u2208<\/jats:italic><jats:italic>S<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic>+1<\/jats:sub> and <jats:italic>s<\/jats:italic><jats:sub>2<\/jats:sub> = (<jats:italic>b<\/jats:italic><jats:sub>0<\/jats:sub>,\u2026,<jats:italic>b<jats:sub>m<\/jats:sub><\/jats:italic>) <jats:italic>\u2208<\/jats:italic><jats:italic>S<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic> + 1<\/jats:sub>, then a strictly monotone function <jats:italic>f<\/jats:italic>: {0,\u2026, <jats:italic>k<\/jats:italic>} \u2192 {0,\u2026, <jats:italic>m<\/jats:italic>} is called an embedding of <jats:italic>s<\/jats:italic><jats:sub>1<\/jats:sub> into <jats:italic>s<\/jats:italic><jats:sub>2<\/jats:sub> if the following two assertions are satisfied:<\/jats:p><jats:p>1) <jats:italic>a<jats:sub>i<\/jats:sub><\/jats:italic>, = <jats:italic>b<jats:sub>f(i)<\/jats:sub><\/jats:italic>, for all <jats:italic>i<\/jats:italic> &lt; <jats:italic>k<\/jats:italic>;<\/jats:p><jats:p>2) if <jats:italic>f<\/jats:italic>(<jats:italic>i<\/jats:italic>) &lt; <jats:italic>j<\/jats:italic> &lt; <jats:italic>f<\/jats:italic>(<jats:italic>i<\/jats:italic> + 1) then <jats:italic>b<jats:sub>j<\/jats:sub><\/jats:italic> &gt; <jats:italic>b<\/jats:italic><jats:sub><jats:italic>f<\/jats:italic>(<jats:italic>i<\/jats:italic>+1)<\/jats:sub>, for all <jats:italic>i<\/jats:italic> &lt; <jats:italic>k<\/jats:italic>, <jats:italic>j<\/jats:italic> &lt; <jats:italic>m<\/jats:italic>.<\/jats:p><jats:p>Then for every infinite sequence <jats:italic>s<\/jats:italic><jats:sub>1<\/jats:sub>, <jats:italic>s<\/jats:italic><jats:sub>2<\/jats:sub>,\u2026,<jats:italic>s<jats:sub>k<\/jats:sub><\/jats:italic>,\u2026 of elements of <jats:italic>S<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic> + 1<\/jats:sub> there exist indices <jats:italic>i<\/jats:italic> &lt; <jats:italic>j<\/jats:italic> and an embedding of <jats:italic>s<jats:sub>i<\/jats:sub><\/jats:italic> into <jats:italic>S<jats:sub>j<\/jats:sub><\/jats:italic>. That is, <jats:italic>S<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic>+1<\/jats:sub> forms a well-quasi-ordering (<jats:italic>wqo<\/jats:italic>) with respect to embeddability. For each <jats:italic>n<\/jats:italic>, this statement W(<jats:italic>S<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic>+1<\/jats:sub>) is provable in the standard second order conservative extension of Peano arithmetic. On the other hand, the proof-theoretic strength of the statements W(<jats:italic>S<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic>+1<\/jats:sub>) grows so fast that this formal theory cannot prove the limit statement \u2200<jats:italic>n<\/jats:italic>W(<jats:italic>S<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic>+1<\/jats:sub>). The appropriate first order <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200027626_inline1\" \/>-versions of these combinatory statements preserve their proof-theoretic strength, so that actually one can speak in terms of provability in Peano arithmetic. These are the main conclusions from [Sch\u00fctte + Simpson].<\/jats:p><jats:p>We wish to extend this into the transfinite. That is, we take an arbitrary countable ordinal <jats:italic>\u03c4<\/jats:italic> &gt; 0 instead of <jats:italic>n<\/jats:italic> + 1 and try to obtain an analogous \u201cstrong\u201d combinatory statement about finite sequences of ordinals &lt; <jats:italic>\u03c4<\/jats:italic>.<\/jats:p>","DOI":"10.2307\/2275019","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T22:29:26Z","timestamp":1146954566000},"page":"100-121","source":"Crossref","is-referenced-by-count":6,"title":["Generalizations of the one-dimensional version of the Kruskal-Friedman theorems"],"prefix":"10.1017","volume":"54","author":[{"given":"L.","family":"Gordeev","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200027626_ref006","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)71365-X"},{"key":"S0022481200027626_ref003","first-page":"193","volume":"33","author":"Feferman","year":"1968","journal-title":"Systems of predicative analysis. II"},{"key":"S0022481200027626_ref005","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)70769-9"},{"key":"S0022481200027626_ref010","first-page":"210","article-title":"Well-quasi-ordering, the tree theorem, and Vazsonyi's conjecture","volume":"95","author":"Kruskal","year":"1960","journal-title":"Transactions of the American Mathematical Society"},{"key":"S0022481200027626_ref013","doi-asserted-by":"publisher","DOI":"10.1007\/BF02007558"},{"key":"S0022481200027626_ref014","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)71124-8"},{"key":"S0022481200027626_ref004","first-page":"447","volume-title":"Proof theory","author":"Feferman","year":"1987"},{"key":"S0022481200027626_ref009","first-page":"867","volume":"49","author":"J\u00e4ger","year":"1984","journal-title":"The strength of admissibility without foundation"},{"key":"S0022481200027626_ref007","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(88)90055-3"},{"key":"S0022481200027626_ref001","doi-asserted-by":"publisher","DOI":"10.1016\/1385-7258(77)90067-1"},{"key":"S0022481200027626_ref012","doi-asserted-by":"publisher","DOI":"10.1007\/BF01972460"},{"key":"S0022481200027626_ref011","doi-asserted-by":"publisher","DOI":"10.1007\/BF01091743"},{"key":"S0022481200027626_ref015","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(09)70156-9"},{"key":"S0022481200027626_ref008","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-2.1.326"},{"key":"S0022481200027626_ref002","first-page":"1","volume":"29","author":"Feferman","year":"1964","journal-title":"Systems of predicative analysis. I"},{"key":"S0022481200027626_ref016","first-page":"432","volume-title":"Proof theory","author":"Simpson","year":"1987"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200027626","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T21:01:41Z","timestamp":1558299701000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200027626\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,3]]},"references-count":16,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1989,3]]}},"alternative-id":["S0022481200027626"],"URL":"https:\/\/doi.org\/10.2307\/2275019","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989,3]]}}}