COH,SRT 2 2,and multiple functionals

Abstract

We prove the following result: there is a family $R = ⟨ R_{0}, R_{1}, \dots ⟩$ of subsets of ω such that for every stable coloring $c : {[ω]}^{2} \to k$ hyperarithmetical in R and every finite collection of Turing functionals, there is an infinite homogeneous set H for c such that none of the finitely many functionals map $R \oplus H$ to an infinite cohesive set for R. This provides a partial answer to a question in computable combinatorics, whether $COH$ is omnisciently computably reducible to ${SRT}_{2}^{2}$ .

Keywords

Ramsey’s theorem computability theory computable combinatorics reverse mathematis

1. Introduction

The ${SRT}_{2}^{2}$ vs. $COH$ problem is a question in computable combinatorics that aims to clarify the relationship between two well-studied combinatorial consequences of Ramsey’s theorem for pairs in terms of their effective content. Recently solved in its original form by Monin and Patey [15], it has given rise to several related and more general problems, as we detail further below. In this article, we establish a new partial results towards the resolution of one of the principal outstanding questions in this inquiry.

For completeness, and also to fix some notation, we begin by briefly reviewing the most relevant definitions below. We refer the reader to Hirschfeldt [6, Chapter 6] for a more thorough discussion and overview of computable combinatorics. We assume familiarity with computability theory and reverse mathematics, and refer to Soare [21] and Simpson [20], respectively, for background on these subjects. We also assume the basics of Weihrauch reducibility and computable reducibility, and refer, e.g., to Brattka, Gherardi, and Pauly [1] for a detailed survey, or, e.g., to Cholak, Dzhafarov, Hirschfeldt, and Patey [3, Section 1] for an introduction aimed more specifically at the kinds of questions we will be dealing with here.

Definition 1.1.
Fix numbers $n, k ⩾ 1$ .
For every set $X \subseteq ω$ , let ${[X]}^{n} = {⟨ x_{0}, \dots, x_{n - 1} ⟩ \in ω^{n} : x_{0} < \dots < x_{n - 1}}$ .

A k-coloring of ${[ω]}^{n}$ is a map $c : {[ω]}^{n} \to {0, \dots, k - 1}$ .

A set $H \subseteq ω$ is homogeneous for c if $c ↾ {[H]}^{n}$ is constant.

A k-coloring of ${[ω]}^{2}$ is stable if ${lim}_{y} c (⟨ x, y ⟩)$ exists for all $x \in ω$ .

A set $L \subseteq ω$ is limit-homogeneous for a stable $c : {[ω]}^{2} \to k$ if ${lim}_{y} c (x, y)$ is the same for all $x \in L$ .

When $n = 2$ , we call $c : {[ω]}^{2} \to k$ a k-coloring of pairs, or simply a coloring of pairs if k is understood. We will write $c (x, y)$ in place of $c (⟨ x, y ⟩)$ .

The following definition is somewhat nonstandard and technical, but it will simplify the presentation in the sequel.
Definition 1.2.
Let $R = ⟨ r_{0}, r_{1}, \dots ⟩$ be a family of functions $r_{i} : ω \to ω$ .
R is a bounded family of functions if for all n there is a k so that $ran (r_{n}) < k$ .

For $k \in ω$ , R is a k-bounded family of functions if $r_{n} (x) < k$ for all n and x.

A set X is cohesive for R if for each n there is a $y \in ω$ such that $f_{n} (x) = y$ for all but finitely many $x \in X$ .

The more typical definition of cohesiveness is with respect to a family $⟨ R_{0}, R_{1}, \dots ⟩$ of subsets of ω, for which a set X is cohesive if for each n, either $X \cap R_{n}$ or $X \cap \overline{R_{n}}$ is finite. Of course, if we identify sets with their characteristic functions then we see that this is just the same as being cohesive for a 2-bounded family of functions. We return to this below.

We follow the now-standard practice of regarding $Π_{2}^{1}$ statements of second-order arithmetic as problems, equipped with a set of instances, and for each instance, a set of solutions, all coded or represented by subsets of $2^{ω}$ (see [3], Definition 1.1). This facilitates their study both in the framework of reverse mathematics and in terms of Weihrauch and computable reducibilities. We shall not be explicit about this identification moving forward, as it is obvious for all of the principles we will be looking at. These are the following.
Definition 1.3.

Ramsey’s theorem is the statement that for all $n, k ⩾ 1$ , every $c : {[ω]}^{n} \to k$ has an infinite homogeneous set.

Stable Ramsey’s theorem for pairs, denoted ${SRT}_{< \infty}^{2}$ , is the restriction of Ramsey’s theorem to stable colorings of pairs.

The $Δ_{2}^{0}$ subset principle, denoted $D_{< \infty}^{2}$ , is the statement for all $k ⩾ 1$ , every stable $c : {[ω]}^{2} \to k$ has an infinite limit-homogeneous set.

The cohesiveness principle for bounded families, denoted ${COH}_{ω}$ , is the principle that every bounded family of functions has an infinite cohesive set.

For fixed $n, k ⩾ 1$ , ${RT}_{k}^{n}$ denotes the restriction of Ramsey’s theorem to k-colorings of ${[ω]}^{n}$ .

For fixed $k ⩾ 1$ , ${SRT}_{k}^{2}$ and $D_{k}^{2}$ denote the restrictions of ${SRT}_{< \infty}^{2}$ and $D_{< \infty}^{2}$ , respectively, to k-colorings.

For fixed $k ⩾ 1$ , ${COH}_{k}$ is the restriction of ${COH}_{ω}$ to k-bounded families of functions.

For $n = 2$ , the traditional notation for ${COH}_{2}$ is $COH$ , and we shall follow this below. However, we can really use the various restrictions of ${COH}_{ω}$ defined above interchangeably, as the following lemma shows.
Lemma 1.4.
For all $k ⩾ 2$ , we have $COH \equiv_{sW} {COH}_{k} \equiv_{sW} {COH}_{ω}$ .
Proof.
Obviously, $COH ⩽_{sW} {COH}_{k} ⩽_{sW} {COH}_{ω}$ . It remains only to show that ${COH}_{ω} ⩽_{sW} COH$ . For all $k, y \in ω$ , let $y_{k}$ be y written in binary, either truncated or prepended by $0 s$ to have exactly $⌜ {log}_{2} k ⌝$ many digits. We view $y_{k}$ as a string, and write $y_{k} (i)$ for its ith digit. Now fix a bounded family of functions $R = ⟨ r_{0}, r_{1}, \dots ⟩$ . Let $b : ω \to ω$ be the function $b (n) = (μ k) (\forall x) [r_{n} (x) < k]$ for all $n \in ω$ . Then b is uniformly $R^{'}$ -computable. So we can fix a uniformly R-computable approximation $\hat{b} : ω^{2} \to ω$ to b, so that ${lim}_{s} \hat{b} (n, s) = b (n)$ for all n. Define a 2-bounded family of functions $R^{'} = ⟨ r_{0}^{'}, r_{1}^{'}, \dots ⟩$ as follows: for all $m, x \in ω$ , $\begin{matrix} r_{m}^{'} (x) = \{\begin{matrix} r_{n} {(x)}_{\hat{b} (n, s)} (i) & if (\exists n, s \in ω) (\exists i < ⌜ {log}_{2} \hat{b} (n, s) ⌝) m = ⟨ \hat{b} (n, s), i ⟩ \\ 0 & otherwise. \end{matrix} \end{matrix}$ Then $R^{'}$ is a uniformly R-computable, and it is not difficult to see that every infinite cohesive set for $R^{'}$ is also cohesive for R. This completes the proof. □

A well-known fact about $COH$ (in the parlance of Definitions 1.2 and 1.3) is that if X computes an infinite cohesive set for some 2-bounded family of functions $R = ⟨ r_{0}, r_{1}, \dots ⟩$ , then so does any set Y satisfying $R ⩽_{T} Y$ and $X^{'} ⩽_{T} Y^{'}$ . By the preceding lemma, we see that the same holds for any bounded family of functions.

The relationship between the stable Ramsey’s theorem and the cohesiveness principle is the focus of a longstanding and ongoing investigation (see, e.g., [2,3,7,9–14,16,17]). We refer the reader to [3, Section 1] for a discussion of some of the history of these principles, and their larger significance in the exploration of the logical strength of combinatorial principles. For many years, the central open question in this investigation was the so-called ${SRT}_{2}^{2}$ vs. $COH$ problem, which asked whether every ω-model of ${SRT}_{2}^{2}$ also satisfy $COH$ . The answer was recently shown to be no.
Theorem 1.5 (Monin and Patey [15]).

There exists an ω-model of ${SRT}_{2}^{2}$ in which $COH$ fails.

The quest to obtain this solution, by multiple authors, gave rise many related questions, many of which hint more deeply at the combinatorial nature of the relationship between ${SRT}_{2}^{2}$ and $COH$ , and which remain open. Our focus in this paper will be on a question that has arguably emerged as the most central among these. We first recall the definition of omniscient reducibility, introduced by Monin and Patey [14, Section 1.1].

Definition 1.6.
Let $P$ and $Q$ be problems.
$P$ is omnisciently computably reducible to $Q$ if for every $P$ -instance X there is a $Q$ -instance $\hat{X}$ with the property that if $\hat{Y}$ is any $Q$ -solution to $\hat{X}$ then $X \oplus \hat{Y}$ computes a $P$ -solution to X.

$P$ is omnisciently Weihrauch reducible to $Q$ if there is a Turing functional Ψ such that for every $P$ -instance X there is a $Q$ -instance $\hat{X}$ with the property that if $\hat{Y}$ is any $Q$ -solution to $\hat{X}$ then $Ψ (X \oplus \hat{Y})$ is a $P$ -solution to X.
The reductions above are strong if the relevant computation of a $P$ -solution to X works with just $\hat{Y}$ as an oracle, rather than $X \oplus \hat{Y}$ .
Question 1.7.
Is $COH$ omnisciently computably reducible to $D_{2}^{2}$ , or to $D_{< \infty}^{2}$ ?

We can at first compare this to the question of whether $COH$ is simply computably reducible to $D_{< \infty}^{2}$ (or $D_{k}^{2}$ for some k). Here, the answer is no. Indeed, it is easy to see that ${SRT}_{< \infty}^{2} \equiv_{c} D_{< \infty}^{2}$ , and that for each specific k, also ${SRT}_{k}^{2} \equiv_{c} D_{k}^{2}$ . Thus, in the computable reducibility question we could replace $D_{< \infty}^{2}$ by ${SRT}_{< \infty}^{2}$ (or $D_{k}^{2}$ by ${SRT}_{k}^{2}$ ), and then the answer follows by Theorem 1.5 since computable reducibility implies implication over ω-models. (Alternatively, it is easy to see that over ω-models, $D_{k}^{2}$ , $D_{< \infty}^{2}$ , ${SRT}_{k}^{2}$ , and ${SRT}_{< \infty}^{2}$ are equivalent, for all $k ⩾ 2$ .)

Omniscient computable reducibility is more sensitive. While Question 1.7 is open, if we replace $D_{2}^{2}$ by ${SRT}_{2}^{2}$ there then the answer is known: $COH$ is omnisciently computably reducible even to ${SRT}_{2}^{2}$ (see [3], Proposition 2.2). On the other hand, we can replace $D_{2}^{2}$ by ${RT}_{2}^{1}$ , as these are easily seen to be omnisciently computably equivalent, and similarly for $D_{< \infty}^{2}$ and ${RT}_{< \infty}^{1}$ . Here, it will be easier to work with $D_{k}^{2}$ and $D_{< \infty}^{2}$ , so the rest of our discussion is formulated in terms of these principles.

For completeness, we note also that Dzhafarov [9, Theorem 3.2 and Corollary 3.5] showed that ${SRT}_{2}^{2}$ is not omnisciently Weihrauch, or strongly omnisciently computably, reducible to $D_{< \infty}^{2}$ , while Patey [17, Corollary 3.3] showed that for all $k > ℓ ⩾ 1$ , $D_{k}^{2}$ is not strongly omnisciently computably reducible to ${SRT}_{ℓ}^{2}$ . Thus, the relationships between different versions of the stable Ramsey’s theorem and the $Δ_{2}^{0}$ subset principle in terms of known reducibilities are fully understood.

As described in [3, Sections 1 and 2], Question 1.7 seems to encompass the true combinatorial core of the relationship between cohesiveness and homogeneity. Adapting the techniques from Monin and Patey’s resolution of the ${SRT}_{2}^{2}$ vs. $COH$ problem, or the techniques from earlier, partial solutions by Dzhafarov [9] and Dzhafarov, Patey, Solomon, and Westrick [11] (who established that $COH ≰_{W} {SRT}_{< \infty}^{2}$ and $COH ≰_{sc} {SRT}_{< \infty}^{2}$ , respectively) has so far proved difficult. There is thus a wide gap between the current results and Question 1.7. Our approach here is to narrow this gap by allowing for multiple functionals in the “backward” direction. For succinctness, we introduce the following definition:
Definition 1.8.
Let $P$ and $Q$ be problems.
$P$ is Weihrauch reducible to $Q$ with finitely many functionals if there is a Turing functional Φ such that for every $P$ -instance X there is a finite set of Turing functionals $Ψ_{0}, \dots, Ψ_{t - 1}$ such that $Φ (X)$ is a $Q$ -instance and if $\hat{Y}$ is any $Q$ -solution to $Φ (X)$ then there is a $t < s$ with $Ψ_{t} (X \oplus \hat{Y})$ a $P$ -solution to X.

$P$ is computably reducible to $Q$ with finitely many functionals if for every $P$ -instance X there is a $Q$ -instance $\hat{X} ⩽_{T} X$ and a finite set of Turing functionals $Ψ_{0}, \dots, Ψ_{t - 1}$ such that if $\hat{Y}$ is any $Q$ -solution to $\hat{X}$ then there is a $t < s$ with $Ψ_{t} (X \oplus \hat{Y})$ a $P$ -solution to X.

$P$ is hyperarithmetically computably reducible to $Q$ with finitely many functionals if for every $P$ -instance X there is a $Q$ -instance $\hat{X}$ hyperarithmetical in X and a finite set of Turing functionals $Ψ_{0}, \dots, Ψ_{t - 1}$ such that if $\hat{Y}$ is any $Q$ -solution to $\hat{X}$ then there is a $t < s$ with $Ψ_{t} (X \oplus \hat{Y})$ a $P$ -solution to X.

$P$ is omnisciently computably reducible to $Q$ with finitely many functionals if for every $P$ -instance X there is a $Q$ -instance $\hat{X}$ and a finite set of Turing functionals $Ψ_{0}, \dots, Ψ_{t - 1}$ such that if $\hat{Y}$ is any $Q$ -solution to $\hat{X}$ then there is a $t < s$ with $Ψ_{t} (X \oplus \hat{Y})$ a $P$ -solution to X.

The basic relationships between the above reducibilities are as follows: $\begin{array}{rcl} P ⩽_{W} Q & ⟹ & P is Weihrauch reducible to Q with finitely many functionals \\ ⟹ & P is computably reducible to Q with finitely many functionals \\ ⟹ & P is hyperarithmetically reducible to Q with finitely many functionals \\ ⟹ & P is omnisciently computably reducible to Q with finitely many functionals \\ ⟹ & P is omnisciently computably reducible to Q . \end{array}$ Note also that while Weihrauch reducibility with finitely many functionals is a generalization of Weihrauch reducibility, computable reducibility with finitely many functionals is a restriction of computable reducibility. A good example here is to look at ${SRT}_{2}^{2}$ and $D_{2}^{2}$ : as mentioned, ${SRT}_{2}^{2} ≰_{W} D_{2}^{2}$ , but it is easy to see that ${SRT}_{2}^{2}$ is Weihrauch reducible to $D_{2}^{2}$ with finitely many (in fact, two) functionals. We can now state our main result:
Theorem 1.9.
$COH$ is not hyperarithmetically computably reducible to $D_{< \infty}^{2}$ with finitely many functionals.

That is, we build a family of sets $G = ⟨ G_{0}, G_{1}, \dots ⟩$ such that for every stable coloring hyperarithmetical in G and every finite collection of Turing functionals $Ψ_{0}, \dots, Ψ_{s - 1}$ , there exists an infinite limit-homogeneous set H for c such that $Ψ_{t} (G \oplus H)$ is not an infinite cohesive set for G, for any $t < s$ .

Our construction will force the instance G of $COH$ to be non-hyperarithmetical. We do not know whether, in general, this is necessary, or whether there exists a witness to Theorem 1.9 that is hyperarithmetical, or perhaps arithemtical or even computable. Indeed, it is even possible that there is a computable instance of $COH$ witnessing a negative answer to Question 1.7.

The rest of this paper is dedicated to a proof of Theorem 1.9. For ease of understanding, we organize this into two parts. In Section 2 we present a proof just for the case of stable 2-colorings. Then, in Section 3, we explain how the argument can be adapted to obtain the theorem in its full generality. Note.
The proof of Monin and Patey [15] of Theorem 1.5 was announced after the original submission of this article. We have updated the introduction here to reflect this fact.

2. Construction

Our approach uses an elaboration on the forcing methods introduced by Dzhafarov [8] for building instances of $COH$ , and by Cholak, Jockusch, and Slaman [4, Section 4] for building solutions to $D_{2}^{2}$ . With respect to the latter, our proof here has a crucial innovation. As in other applications, we force with Mathias conditions, defined below. But here, our reservoirs are not computable or low, or indeed absolute sets of any other kind. Rather, they are names for sets in the forcing language we use to build our $COH$ instance. This allows us to control not just the $COH$ instance and the $D_{2}^{2}$ solution separately, as is done, e.g., in [8] or [11], but also to control their join. We refer the reader to Shore [19, Chapter 3] and Sacks [18, Section IV.3] for background on forcing in arithmetic, and the latter specifically for an introduction to forcing over the hyperarithmetic hierarchy.

In what follows, several notions of forcing are defined. When no confusion can arise, we refer to the conditions and extension relation in each of these simply as “conditions” and “extension”, without explicitly labeling these by the forcing itself.

2.1. Generic instances of $COH$

Definition 2.1.
Let $P$ be the notion of forcing whose conditions are tuples $p = (σ_{0}, \dots, σ_{| p | - 1}, f)$ as follows:
$| p | \in ω$ ;

$σ_{n} \in 3^{< ω}$ for each $n < | p |$ ;

f is a function $| p | \to 3 \cup {u}$ .
A condition $q = (τ_{0}, \dots, τ_{| q | - 1}, g)$ extends p, written $q ⩽ p$ , if:
$| p | ⩽ | q |$ ;

$f ⪯ g$ ;

$σ_{n} ⪯ τ_{n}$ for all $n < | p |$ ;

if $f (n) \neq u$ for some $n < | p |$ then $τ_{n} (x) = f (n)$ for all $x \in [| σ_{n} |, | τ_{n} |)$ .

Given a $P$ -condition $p = (σ_{0}, \dots, σ_{| p | - 1}, f)$ , we also write $σ_{n}^{p}$ and $f^{p}$ for $σ_{n}$ and f, respectively. If $G$ is a sufficiently generic filter on $P$ then we can define $\begin{matrix} G_{n}^{G} = ⋃_{p \in G, | p | > n} σ_{n}^{p} \end{matrix}$ and $G^{G} = ⨁_{n \in ω} G_{n}^{G}$ . Note that this is an instance of ${COH}_{3}$ , and that by genericity, there are infinitely many n such that ${lim}_{x} G_{n}^{G} (x)$ exists, and infinitely many n such that ${lim}_{x} G_{n}^{G} (x)$ does not exist.

The $P$ forcing language and forcing relation are defined inductively as usual, and we use ${\dot{G}}_{n}$ and $\dot{G}$ as names for $G_{n}^{G}$ and $G^{G}$ . More generally, we help ourselves to names (or $P$ -names) for all definable sets in the forcing language and use these as parameters in other definitions.
Lemma 2.2.
Let $φ (\dot{G})$ be a $Σ_{2}^{0} (\dot{G})$ formula in the forcing language that is forced by some condition p. Let q be the condition that is the same as p, only there is some $n < | p |$ such that $f^{p} (n) = u$ and $f^{q} (n) \neq u$ . Then q forces $φ (\dot{G})$ .
Proof.
As we are employing strong forcing, it suffices to consider the case that $φ (\dot{G})$ is $Π_{1}^{0} (\dot{G})$ . Thus, $φ (\dot{G})$ can be put in the form $\neg (\exists x) ψ (\dot{G}, x)$ , where ψ has only bounded quantifiers and has no free variables other than x. If q does not force this formula then by definition there is some $r ⩽ q$ and some $a \in ω$ such that r forces $ψ (\dot{G}, a)$ . Now, as $Ψ (\dot{G}, a)$ has no free variables, it can be put in quantifier-free conjunctive normal form. But the fact that each clause in this conjunction is forced by r depends only on the strings $σ_{0}^{r}, \dots, σ_{| r | - 1}^{r}$ . So let $r^{'}$ be the condition that is the same as r, except that $f^{r^{'}} (n) = f^{p} (n) = u$ . Then $r^{'}$ still forces $Ψ (\dot{G}, a)$ , and hence also $(\exists x) ψ (\dot{G}, x)$ . But $r^{'}$ is an extension of p, and hence witnesses that p could not force $\neg (\exists x) ψ (\dot{G}, x)$ or $φ (\dot{G})$ , a contradiction. □
Lemma 2.3.
If $G$ is a sufficiently generic filter on $P$ then there is no infinite cohesive set for $G^{G}$ which is low over $G^{G}$ .
Proof.
By the remark following Lemma 1.4, it suffices to show that $G^{G}$ has no $G^{G}$ -computable infinite cohesive set. Fix any functional Δ, and any condition p. We exhibit an extension of p forcing that $Δ (\dot{G})$ is not an infinite cohesive set for $\dot{G}$ . This density fact and the genericity of $G$ will yield the lemma. Let $n = | p |$ . Let q be any extension of p with $| q | = n + 1$ and $f^{q} (n) = u$ . If q forces that for each $i < 3$ and each $z \in ω$ there is an $x > z$ such that $Δ (\dot{G}) (x) ↓ = 1$ and ${\dot{G}}_{n} (x) = i$ , then we can take q to be the desired extension. So suppose otherwise. Then there is an $i < 3$ , a $z \in ω$ , and an $r ⩽ q$ such that no extension of r forces that there is an $x > z$ with $Δ (\dot{G}) (x) ↓ = 1$ and ${\dot{G}}_{n} (x) = i$ . In this case, let s be the condition that is the same as r, except that $f^{s} (n) = i$ . Then $s ⩽ p$ and forces that for all $x > max {x, | σ_{n}^{s} |}$ we have $Δ (\dot{G}) (x) ≃ 0$ . □

