Hostname: page-component-586b7cd67f-rcrh6 Total loading time: 0 Render date: 2024-11-24T12:36:13.206Z Has data issue: false hasContentIssue false
  • English
  • Français

From Kruskal’s theorem to Friedman’s gap condition

Published online by Cambridge University Press:  29 January 2021

Anton Freund Open the ORCID record for Anton Freund [Opens in a new window]
Anton Freund*
Affiliation:
Fachbereich Mathematik, Technische Universität Darmstadt, Schlossgartenstr. 7, 64289 Darmstadt, Germany
*
*Corresponding author. Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Harvey Friedman’s 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.

Keywords

Kruskal’s theoremFriedman’s gap conditionlabelled treeswell partial ordersdilators-comprehension
Type
Paper
Information
Mathematical Structures in Computer Science , Volume 30 , Issue 8 , September 2020 , pp. 952 - 975
Check for updates
Copyright
© The Author(s), 2021. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Dershowitz, N. (1982). Orderings for term-rewriting systems. Theoretical Computer Science 17 279–301.CrossRefGoogle Scholar
Ehrhard, T. and Regnier, L. (2003). The differential lambda-calculus. Theoretical Computer Science 309 1–41.CrossRefGoogle Scholar
Freund, A. (2019a). $\Pi _1^1$-comprehension as a well-ordering principle. Advances in Mathematics 355. Article no. 106767, 65 pp.CrossRefGoogle Scholar
Freund, A. (2019b). A categorical construction of Bachmann-Howard fixed points. Bulletin of the London Mathematical Society 51 (5) 801–814.CrossRefGoogle Scholar
Freund, A. (2020). Computable aspects of the Bachmann-Howard principle. Journal of Mathematical Logic 20 (2). Article no. 2050006, 26 pp.CrossRefGoogle Scholar
Freund, A. and Rathjen, M. (2021). Derivatives of normal functions in reverse mathematics. Annals of Pure and Applied Logic 172 (2). Article no. 102890, 49 pp.CrossRefGoogle Scholar
Freund, A., Rathjen, M. and Weiermann, A. (2020). Minimal bad sequences are necessary for a uniform Kruskal theorem. Preprint available as arXiv:2001.06380.Google Scholar
Friedman, H., Robertson, N. and Seymour, P. (1987). Metamathematics of the graph minor theorem. In: Simpson, S. (ed.) Logic and Combinatorics, Contemporary Mathematics, vol. 65, American Mathematical Society, 229–261.Google Scholar
Gallier, J. (1991). What’s so special about Kruskal’s theorem and the ordinal Γ0? A survey of some results in proof theory. Annals of Pure and Applied Logic 53 199–260.CrossRefGoogle Scholar
Girard, J.-Y. (1981). $\Pi _2^1$-logic, part 1: Dilators. Annals of Pure and Applied Logic 21 75–219.Google Scholar
Gordeev, L. (1990). Generalizations of the Kruskal-Friedman theorems. The Journal of Symbolic Logic 55 (1) 157–181.CrossRefGoogle Scholar
Haase, C., Schmitz, S. and Schnoebelen, P. (2013). The power of priority channel systems. In: D’Argenio, P. and Melgratti, H. (eds.) CONCUR 2013 — Concurrency Theory, Lecture Notes in Computer Science, vol. 8052, Springer, 319–333.Google Scholar
Hasegawa, R. (1997). An analysis of divisibility orderings and recursive path orderings. In: Shyamasundar, R. and Ueda, K. (eds.) Advances in Computing Science — ASIAN’97, Lecture Notes in Computer Science, vol. 1345, 283–296.CrossRefGoogle Scholar
Hasegawa, R. (2002). Two applications of analytic functors. Theoretical Computer Science 272 113–175.CrossRefGoogle Scholar
Kříž, I. (1989). Well-quasiordering finite trees with gap-condition. Proof of Harvey Friedman’s conjecture. Annals of Mathematics 130 (1) 215–226.CrossRefGoogle Scholar
Kruskal, J. (1960). Well-quasi-ordering, the tree theorem, and Vazsonyi’s conjecture. Transactions of the American Mathematical Society 95 (2) 210–225.Google Scholar
Nash-Williams, C. S. (1963). On well-quasi-ordering finite trees. Proceedings of the Cambridge Philosophical Society 59 833–835.CrossRefGoogle Scholar
Ogawa, M. (1995). Simple gap termination on term graph rewriting systems. Research report, RIMS, Kyoto University. http://www.kurims.kyoto-u.ac.jp/kyodo/kokyuroku/contents/pdf/0918-10.pdf (accessed 23.09.2020).Google Scholar
Rathjen, M. (1999). The realm of ordinal analysis. In: Cooper, S. and Truss, J. (eds.) Sets and Proofs, London Mathematical Society Lecture Note Series, Cambridge University Press, 219–280.Google Scholar
Rathjen, M. and Weiermann, A. (1993). Proof-theoretic investigations on Kruskal’s theorem. Annals of Pure and Applied Logic 60 49–88.CrossRefGoogle Scholar
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–391. Originally Habilitationsschrift, Universität Heidelberg, 1979.Google Scholar
Simpson, S. (1985). Nonprovability of certain combinatorial properties of finite trees. In: Harrington, L. A., Morley, M. D., Sčědrov, A., and Simpson, S. G. (eds.) Harvey Friedman’s Research on the Foundations of Mathematics, Studies in Logic and the Foundations of Mathematics, vol. 117, North-Holland, 87–117.Google Scholar
Simpson, S. (2009). Subsystems of Second Order Arithmetic, Perspectives in Logic, Cambridge University Press, Cambridge.Google Scholar
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).Google Scholar
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).Google Scholar
van der Meeren, J., Rathjen, M. and Weiermann, A. (2015). Well-partial-orderings and the big Veblen number. Archive for Mathematical Logic 54 (1–2) 193–230.CrossRefGoogle Scholar
van der Meeren, J., Rathjen, M. and Weiermann, A. (2017a). An order-theoretic characterization of the Howard-Bachmann-hierarchy. Archive for Mathematical Logic 56 (1–2) 79–118.CrossRefGoogle Scholar
van der Meeren, J., Rathjen, M. and Weiermann, A. (2017b). Ordinal notation systems corresponding to Friedman’s linearized well-partial-orders with gap-condition. Archive for Mathematical Logic 56 607–638.Google Scholar