Ordinal notation systems corresponding to Friedman’s linearized well-partial-orders with gap-condition. (English) Zbl 1417.03292
Summary: In this article we investigate whether the following conjecture is true or not: does the addition-free theta functions form a canonical notation system for the linear versions of Friedman’s well-partial-orders with the so-called gap-condition over a finite set of \(n\) labels. Rather surprisingly, we can show this is the case for two labels, but not for more than two labels. To this end, we determine the order type of the notation systems for addition-free theta functions in terms of ordinals less than \(\varepsilon _0\). We further show that the maximal order type of the Friedman ordering can be obtained by a certain ordinal notation system which is based on specific binary theta functions.
MSC:
| 03F15 | Recursive ordinals and ordinal notations |
| 03E10 | Ordinal and cardinal numbers |
| 06A06 | Partial orders, general |
Keywords:
well-partial-orderings; maximal order type; gap-embeddability relation; ordinal notation systems; collapsing functionReferences:
| [1] | Buchholz, W., Schütte, K.: Proof theory of impredicative subsystems of analysis, Studies in Proof Theory. Monographs, vol. 2. Bibliopolis, Naples (1988) · Zbl 0653.03039 |
| [2] | Buchholz, W.: A new system of proof-theoretic ordinal functions. Ann. Pure Appl. Log. 32(3), 195-207 (1986) · Zbl 0655.03038 · doi:10.1016/0168-0072(86)90052-7 |
| [3] | Buchholz, W.: An independence result for \[(\text{ II }_1^1 -\text{ CA }+\text{ BI }\] II11-CA+BI). Ann. Pure Appl. Log. 33(2), 131-155 (1987) · Zbl 0636.03052 · doi:10.1016/0168-0072(87)90078-9 |
| [4] | de Jongh, D.H.J., Parikh, R.: Well-partial orderings and hierarchies. Nederl. Akad. Wetensch. Proc. Ser. A 80 =. Indag. Math. 39(3), 195-207 (1977) · Zbl 0435.06004 |
| [5] | Van der Meeren, J.: Connecting the two worlds: Well-partial-orders and ordinal notation systems. Ph.D. thesis, Ghent University (2015) |
| [6] | Diestel, R.: Graph Theory, Graduate Texts in Mathematics, vol. 173, 4th edn. Springer, Heidelberg (2010) · Zbl 1204.05001 |
| [7] | Gordeev, L.: Systems of iterated projective ordinal notations and combinatorial statements about binary labeled trees. Arch. Math. Log. 29(1), 29-46 (1989) · Zbl 0691.03039 · doi:10.1007/BF01630809 |
| [8] | Higman, G.: Ordering by divisibility in abstract algebras. Proc. Lond. Math. Soc. 3(2), 326-336 (1952) · Zbl 0047.03402 · doi:10.1112/plms/s3-2.1.326 |
| [9] | Kruskal, J.B.: The theory of well-quasi-ordering: a frequently discovered concept. J. Comb. Theory Ser. A 13, 297-305 (1972) · Zbl 0244.06002 · doi:10.1016/0097-3165(72)90063-5 |
| [10] | Laver, R.: On Fraïssé’s order type conjecture. Ann. Math. 2(93), 89-111 (1971) · Zbl 0208.28905 · doi:10.2307/1970754 |
| [11] | Lee, G.: Binary trees and (maximal) order types. In: Computation and logic in the real world, Lecture Notes in Computer Science, vol. 4497, pp. 465-473. Springer, Berlin (2007) · Zbl 1151.03348 |
| [12] | Pohlers, W.: A short course in ordinal analysis. In: Proof theory (Leeds, 1990), pp. 27-78. Cambridge University Press, Cambridge (1992) · Zbl 0793.03063 |
| [13] | Rathjen, M., Weiermann, A.: Proof-theoretic investigations on Kruskal’s theorem. Ann. Pure Appl. Log. 60(1), 49-88 (1993) · Zbl 0786.03042 · doi:10.1016/0168-0072(93)90192-G |
| [14] | Schmidt, D.: Well-Partial Orderings and Their Maximal Order Types. Habilitationsschrift, Heidelberg (1979) |
| [15] | Schütte, K., Simpson, S.G.: Ein in der reinen Zahlentheorie unbeweisbarer Satz über endliche Folgen von natürlichen Zahlen. Arch. Math. Log. Grundl. 25(1-2), 75-89 (1985) · Zbl 0591.03041 · doi:10.1007/BF02007558 |
| [16] | Simpson, S.G.: Nonprovability of certain combinatorial properties of finite trees. In: Harvey Friedman’s Research on the Foundations of Mathematics, Studies in Logic and the Foundations of Mathematics, vol. 117, pp. 87-117. North-Holland, Amsterdam (1985) · Zbl 0691.03039 |
| [17] | Simpson, S.G.: Subsystems of Second Order Arithmetic, 2nd edn. Cambridge University Press, Cambridge (2009) · Zbl 1181.03001 · doi:10.1017/CBO9780511581007 |
| [18] | Takeuti, G.: Proof theory, Studies in Logic and the Foundations of Mathematics, vol. 81, second edn. North-Holland Publishing Co., Amsterdam (1987) With an appendix containing contributions by Georg Kreisel, Wolfram Pohlers. Stephen G, Simpson and Solomon Feferman · Zbl 0609.03019 |
| [19] | Van der Meeren, J., Rathjen, M., Weiermann, A.: Well-partial-orderings and the big Veblen number. Arch. Math. Log. 54(1-2), 193-230 (2015) · Zbl 1378.03041 |
| [20] | Van der Meeren, J., Rathjen, M., Weiermann, A.: An order-theoretic characterization of the Howard-Bachmann-hierachy. Available on arXiv (2014, Submitted to Journal) · Zbl 1421.03005 |
| [21] | Weiermann, A.: Well partial orderings and their strength measured in terms of their maximal order types. Summary of a talk given at the conference on computability, reverse mathematics and combinatorics in Banff 2008 |
| [22] | Weiermann, A., Wilken, G.: Ordinal arithmetic with simultaneously defined theta-functions. Math. Log. Q. 57(2), 116-132 (2011) · Zbl 1223.03036 · doi:10.1002/malq.200910125 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
