{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,13]],"date-time":"2024-09-13T18:10:13Z","timestamp":1726251013111},"reference-count":37,"publisher":"Oxford University Press (OUP)","issue":"6","license":[{"start":{"date-parts":[[2023,2,16]],"date-time":"2023-02-16T00:00:00Z","timestamp":1676505600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,9,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Transformations of well partial orders induce functions on the ordinals, via the notion of maximal order type. In most examples from the literature, these functions are not normal, in marked contrast with the central role that normal functions play in ordinal analysis and related work from computability theory. The present paper aims to explain this phenomenon. In order to do so, we investigate a rich class of order transformations that are known as $\\textsf {WPO}$-dilators. According to a first main result of this paper, $\\textsf {WPO}$-dilators induce normal functions when they satisfy a rather restrictive condition, which we call strong normality. Moreover, the reverse implication holds as well, for reasonably well-behaved $\\textsf {WPO}$-dilators. Strong normality also allows us to explain another phenomenon: by previous work of Freund, Rathjen and Weiermann, a uniform Kruskal theorem for $\\textsf {WPO}$-dilators is as strong as $\\varPi ^1_1$-comprehension, while the corresponding result for normal dilators on linear orders is equivalent to the much weaker principle of $\\varPi ^1_1$-induction. As our second main result, we show that $\\varPi ^1_1$-induction is equivalent to the uniform Kruskal theorem for $\\textsf {WPO}$-dilators that are strongly normal.<\/jats:p>","DOI":"10.1093\/logcom\/exad002","type":"journal-article","created":{"date-parts":[[2023,2,17]],"date-time":"2023-02-17T01:04:21Z","timestamp":1676595861000},"page":"1064-1081","source":"Crossref","is-referenced-by-count":0,"title":["Normal functions and maximal order types"],"prefix":"10.1093","volume":"34","author":[{"given":"Anton","family":"Freund","sequence":"first","affiliation":[{"name":"Department of Mathematics, Technical University of Darmstadt , Schlossgartenstr. 7, 64289 Darmstadt, Germany"}]},{"given":"Davide","family":"Manca","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Technical University of Darmstadt , Schlossgartenstr. 7, 64289 Darmstadt, Germany"}]}],"member":"286","published-online":{"date-parts":[[2023,2,16]]},"reference":[{"volume-title":"Mathematical Problems in Logic","year":"1966","author":"Aczel","key":"2024091304303055400_ref1"},{"key":"2024091304303055400_ref2","first-page":"430","article-title":"Normal functors on linear orderings","volume":"32","author":"Aczel","year":"1967","journal-title":"The Journal of Symbolic Logic"},{"key":"2024091304303055400_ref3","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1016\/j.apal.2009.01.001","article-title":"Reverse mathematics and well-ordering principles: a pilot study","volume":"160","author":"Afshari","year":"2009","journal-title":"Annals of Pure and Applied Logic"},{"key":"2024091304303055400_ref4","doi-asserted-by":"crossref","first-page":"3973","DOI":"10.1090\/proc\/15859","article-title":"Boundedness theorems for flowers and sharps","volume":"150","author":"Aguilera","year":"2022","journal-title":"Proceedings of the American Mathematical Society"},{"key":"2024091304303055400_ref5","doi-asserted-by":"crossref","first-page":"27","DOI":"10.4064\/fm181-1-2","article-title":"Orderings of monomial ideals","volume":"181","author":"Aschenbrenner","year":"2004","journal-title":"Fundamenta Mathematicae"},{"key":"2024091304303055400_ref6","doi-asserted-by":"crossref","first-page":"683","DOI":"10.2178\/jsl\/1096901762","article-title":"Reverse mathematics and the equivalence of definitions for well and better quasi-orders","volume":"69","author":"Cholak","year":"2004","journal-title":"The Journal of Symbolic Logic"},{"key":"2024091304303055400_ref7","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1145\/359138.359142","article-title":"Proving termination with multiset orderings","volume":"22","author":"Dershowitz","year":"1979","journal-title":"Communications of the ACM"},{"key":"2024091304303055400_ref8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2307\/2269764","article-title":"Systems of predicative analysis","volume":"29","author":"Feferman","year":"1964","journal-title":"The Journal of Symbolic Logic"},{"key":"2024091304303055400_ref9","doi-asserted-by":"crossref","DOI":"10.1017\/bsl.2018.80","volume-title":"Type-Two Well-Ordering Principles, Admissible Sets, and","author":"Freund","year":"2018"},{"key":"2024091304303055400_ref10","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1016\/j.aim.2019.106767","article-title":"${\\varPi }_1^1$-comprehension as a well-ordering principle","volume":"355","author":"Freund","year":"2019","journal-title":"Advances in Mathematics"},{"key":"2024091304303055400_ref11","doi-asserted-by":"crossref","first-page":"article no. 2050006","DOI":"10.1142\/S0219061320500063","article-title":"Computable aspects of the Bachmann\u2013Howard principle","volume":"20","author":"Freund","year":"2020","journal-title":"Journal of Mathematical Logic"},{"key":"2024091304303055400_ref12","doi-asserted-by":"crossref","first-page":"709","DOI":"10.1017\/jsl.2020.24","article-title":"How strong are single fixed points of normal functions","volume":"85","author":"Freund","year":"2020","journal-title":"The Journal of Symbolic Logic"},{"key":"2024091304303055400_ref13","doi-asserted-by":"crossref","DOI":"10.1007\/s00153-022-00851-5","article-title":"Bachmann\u2013Howard derivatives","volume-title":"Archive for Mathematical Logic","author":"Freund"},{"key":"2024091304303055400_ref14","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/j.apal.2020.102890","article-title":"Derivatives of normal functions in reverse mathematics","volume":"172","author":"Freund","year":"2021","journal-title":"Annals of Pure and Applied Logic"},{"key":"2024091304303055400_ref15","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1016\/j.aim.2022.108265","article-title":"Minimal bad sequences are necessary for a uniform Kruskal theorem","volume":"400","author":"Freund","year":"2022","journal-title":"Advances in Mathematics"},{"key":"2024091304303055400_ref16","first-page":"75","article-title":"${\\varPi }_2^1$-logic, part 1: dilators","volume":"21","author":"Girard","year":"1981","journal-title":"Annals of Pure and Applied Logic"},{"key":"2024091304303055400_ref17","article-title":"Studies in Proof Theory","volume-title":"Proof Theory and Logical Complexity","author":"Girard","year":"1987"},{"key":"2024091304303055400_ref18","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0032399","article-title":"Well-ordering of algebras and Kruskal\u2019s theorem","volume-title":"Logic, Language and Computation","author":"Hasegawa","year":"1994"},{"key":"2024091304303055400_ref19","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0168-0072(94)90076-0","article-title":"Reverse mathematics and ordinal exponentiation","volume":"66","author":"Hirst","year":"1994","journal-title":"Annals of Pure and Applied Logic"},{"key":"2024091304303055400_ref20","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/1385-7258(77)90067-1","article-title":"Well-partial orderings and hierarchies","volume":"80","author":"de Jongh","year":"1977","journal-title":"Indagationes Mathematicae"},{"key":"2024091304303055400_ref21","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1016\/j.apal.2009.01.007","article-title":"On Fra\u00efss\u00e9\u2019s conjecture for linear orders of finite Hausdorff rank","volume":"160","author":"Marcone","year":"2009","journal-title":"Annals of Pure and Applied Logic"},{"key":"2024091304303055400_ref22","doi-asserted-by":"crossref","first-page":"575","DOI":"10.2178\/jsl\/1305810765","article-title":"The Veblen functions for computability theorists","volume":"76","author":"Marcone","year":"2011","journal-title":"The Journal of Symbolic Logic"},{"volume-title":"Connecting the Two Worlds: Well-partial-orders and Ordinal Notation Systems","year":"2015","author":"van der Meeren","key":"2024091304303055400_ref23"},{"key":"2024091304303055400_ref24","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1007\/s00153-014-0408-5","article-title":"Well-partial-orderings and the big Veblen number","volume":"54","author":"van der Meeren","year":"2015","journal-title":"Archive for Mathematical Logic"},{"key":"2024091304303055400_ref25","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/s00153-016-0515-6","article-title":"An order-theoretic characterization of the Howard\u2013Bachmann-hierarchy","volume":"56","author":"van der Meeren","year":"2017","journal-title":"Archive for Mathematical Logic"},{"key":"2024091304303055400_ref26","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/s11083-007-9058-0","article-title":"Computable linearizations of well-partial-orderings","volume":"24","author":"Montalb\u00e1n","year":"2007","journal-title":"Order"},{"key":"2024091304303055400_ref27","first-page":"179","article-title":"$\\omega $-models and well-ordering principles","volume-title":"Foundational Adventures: Essays in Honor of Harvey M. Friedman","author":"Rathjen","year":"2014"},{"key":"2024091304303055400_ref28","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/0168-0072(93)90192-G","article-title":"Proof-theoretic investigations on Kruskal\u2019s theorem","volume":"60","author":"Rathjen","year":"1993","journal-title":"Annals of Pure and Applied Logic"},{"key":"2024091304303055400_ref29","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1142\/9781848162778_0011","article-title":"Reverse mathematics and well-ordering principles","volume-title":"Computability in Context: Computation and Logic in the Real World","author":"Rathjen","year":"2011"},{"key":"2024091304303055400_ref30","doi-asserted-by":"crossref","first-page":"305","DOI":"10.2307\/2272156","article-title":"Bounds for the closure ordinals of replete monotonic increasing functions","volume":"40","author":"Schmidt","year":"1975","journal-title":"The Journal of Symbolic Logic"},{"key":"2024091304303055400_ref31","doi-asserted-by":"crossref","first-page":"351","DOI":"10.1007\/978-3-030-30229-0_13","article-title":"Well-partial orderings and their maximal order types","volume-title":"Well-Quasi Orders in Computation, Logic, Language and Reasoning","author":"Schmidt","year":"2020"},{"key":"2024091304303055400_ref32","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1007\/BF01972460","article-title":"Eine Grenze f\u00fcr die Beweisbarkeit der transfiniten Induktion in der verzweigten Typenlogik","volume":"7","author":"Sch\u00fctte","year":"1964","journal-title":"Archiv f\u00fcr mathematische Logik und Grundlagenforschung"},{"key":"2024091304303055400_ref33","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/S0049-237X(09)70156-9","article-title":"Nonprovability of certain combinatorial properties of finite trees","volume-title":"Harvey Friedman\u2019s Research on the Foundations of Mathematics","author":"Simpson","year":"1985"},{"key":"2024091304303055400_ref34","doi-asserted-by":"crossref","first-page":"961","DOI":"10.2307\/2274585","article-title":"Ordinal numbers and the Hilbert basis theorem","volume":"53","author":"Simpson","year":"1988","journal-title":"The Journal of Symbolic Logic"},{"key":"2024091304303055400_ref35","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511581007","article-title":"Subsystems of second order arithmetic","volume-title":"Perspectives in Logic","author":"Simpson","year":"2009"},{"key":"2024091304303055400_ref36","first-page":"419","article-title":"Proving termination for term rewriting systems","volume-title":"Computer Science Logic. CSL 1991","author":"Weiermann","year":"1992"},{"key":"2024091304303055400_ref37","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-03073-4_50","article-title":"A computation of the maximal order type of the term ordering on finite multisets","volume-title":"Mathematical Theory and Computational Practice. CiE 2009","author":"Weiermann","year":"2009"}],"container-title":["Journal of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/34\/6\/1064\/59088557\/exad002.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/34\/6\/1064\/59088557\/exad002.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,13]],"date-time":"2024-09-13T17:19:03Z","timestamp":1726247943000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/logcom\/article\/34\/6\/1064\/7043024"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,16]]},"references-count":37,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2023,2,16]]},"published-print":{"date-parts":[[2024,9,6]]}},"URL":"https:\/\/doi.org\/10.1093\/logcom\/exad002","relation":{},"ISSN":["0955-792X","1465-363X"],"issn-type":[{"type":"print","value":"0955-792X"},{"type":"electronic","value":"1465-363X"}],"subject":[],"published-other":{"date-parts":[[2024,9]]},"published":{"date-parts":[[2023,2,16]]}}}