Combinatorial unprovability proofs and their model-theoretic counterparts (Q2452679)

The paper begins with a comprehensive survey of unprovability in PA of Ramsey-type combinatorial principles, and then proceeds with a model-theoretic analysis of the canonical Ramsey theorem with a largeness condition ERL, and of a version the Kanamori-McAloon principle KM. The ERL principle states that for all \(n\) and \(k\) there is an \(m\) such that for every function \(f\) defined on \([m]^n\) there is an \(H\subseteq m\), with \(|H|>\max\{\min(H),k\}\), on which \(f\) is canonical, i.e.~ there is a \(v\subseteq n\) such that for all \(x_1<\cdots < x_n\) in \(H\), \(f(x_1,\dots, x_n)\) depends only on \(x_i\) for \(i\in v\). The KM\(_j\) principle is: For all \(n\) and \(k\) there is an \(m\) such that whenever \(f:[m]^n\rightarrow{\mathbb N}\) is \(j\)-regressive, i.e.~ for all \(x_1<\cdots <x_n\leq m\), \(f(x_1,\dots, x_n)\in [x_{j-1}, x_j]\), then there is an \(H\subseteq m\) such that \(|H|\geq k\) and the values of \(f\) on \([H]^n\) depend only on \(x_1,\dots, x_j\). Carlucci and Weiermann gave a combinatorial proof that ERL implies the Paris-Harrington principle PH. The present authors give a model-theoretic proof of unprovability of ERL in PA, and in the process construct a new indicator for cuts satisfying PA. A similar analysis is applied to the KM\(_j\) principle. The main results about it are summarized in the following corollary, in which the principles PH\(^n\) and KM\(^n_j\) are the relativized versions of PH and KM\(_j\) for the fixed exponent \(n\). The following statements are equivalent in \(\mathrm{I}\Sigma_1\): PH\(^{n+1}\); KM\(^{n+1}\); KM\(^{n+j}_j\); 1-Con\((\mathrm I\Sigma_n)\).