Transactions of the American Mathematical Society

Author(s): Teresa Bigorajska; Henryk Kotlarski
Journal: Trans. Amer. Math. Soc. 358 (2006), 4981-5001.
MSC (2000): Primary 05A18
Posted: June 15, 2006
Retrieve article in: PDF DVI PostScript

Abstract: Let $\alpha\rightarrow(\beta)_m^r$ denote the property: if

is an $\alpha$ -large set of natural numbers and

is partitioned into

parts, then there exists a $\beta$ -large subset of

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$ .

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.

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

Teresa Bigorajska
Affiliation: Faculty of Mathematics, Cardinal Stefan Wyszynski University, ul. Dewajtis 5, 01--815 Warszawa, Poland
Email: tebigo@op.pl

Henryk Kotlarski
Affiliation: Faculty of Mathematics, Cardinal Stefan Wyszynski University, ul. Dewajtis 5, 01--815 Warszawa, Poland -- and -- Institute of Mathematics, Polish Academy of Sciences, ul. Sniadeckich 8, P.O. Box 137, 00--950 Warszawa, Poland
Email: hkl@impan.gov.pl

DOI: 10.1090/S0002-9947-06-03883-9
PII: S 0002-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
Posted: June 15, 2006
Copyright of article: Copyright 2006, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6850(e) ISSN 0002-9947(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS