Advanced search
1 file | 191.43 KB

A classification of rapidly growing Ramsey functions

Author
Organization
Abstract
Let f be a number-theoretic function. A finite set X of natural numbers is called f-large if card(X) greater than or equal to f(min(X)). Let PHf 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 PHf is independent of first order (Peano) arithmetic PA. If f is a fixed iteration of the binary length function, then PHf is independent. On the other hand PHlog* is provable in PA. More precisely let f(alpha)( i) := \i\H-alpha(-1) (i) where \i\(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 PHfalpha is independent of PA (for alpha less than or equal to epsilon(0)) iff alpha = epsilon(0).
Keywords
rapidly growing Ramsey functions, Paris Harrington theorem, independence results, fast growing hierarchies, Peano arithmetic

Downloads

  • (...).pdf
    • full text
    • |
    • UGent only
    • |
    • PDF
    • |
    • 191.43 KB

Citation

Please use this url to cite or link to this publication:

Chicago
Weiermann, Andreas. 2004. “A Classification of Rapidly Growing Ramsey Functions.” Proceedings of the American Mathematical Society 132 (2): 553–561.
APA
Weiermann, A. (2004). A classification of rapidly growing Ramsey functions. PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 132(2), 553–561.
Vancouver
1.
Weiermann A. A classification of rapidly growing Ramsey functions. PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY. 2004;132(2):553–61.
MLA
Weiermann, Andreas. “A Classification of Rapidly Growing Ramsey Functions.” PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY 132.2 (2004): 553–561. Print.
@article{364988,
  abstract     = {Let f be a number-theoretic function. A finite set X of natural numbers is called f-large if card(X) greater than or equal to f(min(X)). Let PHf 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 PHf is independent of first order (Peano) arithmetic PA. If f is a fixed iteration of the binary length function, then PHf is independent. On the other hand PHlog* is provable in PA. More precisely let f(alpha)( i) := \i\H-alpha(-1) (i) where \i\(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 PHfalpha is independent of PA (for alpha less than or equal to epsilon(0)) iff alpha = epsilon(0).},
  author       = {Weiermann, Andreas},
  issn         = {0002-9939},
  journal      = {PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY},
  keywords     = {rapidly growing Ramsey functions,Paris Harrington theorem,independence results,fast growing hierarchies,Peano arithmetic},
  language     = {eng},
  number       = {2},
  pages        = {553--561},
  title        = {A classification of rapidly growing Ramsey functions},
  url          = {http://dx.doi.org/10.1090/S0002-9939-03-07086-2},
  volume       = {132},
  year         = {2004},
}

Altmetric
View in Altmetric
Web of Science
Times cited: