On the indecomposability of \(\omega^n\) (Q1762361): Difference between revisions

The authors consider several formulations of pigeonhole principles for finite powers of \(\omega\). The study leads to formalization of two versions of Ramsey's theorem: (1) Weak Ramsey's theorem (WRT\(^2_k\)): For every finite coloring \(c: [\mathbb N ]^2 \to k\) we can find a color \(d\) and an infinite set \(H\) such that for each \(x \in H\) the set \(\{ y \mid c(x,y ) = d \}\) is infinite, and (2) Hyperweak Ramsey's theorem (HWRT\(^2_k\)): For every \(c : [\mathbb N ]^2 \to k\) we can find a color \(d\) and an increasing function \(h : \mathbb N \to \mathbb N\) such that, if \(0 < i < j\), there is an \((x,y) \in [h(i-1), h(i) -1 ] \times [h(j-1) , h(j) - 1 ]\) such that \(c(x,y) = d\). The authors prove that HWRT\(^2_2\) is strictly weaker than WRT\(^2_2\) and that both are weaker than IPT\(^2_2\), as by \textit{D. D. Dzhafarov} and \textit{J. L. Hirst} [Arch. Math. Logic 48, No. 2, 141--157 (2009; Zbl 1172.03007)], and stronger than SADS, as in [\textit{D. R. Hirschfeldt} and \textit{R. A. Shore}, J. Symb. Log. 72, No. 1, 171--206 (2007; Zbl 1118.03055)]. Other principles introduced in the paper lie between B\(\Pi^0_n\) and I\(\Sigma^0_{n+1}\).