A classification of rapidly growing Ramsey functions
HTML articles powered by AMS MathViewer
- by Andreas Weiermann PDF
- Proc. Amer. Math. Soc. 132 (2004), 553-561 Request permission
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
- Toshiyasu Arai, On the slowly well orderedness of $\epsilon _0$, MLQ Math. Log. Q. 48 (2002), no. 1, 125–130. MR 1874210, DOI 10.1002/1521-3870(200201)48:1<125::AID-MALQ125>3.3.CO;2-E
- Benjamin Blankertz and Andreas Weiermann, How to characterize provably total functions by the Buchholz operator method, Gödel ’96 (Brno, 1996) Lecture Notes Logic, vol. 6, Springer, Berlin, 1996, pp. 205–213. MR 1441112, DOI 10.1007/978-3-662-21963-8_{1}4
- W. Buchholz: On rapidly growing Ramsey functions. Technical report, München 1991.
- Wilfried Buchholz, Adam Cichon, and Andreas Weiermann, A uniform approach to fundamental sequences and hierarchies, Math. Logic Quart. 40 (1994), no. 2, 273–286. MR 1271290, DOI 10.1002/malq.19940400212
- Wilfried Buchholz and Stan Wainer, Provably computable functions and the fast growing hierarchy, Logic and combinatorics (Arcata, Calif., 1985) Contemp. Math., vol. 65, Amer. Math. Soc., Providence, RI, 1987, pp. 179–198. MR 891248, DOI 10.1090/conm/065/891248
- Tadasi Nakayama, On Frobeniusean algebras. I, Ann. of Math. (2) 40 (1939), 611–633. MR 16, DOI 10.2307/1968946
- H. Friedman: “Perfect” statements. Posting the FOM email list from 05.02.1999: http:// www.cs.nyu.edu/pipermail/fom/1999-February/002610.html
- Harvey Friedman and Michael Sheard, Elementary descent recursion and proof theory, Ann. Pure Appl. Logic 71 (1995), no. 1, 1–45. MR 1312428, DOI 10.1016/0168-0072(94)00003-L
- Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer, Ramsey theory, 2nd ed., Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1990. A Wiley-Interscience Publication. MR 1044995
- Akihiro Kanamori and Kenneth McAloon, On Gödel incompleteness and finite combinatorics, Ann. Pure Appl. Logic 33 (1987), no. 1, 23–41. MR 870685, DOI 10.1016/0168-0072(87)90074-1
- Richard Kaye, Models of Peano arithmetic, Oxford Logic Guides, vol. 15, The Clarendon Press, Oxford University Press, New York, 1991. Oxford Science Publications. MR 1098499
- Jussi Ketonen and Robert Solovay, Rapidly growing Ramsey functions, Ann. of Math. (2) 113 (1981), no. 2, 267–314. MR 607894, DOI 10.2307/2006985
- Handbook of mathematical logic, Studies in Logic and the Foundations of Mathematics, vol. 90, North-Holland Publishing Co., Amsterdam, 1977. With the cooperation of H. J. Keisler, K. Kunen, Y. N. Moschovakis and A. S. Troelstra. MR 457132
- Martin Loebl and Jaroslav Ne et il, An unprovable Ramsey-type theorem, Proc. Amer. Math. Soc. 116 (1992), no. 3, 819–824. MR 1095225, DOI 10.1090/S0002-9939-1992-1095225-4
- H. E. Rose, Subrecursion: functions and hierarchies, Oxford Logic Guides, vol. 9, The Clarendon Press, Oxford University Press, New York, 1984. MR 752696
- S. S. Wainer, A classification of the ordinal recursive functions, Arch. Math. Logik Grundlag. 13 (1970), 136–153. MR 294134, DOI 10.1007/BF01973619
- Andreas Weiermann, How to characterize provably total functions by local predicativity, J. Symbolic Logic 61 (1996), no. 1, 52–69. MR 1380676, DOI 10.2307/2275597
- A. Weiermann: An application of graphical enumeration to $PA$, Journal of Symbolic Logic 68, no. 1 (2003), 5-16.
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
- MR Author ID: 317296
- Email: Andreas.Weiermann@math.uni-muenster.de
- 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.
- © Copyright 2003 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 132 (2004), 553-561
- MSC (2000): Primary 03F30; Secondary 03D20, 03C62, 05D10
- DOI: https://doi.org/10.1090/S0002-9939-03-07086-2
- MathSciNet review: 2022381