In the next section, we assemble the pieces to diagonalize all stable colorings hyperarithmetical in our generic instance $G^{G}$ of $COH$ . We formualte the pieces for a fixed hyperarithmetical operator Γ, and then apply them across all such operators in the final proof. This forces our filter $G$ to be hyperarithmetically generic, and hence, as remarked earlier, $G^{G}$ to be non-hyperarithmetical.
2.2. Generic limit-homogeneous sets

Throughout this section, let Γ be a fixed hyperarithmetical operator, and let $Ψ_{0}, \dots, Ψ_{s - 1}$ be fixed Turing functionals. Let $p_{Γ}$ be a fixed $P$ -condition forcing that $Γ (\dot{G})$ is a stable coloring ${[ω]}^{2} \to 2$ with no infinite limit-homogeneous set which is low over $\dot{G}$ . For each $i < 2$ we let ${\dot{A}}_{i}$ be a name for the set ${x \in ω : {lim}_{y} Γ (\dot{G}) (x, y) = i}$ .

Definition 2.4.
Let $Q_{p_{Γ}}$ be the notion of forcing whose conditions are tuples $(p, D_{0}, D_{1}, \dot{I})$ as follows:
p is a $P$ -condition extending $p_{Γ}$ ;

$D_{i}$ is a finite set for each $i < 2$ , and p forces that $D_{i} \subseteq {\dot{A}}_{i}$ ;

