## 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