Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

Remote Access
Green Open Access
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826(online) ISSN 0002-9939(print)


A classification of rapidly growing Ramsey functions

Author: Andreas Weiermann
Journal: Proc. Amer. Math. Soc. 132 (2004), 553-561
MSC (2000): Primary 03F30; Secondary 03D20, 03C62, 05D10
Published electronically: August 19, 2003
MathSciNet review: 2022381
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let $f$ be a number-theoretic function. A finite set $X$ of natural numbers is called $f$-large if $card(X)\geq f(min(X))$. Let $PH_f$ be the Paris Harrington statement where we replace the largeness condition by a corresponding $f$-largeness condition. We classify those functions $f$ for which the statement $PH_f$ is independent of first order (Peano) arithmetic $PA$. If $f$ is a fixed iteration of the binary length function, then $PH_f$ is independent. On the other hand $PH_{\log^*}$ is provable in $PA$. More precisely let $f_\alpha(i):= {\lvert i \rvert}_{H_\alpha^{-1}(i)}$where $\mid i\mid_h$ denotes the $h$-times iterated binary length of $i$ and $H_\alpha^{-1}$ denotes the inverse function of the $\alpha$-th member $H_\alpha$of the Hardy hierarchy. Then $PH_{f_\alpha}$ is independent of $PA$ (for $\alpha\leq \varepsilon_0$) iff $\alpha=\varepsilon_0$.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 03F30, 03D20, 03C62, 05D10

Retrieve articles in all journals with MSC (2000): 03F30, 03D20, 03C62, 05D10

Additional Information

Andreas Weiermann
Affiliation: Institut für Mathematische Logik und Grundlagenforschung, der Westfälischen Wilhelms-Universität Münster, Einsteinstr. 62, D-48149 Münster, Germany
Address at time of publication: Department of Mathematics, P.O. Box 80.010, 3508 TA Utrecht, The Nederlands

PII: S 0002-9939(03)07086-2
Keywords: Paris Harrington theorem, rapidly growing Ramsey functions, independence results, fast growing hierarchies, Peano arithmetic
Received by editor(s): February 21, 2002
Received by editor(s) in revised form: July 4, 2002, and September 26, 2002
Published electronically: August 19, 2003
Communicated by: Carl G. Jockusch, Jr.
Article copyright: © Copyright 2003 American Mathematical Society

Comments: Email Webmaster

© Copyright , American Mathematical Society
Contact Us · Sitemap · Privacy Statement

Connect with us Facebook Twitter Google+ LinkedIn Instagram RSS feeds Blogs YouTube Podcasts Wikipedia