$\dot{I}$ is a $P$ -name, and p forces that $\dot{I}$ is an infinite set which is low over $\dot{G}$ , and $max D_{0} \cup D_{1} < min \dot{I}$ .
A condition $(q, E_{0}, E_{1}, \dot{J})$ extends $(p, D_{0}, D_{1}, \dot{I})$ if:
$q ⩽ p$ ;

$D_{i} \subseteq E_{i}$ for each $i < 2$ ;

q forces that $E_{i} \ D_{i} \subseteq \dot{I}$ for each $i < 2$ , and that $\dot{J} \subseteq \dot{I}$ .

Thus, we can think of $Q_{p_{Γ}}$ -condition as p, together with a pair of Mathias conditions, $(D_{0}, \dot{I})$ and $(D_{1}, \dot{I})$ , that share a common reservoir.

For the remainder of this section, let $Ψ_{0}, \dots, Ψ_{s - 1}$ be a fixed collection of Turing functionals.
Lemma 2.5.
The collection of $P$ -conditions $p^{}$ with the following property is dense below* $p_{Γ}$ : there exists a $Q_{p_{Γ}}$ -condition $(p^{}, D_{0}^{}, D_{1}^{}, \dot{I}) $ and a maximal subset M of $2 \times s$ such that for all $⟨ i, t ⟩ \in M$ , $p^{}$ forces that there is a* $z \in ω$ such that $Ψ_{t} (\dot{G} \oplus (D_{i}^{} \cup F)) (x) ≃ 0$ for all finite sets* $F \subseteq {\dot{I}}^{}$ and all* $x > z$ .
Proof.
Let $p ⩽ p_{Γ}$ be given. We exhibit a $p^{}$ as above below p. Fix an enumeration of all pairs $⟨ i, t ⟩ \in 2 \times s$ . Define $M_{0} = \emptyset$ , and let $(p^{0}, D_{0}^{0}, D_{1}^{0}, {\dot{I}}^{0})$ be the $Q_{p_{Γ}}$ -condition $(p, \emptyset, \emptyset, \dot{ω})$ . By induction, suppose that we have defined $M_{k} \subseteq 2 \times s$ for some $k < 2 s$ , along with some $Q_{p_{Γ}}$ -condition $(p^{k}, D_{0}^{k}, D_{1}^{k}, {\dot{I}}^{k})$ . Let $⟨ i, t ⟩$ be the $(k + 1)$ -st element of our enumeration of $2 \times s$ . If there is a condition $(q, E_{0}, E_{1}, \dot{J})$ extending $(p^{k}, D_{0}^{k}, D_{1}^{k}, {\dot{I}}^{k})$ such that q forces there is a $z \in ω$ such that $Ψ_{t} (\dot{G} \oplus (E_{i} \cup F)) (x) ≃ 0$ for all finite sets $F \subseteq \dot{J}$ and all $x > z$ , let $M_{k + 1} = M_{k} \cup {⟨ i, t ⟩}$ and let $(p^{k + 1}, D_{0}^{k + 1}, D_{1}^{k + 1}, {\dot{I}}^{k + 1})$ be such a $(q, E_{0}, E_{1}, \dot{J})$ . Otherwise, let $M_{k + 1} = M_{k}$ and let $(p^{k + 1}, D_{0}^{k + 1}, D_{1}^{k + 1}, {\dot{I}}^{k + 1}) = (p^{k}, D_{0}^{k}, D_{1}^{k}, {\dot{I}}^{k})$ . Clearly, $M = M_{2 s}$ and $(p^{}, D_{0}^{}, D_{1}^{}, {\dot{I}}^{}) = (p^{2 s}, D_{0}^{2 s}, D_{1}^{2 s}, {\dot{I}}^{2 s})$ satisfy the conclusion of the lemma. □

For the duration of this section, let $(p^{}, D_{0}^{}, D_{1}^{}, {\dot{I}}^{})$ and M as above be fixed.
Definition 2.6.
Let $R_{p^{}, D_{0}^{}, D_{1}^{}, {\dot{I}}^{}}$ be the restriction of $Q_{p_{Γ}}$ to conditions extending $(p^{}, D_{0}^{}, D_{1}^{}, {\dot{I}}^{})$ of the form $(p, D_{0}, D_{1}, {\dot{I}}^{} \cap [u, \infty))$ .

