Well-partial-orderings and the big Veblen number

详细信息    查看全文

• 作者：Jeroen Van der Meeren (1)
  Michael Rathjen (2)
  Andreas Weiermann (1)
  
  1. Department of Mathematics ; Ghent University ; Krijgslaan 281 ; 9000 ; Gent ; Belgium
  2. Department of Pure Mathematics ; University of Leeds ; Leeds ; LS2 9JT ; UK
  
• 关键词：Well ; partial ; orderings ; Kruskal鈥檚 theorem ; Big Veblen number ; Ordinal notation systems ; Natural well ; orderings ; Maximal order type ; Collapsing function ; Recursively defined trees ; Tree ; embeddabilities ; 03F15 ; 03E10 ; 06A06
• 刊名：Archive for Mathematical Logic
• 出版年：2015
• 出版时间：February 2015
• 年：2015
• 卷：54
• 期：1-2
• 页码：193-230
• 全文大小：405 KB
• 参考文献：1. Kruskal, J.B.: The theory of well-quasi-ordering: a frequently discovered concept. J. Combin. Theory Ser. A 13, 297鈥?05 (1972) CrossRef
  2. Schmidt, D.: Well-Partial Orderings and Their Maximal Order Types. Habilitationsschrift, Heidelberg (1979)
  3. Simpson, S.G.: Nonprovability of certain combinatorial properties of finite trees. In: Harvey Friedman鈥檚 research on the foundations of mathematics, Stud. Logic Found. Math., vol. 117, pp. 87鈥?17. North-Holland, Amsterdam (1985)
  4. Rathjen, M., Weiermann, A.: Proof-theoretic investigations on Kruskal鈥檚 theorem. Ann. Pure Appl. Logic 60(1), 49鈥?8 (1993) CrossRef
  5. Schmidt, D.: Bounds for the closure ordinals of replete monotonic increasing functions. J. Symb. Logic 40(3), 305鈥?16 (1975) CrossRef
  6. Weiermann, A.: An order-theoretic characterization of the Sch眉tte鈥揤eblen-hierarchy. Math. Logic Q. 39(3), 367鈥?83 (1993) CrossRef
  7. Sch眉tte, K.: Kennzeichnung von Ordnungszahlen durch rekursiv erkl盲rte Funktionen. Math. Ann. 127, 15鈥?2 (1954) CrossRef
  8. Veblen, O.: Continuous increasing functions of finite and transfinite ordinals. Trans. Am. Math. Soc. 9(3), 280鈥?92 (1908) CrossRef
  9. K艡铆啪, I.: Well-quasiordering finite trees with gap-condition. Proof of Harvey Friedman鈥檚 conjecture. Ann. Math. (2) 130(1), 215鈥?26 (1989) CrossRef
  10. Gordeev, L.: Generalizations of the Kruskal鈥揊riedman theorems. J. Symb. Logic 55(1), 157鈥?81 (1990) CrossRef
  11. de Jongh, D.H.J., Parikh, R.: Well-partial orderings and hierarchies. Nederl. Akad. Wetensch. Proc. Ser. A 80 = Indag. Math. 39(3), 195鈥?07 (1977) CrossRef
  12. Aschenbrenner, M., Pong, W.Y.: Orderings of monomial ideals. Fund. Math. 181(1), 27鈥?4 (2004) CrossRef
  13. Weiermann, A.: Proving termination for term rewriting systems. In: Computer Science Logic (Berne, 1991), Lecture Notes in Computer Science, vol. 626, pp. 419鈥?28. Springer, Berlin (1992)
  14. Weiermann, A.: A computation of the maximal order type of the term ordering on finite multisets. In: Mathematical Theory and Computational Practice, Lecture Notes in Computer Science, vol. 5635, pp. 488鈥?98. Springer, Berlin (2009)
  15. Buchholz, W., Sch眉tte, K.: Proof Theory of Impredicative Subsystems of Analysis, Studies in Proof Theory. Monographs, vol. 2. Bibliopolis, Naples (1988)
  16. Weiermann, A.: Complexity bounds for some finite forms of Kruskal鈥檚 theorem. J. Symb. Comput. 18(5), 463鈥?88 (1994) CrossRef
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Mathematical Logic and Foundations
  Mathematics
  Algebra
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1432-0665

文摘

In this article we characterize a countable ordinal known as the big Veblen number in terms of natural well-partially ordered tree-like structures. To this end, we consider generalized trees where the immediate subtrees are grouped in pairs with address-like objects. Motivated by natural ordering properties, extracted from the standard notations for the big Veblen number, we investigate different choices for embeddability relations on the generalized trees. We observe that for addresses using one finite sequence only, the embeddability coincides with the classical tree-embeddability, but in this article we are interested in more general situations (transfinite addresses and well-partially ordered addresses). We prove that the maximal order type of some of these new embeddability relations hit precisely the big Veblen ordinal \({\vartheta \Omega^{\Omega}}\) . Somewhat surprisingly, changing a little bit the well-partially ordered addresses (going from multisets to finite sequences), the maximal order type hits an ordinal which exceeds the big Veblen number by far, namely \({\vartheta \Omega^{\Omega^\Omega}}\) . Our results contribute to the research program (originally initiated by Diana Schmidt) on classifying properties of natural well-orderings in terms of order-theoretic properties of the functions generating the orderings.