{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,27]],"date-time":"2025-09-27T13:50:59Z","timestamp":1758981059145,"version":"3.37.3"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"5-6","license":[{"start":{"date-parts":[[2022,10,26]],"date-time":"2022-10-26T00:00:00Z","timestamp":1666742400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,10,26]],"date-time":"2022-10-26T00:00:00Z","timestamp":1666742400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["460597863"],"award-info":[{"award-number":["460597863"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Arch. Math. Logic"],"published-print":{"date-parts":[[2023,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>It is generally accepted that H.\u00a0Friedman\u2019s gap condition is closely related to iterated collapsing functions from ordinal analysis. But what precisely is the connection? We offer the following answer: In a previous paper we have shown that the gap condition arises from an iterative construction on transformations of partial orders. Here we show that the parallel construction for linear orders yields familiar collapsing functions. The iteration step in the linear case is an instance of a general construction that we call \u2018Bachmann\u2013Howard derivative\u2019. In the present paper, we focus on the unary case, i.e., on the gap condition for sequences rather than trees and, correspondingly, on addition-free ordinal notation systems. This is partly for convenience, but it also allows us to clarify a phenomenon that is specific to the unary setting: As shown by van der Meeren, Rathjen and Weiermann, the gap condition on sequences admits two linearizations with rather different properties. We will see that these correspond to different recursive constructions of sequences.<\/jats:p>","DOI":"10.1007\/s00153-022-00851-5","type":"journal-article","created":{"date-parts":[[2022,10,26]],"date-time":"2022-10-26T13:07:41Z","timestamp":1666789661000},"page":"581-618","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Bachmann\u2013Howard derivatives"],"prefix":"10.1007","volume":"62","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5456-5790","authenticated-orcid":false,"given":"Anton","family":"Freund","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,10,26]]},"reference":[{"issue":"2","key":"851_CR1","doi-asserted-by":"publisher","first-page":"326","DOI":"10.1112\/plms\/s3-2.1.326","volume":"3","author":"G Higman","year":"1952","unstructured":"Higman, G.: Ordering by divisibility in abstract algebras. Proc. Lond. Math. Soc. 3(2), 326\u2013336 (1952)","journal-title":"Proc. Lond. Math. Soc."},{"issue":"2","key":"851_CR2","first-page":"210","volume":"95","author":"J Kruskal","year":"1960","unstructured":"Kruskal, J.: Well-quasi-ordering, the tree theorem, and Vazsonyi\u2019s conjecture. Trans. Am. Math. Soc. 95(2), 210\u2013225 (1960)","journal-title":"Trans. Am. Math. Soc."},{"key":"851_CR3","doi-asserted-by":"publisher","first-page":"833","DOI":"10.1017\/S0305004100003844","volume":"59","author":"CSJA Nash-Williams","year":"1963","unstructured":"Nash-Williams, C.S.J.A.: On well-quasi-ordering finite trees. Proc. Camb. Philos. Soc. 59, 833\u2013835 (1963)","journal-title":"Proc. Camb. Philos. Soc."},{"key":"851_CR4","doi-asserted-by":"crossref","unstructured":"Freund, A., Rathjen, M., Weiermann, A.: Minimal bad sequences are necessary for a uniform Kruskal theorem. Adv. Math. 400, article no. 108265, 44 pages (2022)","DOI":"10.1016\/j.aim.2022.108265"},{"key":"851_CR5","doi-asserted-by":"crossref","unstructured":"Girard, J.-Y.: $${\\Pi ^1_2}$$-logic, part 1: dilators. Ann. Pure Appl. Logic 21, 75\u2013219 (1981)","DOI":"10.1016\/0003-4843(81)90016-4"},{"key":"851_CR6","doi-asserted-by":"crossref","unstructured":"Simpson, S.G.: Subsystems of second order arithmetic. In: Perspectives in Logic. Cambridge University Press (2009)","DOI":"10.1017\/CBO9780511581007"},{"key":"851_CR7","doi-asserted-by":"crossref","unstructured":"Marcone, A.: On the logical strength of Nash\u2013Williams\u2019 theorem on transfinite sequences. In: Hodges, W., Hyland, M., Steinhorn, C., Truss, J. (eds.) Logic: From Foundations to Applications (Oxford). Oxford University Press, pp.\u00a0327\u2013351 (1996)","DOI":"10.1093\/oso\/9780198538622.003.0014"},{"key":"851_CR8","unstructured":"Hasegawa, R.: Well-ordering of algebras and Kruskal\u2019s theorem. In: Jones, N.D., Hagiya, M., Sato, M. (eds.) Logic, Language and Computation, Lecture Notes in Computer Science, vol. 792 (1994)"},{"key":"851_CR9","doi-asserted-by":"crossref","unstructured":"Hasegawa, R.: An analysis of divisibility orderings and recursive path orderings. In: Shyamasundar, R.K., Ueda, K. (eds.) Advances in Computing Science\u2014ASIAN\u201997, Lecture Notes in Computer Science, vol. 1345 (1997)","DOI":"10.1007\/3-540-63875-X_59"},{"key":"851_CR10","doi-asserted-by":"crossref","unstructured":"Weiermann, A.: A computation of the maximal order type of the term ordering on finite multisets. In: Ambos-Spies, K., L\u00f6we, B., Merkle, W. (eds.) Mathematical Theory and Computational Practice. CiE 2009, Lecture Notes in Computer Science, vol. 5635 (2009)","DOI":"10.1007\/978-3-642-03073-4_50"},{"key":"851_CR11","doi-asserted-by":"crossref","unstructured":"Simpson, S.G.: Nonprovability of certain combinatorial properties of finite trees. In: Harrington, L.A., Morley, M.D., S\u010d\u011bdrov, A., Simpson, S.G. (eds.) Harvey Friedman\u2019s Research on the Foundations of Mathematics, Studies in Logic and the Foundations of Mathematics, vol. 117, pp.\u00a087\u2013117. North-Holland (1985)","DOI":"10.1016\/S0049-237X(09)70156-9"},{"key":"851_CR12","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/BF02007558","volume":"25","author":"K Sch\u00fctte","year":"1985","unstructured":"Sch\u00fctte, K., Simpson, S.G.: Ein in der reinen Zahlentheorie unbeweisbarer Satz \u00fcber endliche Folgen von nat\u00fcrlichen Zahlen. Archiv f\u00fcr Mathematische Logik und Grundlagenforschung 25, 75\u201389 (1985)","journal-title":"Archiv f\u00fcr Mathematische Logik und Grundlagenforschung"},{"key":"851_CR13","unstructured":"van der Meeren, J.: Connecting the two worlds: well-partial-orders and ordinal notation systems, PhD thesis, Ghent University (2015)"},{"issue":"30","key":"851_CR14","doi-asserted-by":"publisher","first-page":"952","DOI":"10.1017\/S0960129520000298","volume":"8","author":"A Freund","year":"2020","unstructured":"Freund, A.: From Kruskal\u2019s theorem to Friedman\u2019s gap condition. Math. Struct. Comput. Sci. 8(30), 952\u2013975 (2020)","journal-title":"Math. Struct. Comput. Sci."},{"key":"851_CR15","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0168-0072(93)90192-G","volume":"60","author":"M Rathjen","year":"1993","unstructured":"Rathjen, M., Weiermann, A.: Proof-theoretic investigations on Kruskal\u2019s theorem. Ann. Pure Appl. Logic 60, 49\u201388 (1993)","journal-title":"Ann. Pure Appl. Logic"},{"key":"851_CR16","unstructured":"Freund, A.: Type-Two Well-Ordering Principles, Admissible Sets, and $${\\Pi }^1_1$$-Comprehension, PhD thesis, University of Leeds. http:\/\/etheses.whiterose.ac.uk\/20929\/ (2018)"},{"key":"851_CR17","doi-asserted-by":"crossref","unstructured":"Freund, A.: $${\\Pi }^1_1$$-comprehension as a well-ordering principle. Adv. Math. 355, article no.\u00a0106767, 65 pages (2019)","DOI":"10.1016\/j.aim.2019.106767"},{"issue":"5","key":"851_CR18","doi-asserted-by":"publisher","first-page":"801","DOI":"10.1112\/blms.12285","volume":"51","author":"A Freund","year":"2019","unstructured":"Freund, A.: A categorical construction of Bachmann\u2013Howard fixed points. Bull. Lond. Math. Soc. 51(5), 801\u2013814 (2019)","journal-title":"Bull. Lond. Math. Soc."},{"key":"851_CR19","doi-asserted-by":"crossref","unstructured":"Freund, A.: Computable aspects of the Bachmann\u2013Howard principle. J. Math. Logic 20(2), article no.\u00a02050006, 26 pages (2020)","DOI":"10.1142\/S0219061320500063"},{"key":"851_CR20","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1007\/s00153-017-0559-2","volume":"56","author":"J van der Meeren","year":"2017","unstructured":"van der Meeren, J., Rathjen, M., Weiermann, A.: Ordinal notation systems corresponding to Friedman\u2019s linearized well-partial-orders with gap-condition. Arch. Math. Logic 56, 607\u2013638 (2017)","journal-title":"Arch. Math. Logic"},{"issue":"2","key":"851_CR21","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1002\/malq.200910125","volume":"57","author":"A Weiermann","year":"2011","unstructured":"Weiermann, A., Wilken, G.: Ordinal arithmetic with simultaneously defined theta-functions. Math. Logic Q. 57(2), 116\u2013132 (2011)","journal-title":"Math. Logic Q."},{"issue":"1\u20132","key":"851_CR22","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/s00153-014-0408-5","volume":"54","author":"J van der Meeren","year":"2015","unstructured":"van der Meeren, J., Rathjen, M., Weiermann, A.: Well-partial-orderings and the big Veblen number. Arch. Math. Logic 54(1\u20132), 193\u2013230 (2015)","journal-title":"Arch. Math. Logic"},{"issue":"1\u20132","key":"851_CR23","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/s00153-016-0515-6","volume":"56","author":"J van der Meeren","year":"2017","unstructured":"van der Meeren, J., Rathjen, M., Weiermann, A.: An order-theoretic characterization of the Howard\u2013Bachmann\u2013hierarchy. Arch. Math. Logic 56(1\u20132), 79\u2013118 (2017)","journal-title":"Arch. Math. Logic"},{"issue":"1","key":"851_CR24","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1017\/jsl.2019.83","volume":"85","author":"A Freund","year":"2020","unstructured":"Freund, A.: Predicative collapsing principles. J. Symb. Logic 85(1), 511\u2013530 (2020)","journal-title":"J. Symb. Logic"},{"issue":"3","key":"851_CR25","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/1385-7258(77)90067-1","volume":"80","author":"D de Jongh","year":"1977","unstructured":"de Jongh, D., Parikh, R.: Well-partial orderings and hierarchies. Indagationes Mathematicae 80(3), 195\u2013207 (1977)","journal-title":"Indagationes Mathematicae"},{"key":"851_CR26","doi-asserted-by":"publisher","first-page":"27","DOI":"10.4064\/fm181-1-2","volume":"181","author":"M Aschenbrenner","year":"2004","unstructured":"Aschenbrenner, M., Pong, W.Y.: Orderings of monomial ideals. Fundamenta Mathematicae 181, 27\u201374 (2004)","journal-title":"Fundamenta Mathematicae"},{"key":"851_CR27","doi-asserted-by":"crossref","unstructured":"Knight, J.F.: Lange, K.: Lengths of developments in $$K((G))$$. Selecta Mathematica 25, article no.\u00a014, 36\u00a0pages (2019)","DOI":"10.1007\/s00029-019-0448-0"}],"container-title":["Archive for Mathematical Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00153-022-00851-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00153-022-00851-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00153-022-00851-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,29]],"date-time":"2023-11-29T16:09:19Z","timestamp":1701274159000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00153-022-00851-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,26]]},"references-count":27,"journal-issue":{"issue":"5-6","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["851"],"URL":"https:\/\/doi.org\/10.1007\/s00153-022-00851-5","relation":{},"ISSN":["0933-5846","1432-0665"],"issn-type":[{"type":"print","value":"0933-5846"},{"type":"electronic","value":"1432-0665"}],"subject":[],"published":{"date-parts":[[2022,10,26]]},"assertion":[{"value":"31 May 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 October 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 October 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}