To visually distinguish $R_{p^{}, D_{0}^{}, D_{1}^{}, {\dot{I}}^{}}$ -conditions from more general $Q_{p_{Γ}}$ -extensions of $(p^{}, D_{0}^{}, D_{1}^{}, {\dot{I}}^{})$ , we denote the $R_{p^{}, D_{0}^{}, D_{1}^{}, {\dot{I}}^{}}$ -condition $(p, D_{0}, D_{1}, {\dot{I}}^{} \cap [u, \infty))$ by $(p, D_{0}, D_{1}, u)$ . Note that $(p^{}, D_{0}^{}, D_{1}^{}, {\dot{I}}^{})$ is of course an $R_{p^{}, D_{0}^{}, D_{1}^{}, {\dot{I}}^{}}$ -condition.

We now assemble a couple of density facts that we will use to prove our theorem.
Lemma 2.7.
Let* $(p, D_{0}, D_{1}, u)$ be an $R_{p^{}, D_{0}^{}, D_{1}^{}, {\dot{I}}^{}}$ -condition. The collection of $P$ -condition q for which there exists an $R_{p^{}, D_{0}^{}, D_{1}^{}, {\dot{I}}^{}}$ -condition $(q, E_{0}, E_{1}, v)$ extending $(p, D_{0}, D_{1}, u)$ , and satisfying $| E_{i} | = | D_{i} | + 1$ for each $i < 2$ , is dense below p.
Proof.
Fix any $r ⩽ p$ . Let q be any extension of r deciding, for each $i < 2$ , if there is an $x ⩾ u$ in ${\dot{I}}^{} \cap {\dot{A}}_{i}$ . If for some $i < 2$ , q forces that there is no such x, then q forces that ${\dot{I}}^{} \cap [u, \infty) \subseteq A_{1 - i}$ . But as $q ⩽ p^{}$ , we have that q forces that ${\dot{I}}^{}$ is an infinite set which is low over $\dot{G}$ , and hence that ${\dot{I}}^{} \cap [u, \infty)$ is an infinite set which is low over $\dot{G}$ . But by assumption, $p_{Γ}$ forces that there is no such set contained in ${\dot{A}}_{1 - i}$ , so since $q ⩽ p_{Γ}$ this is a contradiction. Thus, it must be that q forces, for each $i < 2$ , that there is an $x ⩾ u$ in ${\dot{I}}^{} \cap {\dot{A}}_{i}$ . We can thus fix an $x_{i} ⩾ u$ for each $i < 2$ such that q forces that $x_{i} \in {\dot{I}}^{} \cap {\dot{A}}_{i}$ . Let $E_{i} = D_{i} \cup {x_{i}}$ for each i, and let $v = max {x_{0}, x_{1}} + 1$ ; then $(q, E_{0}, E_{1}, v)$ witnesses that q is the desired extension. □

The next lemma facilitates the crucial step of reflecting a $R_{p^{}, D_{0}^{}, D_{1}^{}, {\dot{I}}^{}}$ -condition into $P$ . Lemma 2.8.
Let* $(p, D_{0}, D_{1}, u)$ be an $R_{p^{}, D_{0}^{}, D_{1}^{}, {\dot{I}}^{}}$ -condition, and assume that $f^{p} (n) = u$ for some $n \in [| p^{} |, | p |)$ . For all* $z \in ω$ , $j < 3$ , and $⟨ 0, t_{0} ⟩, ⟨ 1, t_{1} ⟩ \in 2 \times s \ M$ , the collection of $P$ -conditions q with the following property is dense below p: there exists an $R_{p^{}, D_{0}^{}, D_{1}^{}, {\dot{I}}^{}}$ -condition $(q, E_{0}, E_{1}, v)$ extending $(p, D_{0}, D_{1}, u)$ and numbers $i < 2$ and $x > z$ such that q forces that $Ψ_{t_{i}} (\dot{G} \oplus E_{i}) (x) ↓ = 1$ and ${\dot{G}}_{n} (x) = j$ .
Proof.
Fix any $r ⩽ p$ . Consider the $Π_{1}^{0} (\dot{G}, {\dot{I}}^{})$ formula $ψ (\dot{G}, {\dot{I}}^{}, X_{0}, X_{1})$ of two set variables asserting:
$X_{0}$ and $X_{1}$ partition ${\dot{I}}^{} \cap [u, \infty)$ ;

for each $i < 2$ , each $x > z$ , and each finite set $F \subseteq X_{i}$ it is not the case that $Ψ_{t_{i}} (\dot{G} \oplus (D_{i} \cup F)) (x) ↓ = 1$ and ${\dot{G}}_{n} (x) = j$ .
Let $φ (\dot{G}, {\dot{I}}^{})$ be the formula $(\exists X_{0}, X_{1}) ψ (\dot{G}, {\dot{I}}^{}, X_{0}, X_{1})$ . Then $φ (\dot{G}, {\dot{I}}^{})$ is also $Π_{1}^{0} (\dot{G}, {\dot{I}}^{})$ , and we can thus fix some $\hat{r} ⩽ r$ that decides this formula.

