Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Partitioning $ \alpha$-large sets: Some lower bounds


Authors: Teresa Bigorajska and Henryk Kotlarski
Journal: Trans. Amer. Math. Soc. 358 (2006), 4981-5001
MSC (2000): Primary 05A18
DOI: https://doi.org/10.1090/S0002-9947-06-03883-9
Published electronically: June 15, 2006
MathSciNet review: 2231881
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • 1. Avigad, J., Sommer, R., A model theoretic approach to ordinal analysis, Bulletin of Symbolic Logic, 3 (1997), no. 1, 17-52. MR 1444913 (98g:03126)
  • 2. Bigorajska, T., Kotlarski, H., A partition theorem for $ \alpha$-large sets. Fund. Math. 160, 1999, pp. 27-37. MR 1694401 (2000d:05012)
  • 3. Bigorajska, T., Kotlarski, H., Some combinatorics involving $ \xi$-large sets. Fund. Math. 175, 2002, pp. 119-125. MR 1969630 (2005a:05209)
  • 4. Buchholz, W., Cichon, A., Weiermann, A., A uniform approach to fundamental sequences and hierarchies, Mathematical Logic Quarterly 40, 1994, pp. 273-286. MR 1271290 (95g:03035a)
  • 5. Cholak, P., Jockush, C., Slaman, T., On the strength of Ramsey's theorem for pairs, Jour. Symb. Log. 66, March 2001, pp. 1-55. MR 1825173 (2002c:03094)
  • 6. Cichon, E. A., A short proof of two recently discovered independence results using recursion theoretic methods. Proc. Amer. Math. Soc., 87 (1983), no. 4, 704-706. MR 0687646 (84f:03049)
  • 7. Fairtlough, M. V. H., Wainer, S. S., Ordinal complexity of recursive definitions. Information and computation, 99(2), 1992, pp. 123-153. MR 1172210 (93h:03059)
  • 8. Fairtlough, M. V. H., Wainer, S. S., Hierarchies of provably recursive functions, in: S. Buss (editor) Handbook of proof theory, Studies in Logic 137, North-Holland Publishing Company, 1998. MR 1640327 (2000a:03063)
  • 9. Graham, R., Rothschild, B., Spencer, J., Ramsey theory. 2nd edition. Wiley, 1990. MR 1044995 (90m:05003)
  • 10. Ketonen, J., and Solovay, R., Rapidly growing Ramsey functions. Annals of Mathematics 113, 1981, pp. 267-314. MR 0607894 (84c:03100)
  • 11. Kotlarski, H., Piekart, B., Some variations of Hardy hierarchy, Math. Log. Quart. 51, 2005, pp. 417-434. MR 2150370 (2006a:03080)
  • 12. Kotlarski, H., Piekart, B., Weiermann, A., More on lower bounds for partitioning $ \alpha$-large sets, submitted to Annals of Pure and Applied Logic.
  • 13. Kotlarski, H., and Ratajczyk, Z., Inductive full satisfaction classes. Ann. Pure and Appl. Log., 47, 1990, pp. 199-223. MR 1058297 (92b:03058)
  • 14. Kotlarski, H., and Ratajczyk, Z., More on induction in the language with a satisfaction class. Zeitschr. Math. Log., 36, 1990, pp. 441-454. MR 1090318 (92b:03059)
  • 15. Kuratowski, K., Mostowski, A., Set theory. Panstwowe Wydawnictwo Naukowe, 1976.
  • 16. Loebl, M., Nešetril, J., An unprovable Ramsey-type theorem, Proc. Amer. Math. Soc. 116, 1992, pp. 819-824. MR 1095225 (93a:03067)
  • 17. 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.
  • 18. Ratajczyk, Z., A combinatorial analysis of functions provably recursive in $ I\Sigma\sb n$. Fund. Math. 130, 1988, pp. 191-213. MR 0970904 (90d:03126)
  • 19. Ratajczyk, Z., Subsystems of true arithmetic and hierarchies of functions. Ann. Pure and Appl. Log. 64, 1993, pp. 95-152. MR 1241251 (94f:03068)
  • 20. Sommer, R., Transfinite induction and hierarchies of functions generated by transfinite recursion within Peano arithmetic, Ph.D. thesis, University of California, Berkeley, 1990.
  • 21. Sommer, R., Transfinite induction within Peano Arithmetic, Ann. Pure and Appl. Log. 76, 1995, pp. 231-289. MR 1366513 (97f:03075)
  • 22. Weiermann, A., A classification of rapidly growing Ramsey functions, Proc. Amer. Math. Soc. 132, No. 2, pp. 553-561. MR 2022381 (2004m:03211)
  • 23. Weiermann, A., Classifying the phase transition for DENSE(2,2), in preparation.

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2000): 05A18

Retrieve articles in all journals with MSC (2000): 05A18


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

DOI: https://doi.org/10.1090/S0002-9947-06-03883-9
Keywords: Ramsey theorem, Hardy hierarchy, $\alpha$--large sets
Received by editor(s): April 26, 2004
Received by editor(s) in revised form: October 18, 2004
Published electronically: June 15, 2006
Article copyright: © Copyright 2006 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society