Does $\mathsf{SRT}^2_2$ imply $\mathsf{COH}$ in \(\omega\)-models?

BlogDoes $\mathsf{SRT}^2_2$ imply $\mathsf{COH}$ in \(\omega\)-models?
Damir Dzhafarov Staff asked 3 years ago

A coloring \(f : [\omega]^2 \to 2\) is stable if for every \(x \in \omega\), \(\lim_y f(x,y)\) exists. We let $\mathsf{SRT}^2_2$ be Ramsey’s theorem for pairs and two colors restricted to stable colorings.

An infinite set \(C \subseteq \omega\) is \mathsf{COH}esive for a sequence of sets \({R} = \langle R_0, R_1, \dots \rangle\)┬áif for every \(i \in \omega\), either \(C \subseteq^{*} R_i\) or \(C \subseteq^{*} \overline{R}_i\). $\mathsf{COH}$ is the statement “Every countable sequence of sets has a \mathsf{COH}esive set”.

Question ($\mathsf{SRT}^2_2$ vs. $\mathsf{COH}$ problem). Does \(\mathsf{SRT}^2_2\) imply \(\mathsf{COH}\) in \(\omega\)-models?

Several partial results are known in the direction of a negative answer. In what follows, $\leq_W$ denotes Weihrauch reducibility (also known as uniform reducibility), while $\leq_c$ denotes computable reducibility. The associated strong versions, where access is denied to the original instance, are denoted by $\leq_{sW}$ and $\leq_{sc}$, respectively.

Theorem (Dzhafarov).
$\mathsf{COH} \nleq_W \mathsf{SRT}^2_2$ and $\mathsf{COH} \nleq_{sc} \mathsf{SRT}^2_2$.

The entire combinatorial difficulty in the $\mathsf{SRT}^2_2$ vs. $\mathsf{COH}$ problem seems to lie already in extending the above results to computable reduction.

Question. Is $\mathsf{COH} \leq_c \mathsf{SRT}^2_2$?

In fact, this difficulty is even present in the trying to extend the $\leq_W$ result to two-step Weihrauch reductions.

Question. Is $\mathsf{COH}$ Weihrauch reducible to $\mathsf{SRT}^2_2$? in two steps?

That is, do there exist Turing functionals $\Phi_0$, $\Phi_1$, and $\Psi$ such that, given an instance ${R} = \langle R_0,R_1,\ldots \rangle$ of $\mathsf{COH}$, $\Phi_0({R})$ is an instance $f_0 : [\omega]^2 \to 2$ of $\mathsf{SRT}^2_2$, such that if $H_0$ is any infinite homogeneous set for $f_0$, then $\Phi_1({R} \oplus H_0)$ is an instance $f_1 : [\omega]^2 \to 2$ of $\mathsf{SRT}^2_2$, such that if $H_1$ is any infinite homogeneous set for $f_1$ then $\Psi({R} \oplus H_0 \oplus H_1)$ is an infinite \mathsf{COH}esive set for the $R_i$?

An arguably more natural question is to replace computable reductions above by omniscient reductions. In this case, one does not care about how the instance of the problem to be reduced to depends on the instance of the problem to be reduced from. In particular, the former does not need to be computable from the latter.

Definition (Monin and Patey). If $\mathsf{P}$ and $\mathsf{Q}$ are instance-solution problems, then $\mathsf{P}$ is omnisciently computably reducible to $\mathsf{Q}$ if given any $\mathsf{P}$-instance $A$, there is a $\mathsf{Q}$-instance $B$, such that if $T$ is any $\mathsf{Q}$-solution to $B$ then $A \oplus T$ computes a $\mathsf{P}$-solution to $A$.

It is not difficult to show that $\mathsf{COH}$ is omnisciently computably reducible to $\mathsf{SRT}^2_2$, via the following argument.

