Partitioning 𝛼–large sets: Some lower bounds

Bigorajska, Teresa; Kotlarski, Henryk

doi:10.1090/S0002-9947-06-03883-9

Partitioning $\alpha$–large sets: Some lower bounds
HTML articles powered by AMS MathViewer

by Teresa Bigorajska and Henryk Kotlarski PDF

Trans. Amer. Math. Soc. 358 (2006), 4981-5001 Request permission

Abstract:

Let $\alpha \rightarrow (\beta )_m^r$ denote the property: if $A$ is an $\alpha$–large set of natural numbers and $[A]^r$ is partitioned into $m$ parts, then there exists a $\beta$–large subset of $A$ which is homogeneous for this partition. Here the notion of largeness is in the sense of the so–called Hardy hierarchy. We give a lower bound for $\alpha$ in terms of $\beta ,m,r$ for some specific $\beta$.

References

Jeremy Avigad and Richard Sommer, A model-theoretic approach to ordinal analysis, Bull. Symbolic Logic 3 (1997), no. 1, 17–52. MR 1444913, DOI 10.2307/421195
Teresa Bigorajska and Henryk Kotlarski, A partition theorem for $\alpha$-large sets, Fund. Math. 160 (1999), no. 1, 27–37. MR 1694401, DOI 10.4064/fm-160-1-27-37
Teresa Bigorajska and Henryk Kotlarski, Some combinatorics involving $\xi$-large sets, Fund. Math. 175 (2002), no. 2, 119–125. MR 1969630, DOI 10.4064/fm175-2-2
Wilfried Buchholz, Adam Cichon, and Andreas Weiermann, A uniform approach to fundamental sequences and hierarchies, Math. Logic Quart. 40 (1994), no. 2, 273–286. MR 1271290, DOI 10.1002/malq.19940400212
Peter A. Cholak, Carl G. Jockusch, and Theodore A. Slaman, On the strength of Ramsey’s theorem for pairs, J. Symbolic Logic 66 (2001), no. 1, 1–55. MR 1825173, DOI 10.2307/2694910
E. A. Cichon, A short proof of two recently discovered independence results using recursion theoretic methods, Proc. Amer. Math. Soc. 87 (1983), no. 4, 704–706. MR 687646, DOI 10.1090/S0002-9939-1983-0687646-0
M. V. H. Fairtlough and S. S. Wainer, Ordinal complexity of recursive definitions, Inform. and Comput. 99 (1992), no. 2, 123–153. MR 1172210, DOI 10.1016/0890-5401(92)90027-D
Matt Fairtlough and Stanley S. Wainer, Hierarchies of provably recursive functions, Handbook of proof theory, Stud. Logic Found. Math., vol. 137, North-Holland, Amsterdam, 1998, pp. 149–207. MR 1640327, DOI 10.1016/S0049-237X(98)80018-9
Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer, Ramsey theory, 2nd ed., Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1990. A Wiley-Interscience Publication. MR 1044995
Jussi Ketonen and Robert Solovay, Rapidly growing Ramsey functions, Ann. of Math. (2) 113 (1981), no. 2, 267–314. MR 607894, DOI 10.2307/2006985
Henryk Kotlarski and Bożena Piekart, Some variations of the Hardy hierarchy, MLQ Math. Log. Q. 51 (2005), no. 4, 417–434. MR 2150370, DOI 10.1002/malq.200410043
Kotlarski, H., Piekart, B., Weiermann, A., More on lower bounds for partitioning $\alpha$-large sets, submitted to Annals of Pure and Applied Logic.
Henryk Kotlarski and Zygmunt Ratajczyk, Inductive full satisfaction classes, Ann. Pure Appl. Logic 47 (1990), no. 3, 199–223. MR 1058297, DOI 10.1016/0168-0072(90)90035-Z
Henryk Kotlarski and Zygmunt Ratajczyk, More on induction in the language with a satisfaction class, Z. Math. Logik Grundlag. Math. 36 (1990), no. 5, 441–454. MR 1090318, DOI 10.1002/malq.19900360509
Kuratowski, K., Mostowski, A., Set theory. Państwowe Wydawnictwo Naukowe, 1976.
Martin Loebl and Jaroslav Ne et il, An unprovable Ramsey-type theorem, Proc. Amer. Math. Soc. 116 (1992), no. 3, 819–824. MR 1095225, DOI 10.1090/S0002-9939-1992-1095225-4
Paris, J., Harrington, L., A mathematical incompleteness in Peano arithmetic, in: Handbook of mathematical logic (J. Barwise, editor), North-Holland Publ. Comp. 1977, pp. 1133–1142.
Z. Ratajczyk, A combinatorial analysis of functions provably recursive in $\textrm {I}\Sigma _n$, Fund. Math. 130 (1988), no. 3, 191–213. MR 970904, DOI 10.4064/fm-130-3-191-213
Z. Ratajczyk, Subsystems of true arithmetic and hierarchies of functions, Ann. Pure Appl. Logic 64 (1993), no. 2, 95–152. MR 1241251, DOI 10.1016/0168-0072(93)90031-8
Sommer, R., Transfinite induction and hierarchies of functions generated by transfinite recursion within Peano arithmetic, Ph.D. thesis, University of California, Berkeley, 1990.
Richard Sommer, Transfinite induction within Peano arithmetic, Ann. Pure Appl. Logic 76 (1995), no. 3, 231–289. MR 1366513, DOI 10.1016/0168-0072(95)00029-G
Andreas Weiermann, A classification of rapidly growing Ramsey functions, Proc. Amer. Math. Soc. 132 (2004), no. 2, 553–561. MR 2022381, DOI 10.1090/S0002-9939-03-07086-2
Weiermann, A., Classifying the phase transition for DENSE(2,2), in preparation.