The polarized Ramsey's theorem (Q1014283)

The authors study the proof-theoretic strength of a version of Ramsey's theorem called the Polarized Ramsey's Theorem. Given a coloring \(f: [\omega]^n\to k\), a \(p\)-homogeneous set for \(f\) is a sequence \(\langle H_1,\dots,H_n\rangle\) of infinite sets such that for some \(c\), \(f(\langle x_1,\dots,x_n\rangle)=c\) for every tuple \(\langle x_1,\dots,x_n\rangle\in H_1\times\cdots\times H_n\). If this is true only for increasing tuples, we call \(\langle H_1,\dots,H_n\rangle\) an increasing \(p\)-homogeneous set. The statement of the Polarized Ramsey's Theorem, denoted by \(\text{PT}^n_k\), says that every coloring \(f: [\omega]^n\to k\) has a \(p\)-homogeneous set. The statement of the Increasing Polarized Ramsey's Theorem, denoted by \(\text{IPT}^n_k\), says that every coloring \(f: [\omega]^n\to k\) has an increasing \(p\)-homogeneous set. We use \(\text{RT}^n_k\) to denote the usual Ramsey's theorem for \(n\)-tuples and \(k\) colors. The authors show that for \(n\geq 3\) and any \(k\), both \(\text{PT}^n_k\) and \(\text{IPT}^n_k\) are equivalent to \(\text{RT}^n_k\), and hence to \(\text{ACA}_0\) over \(\text{RCA}_0\). For \(n=2\), they get that, over \(\text{RCA}_0\), \(\text{RT}^2_k\leftrightarrow \text{PT}^2_k \rightarrow \text{IPT}^2_k\), and over \(\text{B}\Sigma^0_2\), \(\text{IPT}^2_k\) implies the Stable Ramsey Theorem \(\text{SRT}^2_k\). They also analyze the stable versions of the polarized and the increasing polarized Ramsey's theorems.