{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,12]],"date-time":"2025-09-12T18:51:01Z","timestamp":1757703061729,"version":"3.40.5"},"reference-count":28,"publisher":"Cambridge University Press (CUP)","issue":"8","license":[{"start":{"date-parts":[[2021,1,29]],"date-time":"2021-01-29T00:00:00Z","timestamp":1611878400000},"content-version":"unspecified","delay-in-days":150,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2020,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Harvey Friedman\u2019s gap condition on embeddings of finite labelled trees plays an important role in combinatorics (proof of the graph minor theorem) and mathematical logic (strong independence results). In the present paper we show that the gap condition can be reconstructed from a small number of well-motivated building blocks: It arises via iterated applications of a uniform Kruskal theorem.<\/jats:p>","DOI":"10.1017\/s0960129520000298","type":"journal-article","created":{"date-parts":[[2021,1,29]],"date-time":"2021-01-29T02:53:52Z","timestamp":1611888832000},"page":"952-975","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":6,"title":["From Kruskal\u2019s theorem to Friedman\u2019s gap condition"],"prefix":"10.1017","volume":"30","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5456-5790","authenticated-orcid":false,"given":"Anton","family":"Freund","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2021,1,29]]},"reference":[{"key":"S0960129520000298_ref27","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-016-0515-6"},{"year":"1987","author":"Friedman","key":"S0960129520000298_ref8"},{"key":"S0960129520000298_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00392-X"},{"key":"S0960129520000298_ref11","doi-asserted-by":"publisher","DOI":"10.2307\/2274960"},{"key":"S0960129520000298_ref26","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-014-0408-5"},{"year":"1999","author":"Rathjen","key":"S0960129520000298_ref19"},{"key":"S0960129520000298_ref4","doi-asserted-by":"publisher","DOI":"10.1112\/blms.12285"},{"volume-title":"Research report","year":"1995","author":"Ogawa","key":"S0960129520000298_ref18"},{"key":"S0960129520000298_ref24","unstructured":"Tzameret, I. (2002). Kruskal-Friedman Gap Embedding Theorems over Well-Quasi-Orderings. MSc thesis, Tel-Aviv University. www.cs.tau.ac.il\/thesis\/thesis\/Tzameret-Iddo-MSc-Thesis.pdf (accessed 23.09.2020)."},{"key":"S0960129520000298_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90026-3"},{"key":"S0960129520000298_ref5","doi-asserted-by":"publisher","DOI":"10.1142\/S0219061320500063"},{"key":"S0960129520000298_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2020.102890"},{"key":"S0960129520000298_ref10","first-page":"75","article-title":"$\\Pi _2^1$-logic, part 1: Dilators","volume":"21","author":"Girard","year":"1981","journal-title":"Annals of Pure and Applied Logic"},{"year":"2009","author":"Simpson","key":"S0960129520000298_ref23"},{"key":"S0960129520000298_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-63875-X_59"},{"key":"S0960129520000298_ref16","first-page":"210","article-title":"Well-quasi-ordering, the tree theorem, and Vazsonyi\u2019s conjecture","volume":"95","author":"Kruskal","year":"1960","journal-title":"Transactions of the American Mathematical Society"},{"key":"S0960129520000298_ref17","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100003844"},{"key":"S0960129520000298_ref25","unstructured":"van der Meeren, J. (2015). Connecting the Two Worlds: Well-Partial-Orders and Ordinal Notation Systems. PhD thesis, Ghent University. https:\/\/biblio.ugent.be\/publication\/8094697\/file\/8094746.pdf (accessed 25.09.2020)."},{"key":"S0960129520000298_ref15","doi-asserted-by":"publisher","DOI":"10.2307\/1971481"},{"key":"S0960129520000298_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(91)90022-E"},{"key":"S0960129520000298_ref28","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1007\/s00153-017-0559-2","article-title":"Ordinal notation systems corresponding to Friedman\u2019s linearized well-partial-orders with gap-condition","volume":"56","author":"van der Meeren","year":"2017","journal-title":"Archive for Mathematical Logic"},{"year":"2013","author":"Haase","key":"S0960129520000298_ref12"},{"key":"S0960129520000298_ref14","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00349-2"},{"year":"1985","author":"Simpson","key":"S0960129520000298_ref22"},{"key":"S0960129520000298_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2019.106767"},{"key":"S0960129520000298_ref21","unstructured":"Schmidt, D. (2020). Well-partial orderings and their maximal order types. In: Schuster, P. , Seisenberger, M. and Weiermann, A. (eds.) Well-Quasi Orders in Computation, Logic, Language and Reasoning, Trends in Logic (Studia Logica Library), vol. 53, Cham, Springer, 351\u2013391. Originally Habilitationsschrift, Universit\u00e4t Heidelberg, 1979."},{"key":"S0960129520000298_ref7","unstructured":"Freund, A. , Rathjen, M. and Weiermann, A. (2020). Minimal bad sequences are necessary for a uniform Kruskal theorem. Preprint available as arXiv:2001.06380."},{"key":"S0960129520000298_ref20","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(93)90192-G"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129520000298","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,6]],"date-time":"2021-02-06T02:51:42Z","timestamp":1612579902000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129520000298\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9]]},"references-count":28,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["S0960129520000298"],"URL":"https:\/\/doi.org\/10.1017\/s0960129520000298","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"type":"print","value":"0960-1295"},{"type":"electronic","value":"1469-8072"}],"subject":[],"published":{"date-parts":[[2020,9]]},"assertion":[{"value":"\u00a9 The Author(s), 2021. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}