A classification of rapidly growing Ramsey functions期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

按检索

A classification of rapidly growing Ramsey functions

Authors:	Andreas Weiermann

Institution:	Institut für Mathematische Logik und Grundlagenforschung, der Westfälischen Wilhelms-Universität Münster, Einsteinstr. 62, D-48149 Münster, Germany

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

Keywords:	Paris Harrington theorem rapidly growing Ramsey functions independence results fast growing hierarchies Peano arithmetic

	点击此处可从《Proceedings of the American Mathematical Society》浏览原始摘要信息
	点击此处可从《Proceedings of the American Mathematical Society》下载免费的PDF全文