Suppose first that $\hat{r}$ forces $φ (\dot{G}, {\dot{I}}^{})$ . Let ${\hat{r}}^{'}$ be the condition that is the same as $\hat{r}$ except that $f^{{\hat{r}}^{'}} (n) = j$ for each $i < 2$ . We claim that ${\hat{r}}^{'}$ forces $φ (\dot{G}, {\dot{I}}^{})$ . Indeed, as $φ (\dot{G}, {\dot{I}}^{})$ is $Π_{1}^{0} (\dot{G}, {\dot{I}}^{})$ and $p^{}$ forces that ${\dot{I}}^{}$ is low over $\dot{G}$ , it follows that there is a $Σ_{2}^{0} (\dot{G})$ formula $θ (\dot{G})$ that $p^{}$ forces is equivalent to $φ (\dot{G}, {\dot{I}}^{})$ . Since $n ⩾ | p^{} |$ we have that $\hat{r}, {\hat{r}}^{'} ⩽ p^{}$ , and so this equivalence is still forced by $\hat{r}$ and ${\hat{r}}^{'}$ . Thus, $\hat{r}$ forces $θ (\dot{G})$ , and hence so does ${\hat{r}}^{'}$ by Lemma 2.2. Now it follows that ${\hat{r}}^{'}$ forces $φ (\dot{G}, {\dot{I}}^{})$ , as desired.

By the uniformity of the low basis theorem, we can fix names ${\dot{X}}_{0}$ and ${\dot{X}}_{1}$ and a condition ${\hat{r}}^{″} ⩽ {\hat{r}}^{'}$ forcing that ${\dot{X}}_{0} \oplus {\dot{X}}_{1}$ is low over $\dot{G}$ and $ψ (\dot{G}, {\dot{I}}^{}, {\dot{X}}_{0}, {\dot{X}}_{1})$ holds. We may further assume that ${\hat{r}}^{″}$ decides, for each $i < 2$ , whether or not ${\dot{X}}_{i}$ is infinite. Since ${\hat{r}}^{″}$ forces that ${\dot{I}}^{}$ is infinite and ${\dot{X}}_{0} \cup {\dot{X}}_{1} = {\dot{I}}^{} \cap [u, \infty)$ , we can fix $i < 2$ such that ${\hat{r}}^{″}$ forces that ${\dot{X}}_{i}$ is infinite. But now consider the $Q_{p_{Γ}}$ -condition $({\hat{r}}^{″}, D_{0}, D_{1}, {\dot{X}}_{i})$ . This is an extension (in $Q_{p_{Γ}}$ ) of $(p^{}, D_{0}^{}, D_{1}^{}, {\dot{I}}^{})$ , and ${\hat{r}}^{″}$ forces that $Ψ_{t_{i}} (\dot{G} \oplus (D_{i} \cup F)) (x) ↓ ≃ 0$ for all finite subset F of ${\dot{X}}_{i}$ and all $x > z$ . By maximality of M, this means that $⟨ i, t_{i} ⟩$ should be in M, even though we assumed it was not. This is a contradiction.

We conclude that $\hat{r}$ actually forces $\neg φ (\dot{G}, {\dot{I}}^{})$ , and so some $q ⩽ \hat{r}$ must force $\begin{matrix} \neg ψ (\dot{G}, {\dot{I}}^{}, {\dot{I}}^{} \cap [u, \infty) \cap {\dot{A}}_{0}, {\dot{I}}^{} \cap [u, \infty) \cap {\dot{A}}_{1}) . \end{matrix}$ In particular, there is an $i < 2$ , an $x > z$ , and a finite set F such that q forces that $F \subseteq {\dot{I}}^{} \cap [u, \infty) \cap {\dot{A}}_{i}$ and that $Ψ_{t_{i}} (\dot{G} \oplus (D_{i} \cup F)) (x) ↓ = 1$ and ${\dot{G}}_{n} (x) = j$ . Let $E_{i} = D_{i} \cup F$ and $E_{1 - i} = E_{i}$ , and let $v = max F$ . Then q is the desired extension of r, as witnessed by $(q, E_{0}, E_{1}, v)$ . □

2.3. Putting it all together

We are now ready to prove the main theorem of this section, which is Theorem 1.9 for stable 2-colorings. In fact, we prove following stronger result which clearly implies it.

Theorem 2.9.
Let $G$ be a hyperarithmetically generic filter on $P$ . Then for every stable coloring $c : {[ω]}^{2} \to 2$ hyperarithmetical in $G^{G}$ , and every finite collection of Turing functionals $Ψ_{0}, \dots, Ψ_{s - 1}$ , there exists an infinite limit-homogeneous set L for c such that $Ψ_{t} (G^{G} \oplus L)$ is not an infinite cohesive set for $G^{G}$ , for any $t < s$ .
Proof.
Let c and $Ψ_{0}, \dots, Ψ_{s - 1}$ be given. Fix a hyperarithmetical operator Γ such that $c = Γ (G^{G})$ . If c has an infinite limit-homogeneous set which is low over $G^{G}$ , then we can take this to be L and then we are done by Lemma 2.3. So assume otherwise, and choose $p_{Γ} \in G$ forcing that $Γ (\dot{G})$ is a stable coloring ${[ω]}^{2} \to 2$ with no infinite limit-homogeneous set which is low over $\dot{G}$ . Define ${\dot{A}}_{0}$ , ${\dot{A}}_{1}$ , and $Q_{p_{Γ}}$ as in the previous section. Since $G$ is generic, we may fix a $p^{} \in G$ , a $Q_{p_{Γ}}$ -condition $(p^{}, D_{0}^{}, D_{1}^{}, {\dot{I}}^{})$ , and a maximal subset M of $2 \times s$ as in Lemma 2.5. We define a sequence of $R_{p^{}, D_{0}^{}, D_{1}^{}, {\dot{I}}^{}}$ -conditions $\begin{matrix} (p_{0}, D_{0, 0}, D_{0, 1}, u_{0}) ⩾ (p_{1}, D_{1, 0}, D_{1, 1}, u_{1}) ⩾ (p_{2}, D_{2, 0}, D_{2, 1}, u_{2}) ⩾ \dots \end{matrix}$ with $p_{z} \in G$ for all $z \in ω$ .

If there is an $i < 2$ such that $⟨ i, t ⟩ \in M$ for all $t < s$ , let $(p_{0}, D_{0, 0}, D_{0, 1}, u_{0}) = (p^{}, D_{0}^{}, D_{1}^{}, {\dot{I}}^{})$ . Now given $(p_{z}, D_{z, 0}, D_{z, 1}, u_{z})$ for some z, apply Lemma 2.7 to find an extension $(p_{z + 1}, D_{z + 1, 0}, D_{z + 1, 1}, u_{z + 1})$ with $p_{z + 1} \in G$ and $| D_{z + 1, i} | = | D_{z, i} | + 1$ for each $i < 2$ . Thus, $L = ⋃_{z \in ω} D_{z, i}$ is an infinite limit homogeneous set for $Γ (G^{G})$ , and by assumption, and the definition of M, we have $Ψ_{t} (G^{G} \oplus L) (x) ≃ 0$ for all $t < s$ and all sufficiently large x. In particular, $Ψ_{t} (G^{G} \oplus L)$ is not an infinite cohesive set for $G^{G}$ , as desired.

Now suppose that for each $i < 2$ there is at least one $t < s$ with $⟨ i, t ⟩ \notin M$ . Let $p_{0}$ be any extension of $p^{}$ in $G$ such that $f^{p_{0}} (n) = u$ for some $n \in [| p^{} |, | p_{0} |)$ , and denote the least such n by $n_{0}$ . Let $D_{i}^{0} = D_{i}^{}$ for each $i < 2$ , and $u_{0} = 0$ , so that $(p_{0}, D_{0, 0}, D_{0, 1}, u_{0}) = (p_{0}, D_{0}^{}, D_{1}^{}, {\dot{I}}^{*})$ . Assume next that we have defined $(p_{z}, D_{z, 0}, D_{z, 1}, u_{z})$ for some z. If z is even, define $(p_{z + 1}, D_{z + 1, 0}, D_{z + 1, 1}, u_{z + 1})$ as in the preceding case, thereby ensuring that $| D_{z + 1, i} | = | D_{z, i} | + 1$ for each $i < 2$ . Next, suppose z is odd. Assume we have a fixed map h from the odd integers onto the set $\begin{matrix} [({0} \times s) \times ({1} \times s) \ M^{2}] \times 3, \end{matrix}$ in which the pre-image of every element in the range is infinite. Say $h (z) = ⟨ ⟨ 0, t_{0} ⟩, ⟨ 1, t_{1} ⟩, j ⟩$ . We then apply Lemma 2.8 to find $(p_{z + 1}, D_{z + 1, 0}, D_{z + 1, 1}, u_{z + 1})$ extending $(p_{z}, D_{z, 0}, D_{z, 1}, u_{z})$ with $p_{z + 1} \in G$ such that for some $i < 2$ and $x > z$ we have that $p_{z + 1}$ forces $Ψ_{t_{i}} (\dot{G} \oplus D_{z + 1, i}) (x) ↓ = 1$ and ${\dot{G}}_{n_{0}} (x) = j$ .

Now, let $L_{i} = ⋃_{z \in ω} D_{z, i}$ for each $i < 2$ , which is an infinite limit-homogeneous set for $Γ (G^{G})$ . If, for each $i < 2$ , there is $t_{i} < s$ such that $Ψ_{t_{i}} (G^{G} \oplus L_{i})$ is an infinite cohesive set for $G^{G}$ , then by genericity of $G$ and the definition of M, it must be that $⟨ i, t_{i} ⟩ \notin M$ . For each $j < 3$ , there are infinitely many odd numbers z such that $h (z) = ⟨ ⟨ 0, t_{0} ⟩, ⟨ 1, t_{1} ⟩, j ⟩$ , and by construction, for each such z, there is an $i < 2$ and an $x > z$ such that $Ψ_{t_{i}} (G^{G} \oplus L_{i}) (x) ↓ = 1$ and $G_{n_{0}}^{G} (x) = j$ . Denote the least such i by $i_{z}$ . Thus, for each $j < 3$ there must be a $k_{j} < 2$ such that $i_{z} = k_{j}$ for infinitely many z with $h (z) = ⟨ ⟨ 0, t_{0} ⟩, ⟨ 1, t_{1} ⟩, j ⟩$ . Fix $j, j^{'} < 3$ with $j \neq j^{'}$ and $k_{j} = k_{j^{'}}$ , and denote the latter by i. Then there are infinitely many x such that $Ψ_{t_{i}} (G^{G} \oplus L_{i}) (x) ↓ = 1$ and $G_{n_{0}}^{G} (x) = j$ , and infinitely many x such that $Ψ_{t_{i}} (G^{G} \oplus L_{i}) (x) ↓ = 1$ and $G_{n_{0}}^{G} (x) = j^{'}$ . Thus, $Ψ_{t_{i}} (G^{G} \oplus L_{i})$ is not cohesive for $G^{G}$ , a contradiction.

We conclude that there is an $i < 2$ such that $Ψ_{t} (G^{G} \oplus L_{i})$ is not an infinite cohesive set for $G^{G}$ , for any $t < s$ , as was to be shown. □

3. Extensions to arbitrary colorings

To prove Theorem 1.9 in full generality, we need to modify our construction of the family $G = ⟨ G_{0}, G_{1}, \dots ⟩$ . Specifically, whereas a 3-bounded family of functions sufficed to defeat all potential stable 2-colorings, we will in general need a $(k + 1)$ -bounded family to defeat all stable k-colorings. For this reason, we introduce the following modification of the forcing notion $P$ defined earlier.

Definition 3.1.

Let $P_{ω}$ be the notion of forcing whose conditions are tuples $p = (σ_{0}, \dots, σ_{| p | - 1}, b, f)$ as follows:

$| p | \in ω$ ;

$σ_{n} \in ω^{< ω}$ for each $n < | p |$ ;

b is a function $| p | \to ω$ , and $max ran σ_{n} < b (n)$ for all $n < | p |$ ;

f is a function $| p | \to 3 \cup {u}$ , and if $f (n) \neq u$ for some $n < | p |$ then $f (n) < b (n)$ .

A condition

q = (τ_{0}, \dots, τ_{| q | - 1}, c, g)

extends p, written

q ⩽ p

, if:

$| p | ⩽ | q |$ ;

$b ⪯ c$ ;

$f ⪯ g$ ;

$σ_{n} ⪯ τ_{n}$ for all $n < | p |$ ;

if $f (n) \neq u$ for some $n < | p |$ then $τ_{n} (x) = f (n)$ for all $x \in [| σ_{n} |, | τ_{n} |)$ .

We write $σ_{n}^{p}$ , $b^{p}$ , $f^{p}$ for $σ_{n}$ , b, and f, as before. It is clear that if $G$ is a sufficiently generic filter on $P_{ω}$ then $G^{G} = ⨁ G_{n}^{G}$ , where again $G_{n}^{G} = ⋃_{p \in G, | p | > n} σ_{n}^{p}$ , is now an instance of ${COH}_{ω}$ . Everything else transfers from $P$ to $P_{ω}$ analogously, with obvious changes. In particular, this is true of Lemmas 2.2 and 2.3.

Now, fix a hyperarithmetical operator Γ, and Turing functionals $Ψ_{0}, \dots, Ψ_{s - 1}$ . Suppose $p_{Γ}$ is a $P_{ω}$ -condition forcing, for some $k ⩾ 2$ , that $Γ (\dot{G})$ is a stable coloring ${[ω]}^{2} \to k$ with no infinite limit-homogeneous set which is low over $\dot{G}$ . For each $i < k$ , let ${\dot{A}}_{i}$ be a name for the set ${x \in ω : {lim}_{y} Γ (\dot{G}) (x, y) = i}$ . We define a suitable modification of the forcing notion $Q_{p_{Γ}}$ .

Definition 3.2.

Let $Q_{ω, p_{Γ}}$ be the notion of forcing whose conditions are tuples $(p, D_{0}, \dots, D_{k - 1}, \dot{I})$ as follows:

p is a $P$ -condition extending $p_{Γ}$ ;

$D_{i}$ is a finite set for each $i < k$ , and p forces that $D_{i} \subseteq {\dot{A}}_{i}$ ;

$\dot{I}$ is a $P_{ω}$ -name, and p forces that $\dot{I}$ is an infinite set which is low over $\dot{G}$ , and $max ⋃_{i < k} D_{i} < min \dot{I}$ .

A condition

(q, E_{0}, \dots, E_{k - 1}, \dot{J})

extends

(p, D_{0}, \dots, D_{k - 1}, \dot{I})

if:

$q ⩽ p$ ;

$D_{i} \subseteq E_{i}$ for each $i < k$ ;

q forces that $E_{i} \ D_{i} \subseteq \dot{I}$ for each $i < k$ , and that $\dot{J} \subseteq \dot{I}$ .

We get an analogue of Lemma 2.5, stated below. The proof is entirely the same.

Lemma 3.3.

The collection of $P_{ω}$ -conditions $p^{*}$ with the following property is dense below $p_{Γ}$ : there exists a $Q_{ω, p_{Γ}}$ -condition $(p^{*}, D_{0}^{*}, \dots, D_{k - 1}^{*}, {\dot{I}}^{*})$ and a maximal subset M of $k \times s$ such that for all $⟨ i, t ⟩ \in M$ , $p^{*}$ forces that there is a $z \in ω$ such that $Ψ_{t} (\dot{G} \oplus (D_{i}^{*} \cup F)) (x) ≃ 0$ for all finite sets $F \subseteq {\dot{I}}^{*}$ and all $x > z$ .

Fixing $(p^{*}, D_{0}^{*}, \dots, D_{k - 1}^{*}, \dot{I}) *$ and M as above, we can define an analogue of the restricted forcing of Definition 2.6, and obtain analogues of Lemmas 2.7 and 2.8. For clarity, we include the definition and statements, and omit the proofs, which carry over from above, mutatis mutandis.

Definition 3.4.

Let $R_{ω, p^{*}, D_{0}^{*}, \dots, D_{k - 1}^{*}, {\dot{I}}^{*}}$ be the restriction of $Q_{ω, p_{Γ}}$ to conditions extending $(p^{*}, D_{0}^{*}, \dots, D_{k - 1}^{*}, {\dot{I}}^{*})$ of the form $(p, D_{0}, \dots, D_{k - 1}, {\dot{I}}^{*} \cap [u, \infty))$ .

As before, we write $(p, D_{0}, \dots, D_{k - 1}, u)$ for $(p, D_{0}, \dots, D_{k - 1}, {\dot{I}}^{*} \cap [u, \infty))$ .

Lemma 3.5.

Let $(p, D_{0}, \dots, D_{k - 1}, u)$ be an $R_{ω, p^{*}, D_{0}^{*}, \dots, D_{k - 1}^{*}, {\dot{I}}^{*}}$ -condition. The collection of $P_{ω}$ -conditions q for which there exists an $R_{ω, p^{*}, D_{0}^{*}, \dots, D_{k - 1}^{*}, {\dot{I}}^{*}}$ -condition $(q, E_{0}, \dots, E_{k - 1}, v)$ extending $(p, D_{0}, \dots, D_{k - 1}, u)$ , and satisfying $| E_{i} | = | D_{i} | + 1$ for each $i < k$ , is dense below p.

Lemma 3.6.

Let $(p, D_{0}, \dots, D_{k - 1}, u)$ be an $R_{ω, p^{*}, D_{0}^{*}, \dots, D_{k - 1}^{*}, {\dot{I}}^{*}}$ -condition., and assume that $b^{p} (n) = k + 1$ and $f^{p} (n) = u$ for some $n \in [| p^{*} |, | p |)$ . For all $z \in ω$ , $j < 3$ , and $⟨ 0, t_{0} ⟩, \dots, ⟨ k - 1, t_{k - 1} ⟩ \in k \times s \ M$ , the collection of $P_{ω}$ -conditions q with the following property is dense below p: there exists an $R_{ω, p^{*}, D_{0}^{*}, \dots, D_{k - 1}^{*}, {\dot{I}}^{*}}$ -condition $(q, E_{0}, \dots, E_{k - 1}, v)$ extending $(p, D_{0}, \dots, D_{k - 1}, u)$ and numbers $i < k$ and $x > z$ such that q forces that $Ψ_{t_{i}} (\dot{G} \oplus E_{i}) (x) ↓ = 1$ and ${\dot{G}}_{n} (x) = j$ .

Everything can now be put together as in the proof of Theorem 2.9 above, to prove the theorem below, from which Theorem 1.9 follows.

Theorem 3.7.

Let $G$ be a hyperarithmetically generic filter on $P_{ω}$ . Then for every $k ⩾ 2$ and every stable coloring $c : {[ω]}^{2} \to k$ hyperarithmetical in $G^{G}$ , and every finite collection of Turing functionals $Ψ_{0}, \dots, Ψ_{s - 1}$ , there exists an infinite limit-homogeneous set L for c such that $Ψ_{t} (G^{G} \oplus L)$ is not an infinite cohesive set for $G^{G}$ , for any $t < s$ .

Footnotes

Acknowledgements

Dzhafarov was supported by a Collaboration Grant for Mathematicians from the Simons Foundation and by a Focused Research Group grant from the National Science Foundation of the United States, DMS-1854355. Patey was partially supported by grant ANR “ACTC” #ANR-19-CE48-0012-01. The authors thank the anonymous referee for helpful comments.

References

Brattka,

Gherardi and

Pauly, Weihrauch complexity in computable analysis. to appear.

Brattka and

Rakotoniaina, On the uniform computational content of Ramsey’s theorem, The Journal of Symbolic Logic 82(4) (2017), 1278–1316. doi:10.1017/jsl.2017.43.

Cholak,

D.D.

Dzhafarov,

D.R.

Hirschfeldt and

Patey, Some results concerning the

{SRT}_{2}^{2}

vs.

COH

problem, submitted.

P.A.

Cholak,

C.G.

Jockusch and

T.A.

Slaman, On the strength of Ramsey’s theorem for pairs, J. Symbolic Logic 66(1) (2001), 1–55. doi:10.2307/2694910.

C.T.

Chong,

Lempp and

Yang, On the role of the collection principle for

Σ_{2}^{0}

-formulas in second-order reverse mathematics, Proc. Amer. Math. Soc. 138(3) (2010), 1093–1100. doi:10.1090/S0002-9939-09-10115-6.

Denis and

Hirschfeldt, Slicing the Truth: On the Computable and Reverse Mathematics of Combinatorial Principles, Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore. World Scientific Publishing Company Incorporated, 2014.

F.G.

Dorais,

D.D.

Dzhafarov,

J.L.

Hirst,

J.R.

Mileti and

Shafer, On uniform relationships between combinatorial problems, Trans. Amer. Math. Soc. 368(2) (2016), 1321–1359. doi:10.1090/tran/6465.

D.D.

Dzhafarov, Cohesive avoidance and strong reductions, Proc. Amer. Math. Soc. 143(2) (2015), 869–876. doi:10.1090/S0002-9939-2014-12261-1.

D.D.

Dzhafarov, Strong reductions between combinatorial principles, J. Symbolic Logic 81(4) (2016), 1405–1431. doi:10.1017/jsl.2016.1.

10.

D.D.

Dzhafarov,

Le Goh,

D.R.

Hirschfeldt,

Patey and

Pauly, Ramsey’s theorem and products in the Weihrauch degrees, Computability, to appear.

11.

D.D.

Dzhafarov,

Patey,

Solomon and

Brown Westrick, Ramsey’s theorem for singletons and strong computable reducibility, Proc. Amer. Math. Soc. 145(3) (2017), 1343–1355. doi:10.1090/proc/13315.

12.

D.R.

Hirschfeldt and

C.G.

JockuschJr., On notions of computability-theoretic reduction between

Π_{2}^{1}

principles, J. Math. Log. 16(1) (2016), 1650002. doi:10.1142/S0219061316500021.

13.

J.L.

Hirst and

Mummert, Using Ramsey’s theorem once, to appear.

14.

Monin and

Patey,

Π_{1}^{0}

encodability and omniscient reductions, Notre Dame Journal of Formal Logic, to appear.

15.

Monin and

Patey,

S R T_{2}^{2}

does not imply

C O H

in ω-models, to appear.

16.

Patey, Partial orders and immunity in reverse mathematics, in: Pursuit of the Universal, Lecture Notes in Comput. Sci., Vol. 9709, Springer, Cham, 2016, pp. 353–363. doi:10.1007/978-3-319-40189-8_36.

17.

Patey, The weakness of being cohesive, thin or free in reverse mathematics, Israel J. Math. 216(2) (2016), 905–955. doi:10.1007/s11856-016-1433-3.

18.

G.E.

Sacks, Higher Recursion Theory, Perspectives in Mathematical Logic., Springer-Verlag, Berlin, 1990.

19.

R.A.

Shore, The Turing degrees: An introduction, in: Forcing, Iterated Ultrapowers, and Turing Degrees, Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap., Vol. 29, World Sci. Publ., Hackensack, NJ, 2016, pp. 39–121. doi:10.1142/9789814699952_0002.

20.

S.G.

Simpson, Subsystems of Second Order Arithmetic. Perspectives in Logic, 2nd edn, Cambridge University Press, Cambridge, 2009.

21.

R.I.

Soare, Turing Computability: Theory and Applications, 1st edn, Springer Publishing Company, Incorporated, 2016.

COH,SRT 2 2,and multiple functionals

Abstract

Keywords

1. Introduction

2.1. Generic instances of COH

Footnotes

Acknowledgements

References

2.1. Generic instances of $COH$