A classification of rapidly growing Ramsey functions
 Author
 Andreas Weiermann (UGent)
 Organization
 Abstract
 Let f be a numbertheoretic function. A finite set X of natural numbers is called flarge 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 flargeness 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\Halpha(1) (i) where \i\(h) denotes the htimes iterated binary length of i and Halpha(1) denotes the inverse function of the alphath member Halpha 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
 
 
 191.43 KB
Citation
Please use this url to cite or link to this publication: http://hdl.handle.net/1854/LU364988
 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 numbertheoretic function. A finite set X of natural numbers is called flarge 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 flargeness 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\Halpha(1) (i) where \i\(h) denotes the htimes iterated binary length of i and Halpha(1) denotes the inverse function of the alphath member Halpha 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 = {00029939}, 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 = {553561}, title = {A classification of rapidly growing Ramsey functions}, url = {http://dx.doi.org/10.1090/S0002993903070862}, volume = {132}, year = {2004}, }
 Altmetric
 View in Altmetric
 Web of Science
 Times cited: