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.
Additional Information
- Teresa Bigorajska
- Affiliation: Faculty of Mathematics, Cardinal Stefan Wyszyński University, ul. Dewajtis 5, 01–815 Warszawa, Poland
- Email: tebigo@op.pl
- Henryk Kotlarski
- Affiliation: Faculty of Mathematics, Cardinal Stefan Wyszyński University, ul. Dewajtis 5, 01–815 Warszawa, Poland – and – Institute of Mathematics, Polish Academy of Sciences, ul. Śniadeckich 8, P.O. Box 137, 00–950 Warszawa, Poland
- Email: hkl@impan.gov.pl
- Received by editor(s): April 26, 2004
- Received by editor(s) in revised form: October 18, 2004
- Published electronically: June 15, 2006
- © Copyright 2006
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - Journal: Trans. Amer. Math. Soc. 358 (2006), 4981-5001
- MSC (2000): Primary 05A18
- DOI: https://doi.org/10.1090/S0002-9947-06-03883-9
- MathSciNet review: 2231881