×

zbMATH — the first resource for mathematics

On ordinal invariants in well quasi orders and finite antichain orders. (English) Zbl 07218737
Schuster, Peter M. (ed.) et al., Well-quasi orders in computation, logic, language and reasoning. A unifying concept of proof theory, automata theory, formal languages and descriptive set theory. Based on the minisymposium on well-quasi orders: from theory to applications within the Jahrestagung der Deutschen Mathematiker-Vereinigung (DMV), Hamburg, Germany, September 21–25, 2015 and the Dagstuhl seminar 16031 on well quasi-orders in computer science, Schloss Dagstuhl, Germany, January 17–22, 2016. Cham: Springer (ISBN 978-3-030-30228-3/hbk; 978-3-030-30229-0/ebook). Trends in Logic – Studia Logica Library 53, 29-54 (2020).
Summary: We investigate the ordinal invariants height, length, and width of well quasi orders (WQO), with particular emphasis on width, an invariant of interest for the larger class of orders with finite antichain condition (FAC). We show that the width in the class of FAC orders is completely determined by the width in the class of WQOs, in the sense that if we know how to calculate the width of any WQO then we have a procedure to calculate the width of any given FAC order. We show how the width of WQO orders obtained via some classical constructions can sometimes be computed in a compositional way. In particular this allows proving that every ordinal can be obtained as the width of some WQO poset. One of the difficult questions is to give a complete formula for the width of Cartesian products of WQOs. Even the width of the product of two ordinals is only known through a complex recursive formula. Although we have not given a complete answer to this question we have advanced the state of knowledge by considering some more complex special cases and in particular by calculating the width of certain products containing three factors. In the course of writing the paper we have discovered that some of the relevant literature was written on cross-purposes and some of the notions re-discovered several times. Therefore we also use the occasion to give a unified presentation of the known results.
For the entire collection see [Zbl 1443.03002].
MSC:
03E Set theory
06A Ordered sets
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abraham, U. (1987). A note on Dilworth’s theorem in the infinite case. Order, 4(2), 107-125. https://doi.org/10.1007/BF00337691. · Zbl 0629.06002
[2] Abraham, U., & Bonnet, R. (1999). Hausdorff’s theorem for posets that satisfy the finite antichain property. Fundamenta Mathematicae, 159(1), 51-69. · Zbl 0934.06005
[3] Abraham, U., Bonnet, R., Cummings, J., Džamonja, M., & Thompson, K. (2012). A scattering of orders. Transactions of the American Mathematical Society, 364(12), 6259-6278. https://doi.org/10.1090/S0002-9947-2012-05466-3. · Zbl 1297.06004
[4] Blass, A., & Gurevich, Y. (2008). Program termination and well partial orderings. ACM Transactions on Computational Logic, 9(3), 18. https://doi.org/10.1145/1352582.1352586. · Zbl 1367.68061
[5] Dilworth, R. P. (1950). A decomposition theorem for partially ordered sets. Annals of Mathematics, 51(1), 161-166. https://doi.org/10.2307/1969503. · Zbl 0038.02003
[6] Dushnik, B., & Miller, E. W. (1941). Partially ordered sets. American Journal of Mathematics, 63(3), 600-610. https://doi.org/10.2307/2371374. · Zbl 0025.31002
[7] Higman, G. (1952). Ordering by divisibility in abstract algebras. Proceedings of the London Mathematical Society, 3(2), 326-336. https://doi.org/10.1112/plms/s3-2.1.326. · Zbl 0047.03402
[8] de Jongh, D. H. J., & Parikh, R. (1977). Well-partial orderings and hierarchies. Indagationes Mathematicae (Proceedings), 39(3):195-207. https://doi.org/10.1016/1385-7258(77)90067-1. · Zbl 0435.06004
[9] Kříž, I., Thomas, R. (1990). Ordinal types in Ramsey theory and well-partial-ordering theory. In J. Nešetřil & V. Rödl (Eds.), Algorithms and Combinatorics: Mathematics of Ramsey Theory (Vol. 5, pp 57-95). Springer. https://doi.org/10.1007/978-3-642-72905-8_7. · Zbl 0752.05057
[10] Kruskal, J. (1960). Well-quasi-ordering, the Tree theorem, and Vazsonyi’s conjecture. Transactions of the American Mathematical Society, 95(2), 210-225. https://doi.org/10.2307/1993287. · Zbl 0158.27002
[11] Kruskal, J. B. (1972). The theory of well-quasi-ordering: A frequently discovered concept. Journal of Combinatorial Theory, Series A, 13(3), 297-305. https://doi.org/10.1016/0097-3165(72)90063-5. · Zbl 0244.06002
[12] Laver, R. (1976). Well-quasi-orderings and sets of finite sequences. In Mathematical Proceedings of the Cambridge Philosophical Society (Vol. 79, No. 1, pp. 1-10). https://doi.org/10.1017/S030500410005204X. · Zbl 0405.06001
[13] Van der Meeren, J. (2015). Connecting the two worlds: Well-partial-orders and ordinal notation systems. Ph.D. thesis, Universiteit Gent.
[14] Van der Meeren, J., Rathjen, M., & Weiermann, A. (2015). Well-partial-orderings and the big Veblen number. Archive for Mathematical Logic, 54(1-2), 193-230. https://doi.org/10.1007/s00153-014-0408-5. · Zbl 1378.03041
[15] Milner, E. C. (1985). Basic wqo- and bqo-theory. In Graphs and order (Banff, Alta., 1984), NATO Advanced Science Institutes Series C: Mathematical and Physical Sciences (Vol. 147, pp. 487-502). Dordrecht: Reidel. https://doi.org/10.1007/978-94-009-5315-4_14.
[16] Milner, E. C., & Sauer, N. (1981). On chains and antichains in well founded partially ordered sets. Journal of the London Mathematical Society, 2(1), 15-33. https://doi.org/10.1112/jlms/s2-24.1.15. · Zbl 0483.04005
[17] Mirsky, L. (1971). A dual of Dilworth’s decomposition theorem. American Mathematical Monthly, 78(8), 876-877. https://doi.org/10.2307/2316481. · Zbl 0263.06002
[18] Perles, M. A. (1963). On Dilworth’s theorem in the infinite case. Israel Journal of Mathematics, 1(2), 108-109. https://doi.org/10.1007/BF02759806. · Zbl 0115.01703
[19] Pouzet, M. (1979). Sur les chaînes d’un ensemble partiellement bien ordonné. Publ Dép Math Lyon, 16(1), 21-26. http://www.numdam.org/article/PDML_1979__16_1_21_0.pdf. · Zbl 0451.06007
[20] Rado, R. (1954). Partial well-ordering of sets of vectors. Mathematika, 1(2), 89-95. https://doi.org/10.1112/S0025579300000565. · Zbl 0057.04302
[21] Rathjen, M., & Weiermann, A. (1993). Proof-theoretic investigations on Kruskal’s theorem. Annals of Pure and Applied Logic, 60(1), 49-88. https://doi.org/10.1016/0168-0072(93)90192-G. · Zbl 0786.03042
[22] Schmerl, J. H. (2002). Obstacles to extending Mirsky’s theorem. Order, 19(2), 209-211. https://doi.org/10.1023/A:1016541101728. · Zbl 1008.06002
[23] Schmidt, D. (1979). Well-partial orderings and their maximal order types. Heidelberg: Habilitationsschrift.
[24] Schmidt, D. (1981). The relation between the height of a well-founded partial ordering and the order types of its chains and antichains. Journal of Combinatorial Theory, Series B, 31(2), 183-189. https://doi.org/10.1016/S0095-8956(81)80023-8. · Zbl 0443.06002
[25] Schmitz, S., Schnoebelen, Ph. (2011). Multiply-recursive upper bounds with Higman’s lemma. In Proceeding of the ICALP 2011. Lecture Notes in Computer Science (Vol. 6756, pp. 441-452). Springer. https://doi.org/10.1007/978-3-642-22012-8_35. · Zbl 1333.68179
[26] Weiermann, A. (2009). A computation of the maximal order type of the term ordering on finite multisets. In Proceedings of CiE-2009. Lecture Notes in Computer Science (Vol. 5635, pp. 488-498). Springer. https://doi.org/10.1007/978-3-642-03073-4_50 · Zbl 1268.03064
[27] West, D. B. (1982). Extremal problems in partially ordered sets. In Rival, I. (Ed.), Ordered Sets, NATO Advanced Study Institutes Series (Vol. 83, pp. 473-521). Springer. https://doi.org/10.1007/978-94-009-7798-3_16.
[28] Wolk, E. · Zbl 0153.02601
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.