On Gödel incompleteness and finite combinatorics (Q581400)

This paper deals with a combinatorial principle which is independent of PA; this principle does not involve the notion of ``relatively large set'', and is stated as follows: Let m,n,K\(\in N\), \(X\subseteq N\); say that \(f:[X]^ n\to N\) is regressive iff \(fs<\min s\), whenever \(s\in [X]^ n\), and min s\(>0\). Also, say that \(H\leq X\) is min homogeneous for f iff \(fs=ft\) whenever \(s,t\in [H]^ n\) and min \(s\leq \min t\). As usual, let us identify each \(m\in N\) with \(\{\) \(n\in N:\) \(n<m\}\). Then: (*) For any n,k\(\in N\), there is an m such that for each regressive \(f:[m]^ n\to N\), there is a K-element subset H of m min homogeneous for f (we simply write: \(m\to (K)^ nreg\). Thus (*) is: \(\forall n,K \exists m:\) \(m\to (K)^ nreg).\) (*) is provable in ZF, because if follows from Erdős-Rado's Theorem: ``For each n and for each regressive \(f:[N]^ n\to N\), there is an infinite set \(H\subseteq N\), which is min homogeneous for f. Facts: i) (*) is proved to be independent of PA. (More precisely, it is shown to be provably equivalent to Paris-Harrington principle PH: \(\forall n,K,r \exists m\) \(m\to_{*}(K)^ n_ r)\). ii) The function \(\nu n=\mu z:z\to (2n)^ mreg\) eventually majorizes all prov. recursive functions. iii) The function \(\nu_ 0n=\mu z:z\to (n)^ 2reg\) has the same rate of amount as Ackermann's function. iv) Let \((PH)_{n+1}\) and \((*)_{n+1}\) denote the sentences resulting from PH and (*) by dropping the quantifier \(\forall n\) (i.e. by fixing the exponent n). Then \((PH)_{n+1}\) and \((*)_{n+1}\) are equivalent in \(I\Sigma_ 1\). The methods used are model-theoretical.