Fix an instance $R = \langle R_0, R_1, \ldots \rangle$ of $\mathsf{COH}$. For each $x$, let $R_x^0 = R_x$ and $R_x^1 = \overline{R_x}$, and for each $\sigma \in 2^{<\omega}$, let $R^\sigma = \bigcap_{x < |\sigma|} R^{\sigma(x)}_x$. Now define $f : [\omega]^2 \to 2$ as follows. Given $x < y$, let $f(x,y) = 0$ if there exists a $\sigma$ of length $x$ such that $R^\sigma$ is finite but $R^\sigma$ contains an element $m \geq y$. Otherwise, let $f(x,y) = 1$. Suppose now that $H$ is an infinite homogeneous set for $f$. From $R \oplus H$, we can compute an $S \in 2^\omega$ such that $R^{S \upharpoonright x}$ is infinite for each $x$, from which it is easy to construct a cohesive set for the $R_i$. We build $S$ by initial segments. Suppose inductively that we have defined $S \upharpoonright x$ and that $R^{S \upharpoonright x}$ is infinite; we define $S(x)$. Choose $x_0, x_1 \in H$ with $x < x_0 < x_1$. Search for the least $m \geq x_1$ in either $R^{S \upharpoonright x} \cap R_x$ or $R^{S \upharpoonright x} \cap \overline{R_x}$, which must exist since one of these two intersections is necessarily infinite. Let $S(x) = 0$ or $1$, depending on which of these cases occurs. By construction, $R^{S \upharpoonright x} \cap R^{S(x)}_x$ is infinite.

The instance $f$ built above has complicated homogeneous sets, but very simple limit-homogeneous sets. Recall that a set $L$ is limit-homogeneous for a stable coloring if all of its elements have the same limit. Every limit-homogeneous set can of course be thinned out to a homogeneous one. But for the coloring $f$ above, all the elements have limit $1$, hence $\omega$ is a limit-homogeneous set for $f$. The complexity of the homogeneous sets of $f$ thus comes entirely from the sparsity of its elements.

For this reason, it is better to replace $\mathsf{SRT}^2_2$ by the related principle $\mathsf{D}^2_2$ when considering omniscient reductions. $\mathsf{D}^2_2$ asserts that every stable coloring $f : [\omega]^2 \to 2$ has an infinite limit-homogeneous set. It is well-known that $\mathsf{SRT}^2_2$ and $\mathsf{D}^2_2$ are computably equivalent. On the other hand, $\mathsf{D}^2_2$ is just the relativization to $\emptyset’$ of $\mathsf{RT}^1_2$, and clearly, the two are omnisciently computably equivalent. Thus, we can ask the following:

Question. Is $\mathsf{COH}$ omnisciently computably reducible to $RT^1_2$?

We do know that if there is a reduction, then it must make essential use of the instance of $\mathsf{COH}$. In fact, the following is true:

Theorem (Dzhafarov, Patey, Solomon, and Westrick).
$\mathsf{COH}$ is not omnisciently strongly computably reducible to $\mathsf{SRT}^2_2$. That is, there is an instance $R_0, R_1, \ldots$ of $\mathsf{COH}$ such that every stable coloring $f : [\omega]^2 \to 2$ (whether computable from the sequence or not) has an infinite homogeneous set $H$ with the property that $H$ computes no infinite set \mathsf{COH}esive for the $R_i$.

We can also formulate many of the above questions in purely degree-theoretic terms. Recall that a set has p-cohesive degree if it computes an infinite set which is cohesive for the sequence of primitive recursive sets. (By a result of Jockusch and Stephan, this is equivalent to having jump of degree PA relative to $\emptyset’$.) A Turing ideal $\mathcal{M}$ is an $\omega$-model of $\mathsf{COH}$ if and only if for every $X \in \mathcal{M}$ there is a $Y \in \mathcal{M}$ such that $Y$ has p-cohesive degree relative to $X$. Thus, for example, we can restate the previous question as follows.

Question. Is there a set $A$ such that every infinite subset of $A$ or $\overline{A}$ has p-cohesive degree?