# Cross-constraint basis theorems
and products of partitions

Julien Cervelle  William Gaudelier  Ludovic Levy Patey

###### Abstract

We both survey and extend a new technique from Lu Liu to prove separation
theorems between products of Ramsey-type theorems over computable
reducibility. We use this technique to show that Ramsey’s theorem for
$n$-tuples and three colors is not computably reducible to finite products of
Ramsey’s theorem for $n$-tuples and two colors.

##  1 Introduction

In this article, we consider mathematical theorems as problems $\mathsf{P}$,
formulated in terms of _instances_ and _solutions_. For example, König’s lemma
states that every infinite, finitely branching tree admits an infinite path.
Here, an instance of $\mathsf{KL}$ is an infinite, finitely branching tree
$T\subseteq\mathbb{N}^{<\mathbb{N}}$, and a solution to $T$ is an infinite
path $P\in[T]$.

There are many ways to compare the strength of mathematical problems. The most
well-known approach is proof-theoretic, using _reverse mathematics_. It uses
subsystems of second-order arithmetic, with a base theory, $\mathsf{RCA}_{0}$,
capturing _computable mathematics_. Then, if
$\mathsf{RCA}_{0}\vdash\mathsf{Q}\rightarrow\mathsf{P}$, then $\mathsf{Q}$ is
at least as strong as $\mathsf{P}$, in the sense that one can solve
$\mathsf{P}$ using multiple applications of $\mathsf{Q}$ as a black box, with
only computable manipulations. There exist other approaches, more
computability-theoretic, such as the _Weihrauch reduction_ and _computable
reduction_. A problem $\mathsf{P}$ is _computably reducible_ to $\mathsf{Q}$
(written $\mathsf{P}\leq_{c}\mathsf{Q}$) if for every $\mathsf{P}$-instance
$X$, there exists an $X$-computable $\mathsf{Q}$-instance $\widehat{X}$ such
that, for every $\mathsf{Q}$-solution $\widehat{Y}$ of $\widehat{X}$,
$X\oplus\widehat{Y}$ computes a $\mathsf{P}$-solution to $X$. Weihrauch
reduction is a uniform variant of computable reduction.

The proof-theoretic and computability-theoretic approaches are related, in
that when restricting reverse mathematics to _$\omega$ -models_, that is,
models whose first-order part consists of the standard integers together with
the usual operations, then an implication over $\mathsf{RCA}_{0}$ is a
generalization of computable reduction, in which multiple successive
applications are allowed. There are similar links between intuitionistic
reverse mathematics and the Weihrauch reduction. From this viewpoint,
computable reduction is “ressource-sensitive”, in that only one application of
$\mathsf{Q}$ is allowed to solve $\mathsf{P}$. Each approach has its own
interest, as it reveals a different aspect of the relation between
$\mathsf{P}$ and $\mathsf{Q}$.

###  1.1 Ramsey’s theorem

In this article, we consider one particular family of problems, based on
_Ramsey’s theorem_. Given a set $X\subseteq\mathbb{N}$, we write $[X]^{n}$ for
the set of all $n$-element subsets of $X$. Given a coloring
$f:[\mathbb{N}]^{n}\to k$, a set $H\subseteq\mathbb{N}$ is _$f$ -homogeneous_
if $f$ is constant on $[H]^{n}$. Ramsey’s theorem for $n$-tuples and
$k$-colors ($\mathsf{RT}^{n}_{k}$) states the existence, for every coloring
$f:[\mathbb{N}]^{n}\to k$, of an infinite $f$-homogeneous set. The statement
$\mathsf{RT}^{n}_{k}$ has two parameters.

The computational power of $\mathsf{RT}^{n}_{k}$ depending on $n$ is well-
understood for computable instances. For $n=1$, there is always a computable
solution. For $n\geq 2$, Jockusch [17, Theorem 5.1] proved the existence of a
computable instance of $\mathsf{RT}^{n}_{2}$ with no $\Sigma^{0}_{n}$
solution. He also showed [17, Theorem 5.5] that every computable instance of
$\mathsf{RT}^{n}_{k}$ admits a $\Pi^{0}_{n}$ solution. Cholak, Jockusch, and
Slaman [5, Theorem 12.1] proved that for every computable instance of
$\mathsf{RT}^{n}_{k}$, every PA degree over $\emptyset^{(n-2)}$ computes the
jump of a solution. Seetapun [27, Theorem 2.1] proved that for every
computable instance of $\mathsf{RT}^{n}_{k}$ and for every non
$\Delta^{0}_{n-1}$ set $C$, there exists a solution that does not compute $C$.
Liu [21, Theorem 1.5] proved that every computable instance of
$\mathsf{RT}^{2}_{k}$ admits a solution of non-PA degree. On the other hand,
for $n\geq 3$, Hirschfeldt and Jockusch [15, Corollary 2.2] proved the
existence of a computable instance of $\mathsf{RT}^{n}_{2}$ such that every
solution is of PA degree over $\emptyset^{(n-2)}$.

Translated in terms of reverse mathematics, $\mathsf{RT}^{1}_{2}$ is provable
over $\mathsf{RCA}_{0}$, $\mathsf{RT}^{2}_{2}$ is strictly in between
$\mathsf{RCA}_{0}$ and $\mathsf{ACA}_{0}$, and incomparable with
$\mathsf{WKL}_{0}$, and $\mathsf{RT}^{n}_{2}$ is equivalent to
$\mathsf{ACA}_{0}$ over $\mathsf{RCA}_{0}$ for every $n\geq 3$. See Simpson
[28] for a presentation of $\mathsf{RCA}_{0}$, $\mathsf{WKL}_{0}$ and
$\mathsf{ACA}_{0}$. The number $k$ of colors is not relevant when it is
standard, using a color-blindness argument. Indeed, given an instance of
$\mathsf{RT}^{n}_{k^{2}}$, one can create an instance of $\mathsf{RT}^{n}_{k}$
by grouping the colors into blocks of size $k$, and, given a solution, define
another instance of $\mathsf{RT}^{n}_{k}$ by working on the domain of the
first solution. For this reason, the power of $\mathsf{RT}^{n}_{k}$ depending
on $k$ was not studied until recently.

The color blindness argument shows that
$\mathsf{RCA}_{0}\vdash\mathsf{RT}^{n}_{k}\rightarrow\mathsf{RT}^{n}_{k^{2}}$
by two successive applications of $\mathsf{RT}^{n}_{k}$. This kind of argument
does not hold for a resource-sensitive notion such as computable reduction.
Patey [24, Corollary 3.14] proved that for every $n\geq 2$ and every $k$,
$\mathsf{RT}^{n}_{k+1}\not\leq_{c}\mathsf{RT}^{n}_{k}$.

###  1.2 Products of problems

There exist various operators on mathematical problems, coming essentially
from the study of Weihrauch degrees. Among these, we shall consider two
operators:

  * •

The _star_ of a problem $\mathsf{P}$ is the problem $\mathsf{P}^{*}$ whose
instances are finite tuples $(X_{0},\dots,X_{n-1})$ of instances of
$\mathsf{P}$ for some $n\in\mathbb{N}$ and whose solutions are finite tuples
$(Y_{0},\dots,Y_{n-1})$ such that $Y_{i}$ is a $\mathsf{P}$-solution to
$X_{i}$ for every $i<n$.

  * •

The _parallelization_ of a problem $\mathsf{P}$ is the problem
$\widehat{\mathsf{P}}$ whose instances are infinite sequences of
$\mathsf{P}$-instances $X_{0},X_{1},\dots$ and whose solutions are infinite
sequences $Y_{0},Y_{1},\dots$ such that for every $n\in\mathbb{N}$, $Y_{n}$ is
a $\mathsf{P}$-solution to $X_{n}$.

When considering a reduction $\mathsf{P}\leq_{c}\mathsf{Q}^{*}$, one is
allowed to use an arbitrarily large, but finite number $n$ of instances of
$\mathsf{Q}$ to solve an instance $X$ of $\mathsf{P}$, where $n$ depends on
$X$. However, the instances of $\mathsf{Q}$ must be simultaneously chosen, in
that they are not allowed to depend on each others’ solutions. This
simultaneity prevents from using the standard color blindness argument, and
motivates the following question:

######  Question 1.1.

Given $n,k\geq 1$, is
$\mathsf{RT}^{n}_{k+1}\leq_{c}(\mathsf{RT}^{n}_{k})^{*}$?

The case $n=1$ is not interesting since $\mathsf{RT}^{n}_{k}$ is computably
true, but was studied in the context of Weihrauch degrees by Dorais et al [8],
Hirschfeldt and Jockusch [15] and Dzhafarov and al [10]. The first interesting
case for computable reduction is then $n=2$. Let us first illustrate why the
technique used to prove that
$\mathsf{RT}^{2}_{k+1}\not\leq_{c}\mathsf{RT}^{2}_{k}$ fails when considering
products. Patey [24] used an analysis based on preservation of
hyperimmunities. A function $g:\mathbb{N}\to\mathbb{N}$ is _hyperimmune_ if it
is not dominated by any computable function. An infinite set $A$ is
hyperimmune if its principal function is hyperimmune, where the _principal
function_ $p_{A}$ of a set $A\coloneqq\\{x_{0}<x_{1}<\ldots\\}$ is the
function $n\mapsto x_{n}$. Patey proved [24, Theorem 3.11] that for every
$k\geq 1$, every $(k+1)$-tuple of hyperimmune functions $g_{0},\dots,g_{k}$,
and every computable instance $X$ of $\mathsf{RT}^{n}_{k}$, there exists a
solution $Y$ such that at least two among the hyperimmune functions remain
$Y$-hyperimmune, but that it is not the case for computable instances of
$\mathsf{RT}^{n}_{k+1}$. This property fails when considering the star
operator, as the following lemma shows:

######  Lemma 1.2 (Cholak et al [4]).

There exist 4 hyperimmune functions $g_{0},\dots,g_{3}$ and two computable
colorings $f_{0},f_{1}:[\mathbb{N}]^{2}\to 2$ such that for every infinite
$f_{0}$-homogeneous set $H_{0}$ and every infinite $f_{1}$-homogeneous set
$H_{1}$, at most one $g_{i}$ is $H_{0}\oplus H_{1}$-homogeneous.

###### Proof.

Indeed, consider a $\Delta^{0}_{2}$ 4-partition $A_{0}\sqcup\dots\sqcup
A_{3}=\mathbb{N}$ such that for every $i<4$, $\overline{A}_{i}$ is
hyperimmune. For every $i<4$, $g_{i}$ is the principal function of
$\overline{A}_{i}$. Let $f_{0},f_{1}$ be computable instances of
$\mathsf{RT}^{2}_{2}$ such that for every $x$, $\lim_{y}f_{0}(x,y)=1$ iff
$x\in A_{0}\cup A_{1}$ and $\lim_{y}f_{1}(x,y)=1$ iff $x\in A_{0}\cup A_{2}$.
Every infinite $f_{0}$-homogeneous set $H_{0}$ is either included in
$A_{0}\cup A_{1}$ or in $A_{2}\cup A_{3}$, and every infinite
$f_{1}$-homogeneous set $H_{1}$ is either included in $A_{0}\cup A_{2}$ or in
$A_{1}\cup A_{3}$.

Note that if a set $H\subseteq A_{i}\cup A_{j}$ for some $i<j<4$, then $p_{H}$
dominates each $g_{k}$ for $k\in\\{0,1,2,3\\}-\\{i,j\\}$, in which case none
of those $g_{k}$ are $H$-hyperimmune. Thus, either $g_{0}$ and $g_{1}$ or
$g_{2}$ and $g_{3}$ are not $H_{0}$-hyperimmune, and either $g_{0}$ and
$g_{2}$, or $g_{1}$ and $g_{3}$ are not $H_{1}$-hyperimmune. It follows that
at most one of the $g_{i}$ is $H_{0}\oplus H_{1}$-hyperimmune. ∎

The instances of $\mathsf{RT}^{2}_{2}$ created in Lemma 1.2 are called
_stable_ , that is, for every $x$, $\lim_{y}f(x,y)$ exists. Let
$\mathsf{SRT}^{2}_{k}$ denote the restriction of $\mathsf{RT}^{2}_{k}$ to
stable instances. Liu [22] proved that
$\mathsf{SRT}^{2}_{3}\not\leq_{c}(\mathsf{SRT}^{2}_{2})^{*}$, answering a
question by Cholak et al [4]. His proof involved completely new combinatorics,
which will be presented in this article. We will also extend his result to
give a complete answer to 1.1 and prove that
$\mathsf{RT}^{n}_{3}\not\leq_{c}(\mathsf{RT}^{n}_{2})^{*}$ for every $n\geq
2$. Before presenting Liu’s approach, note that the reduction holds when
considering parallelization, but for a completely different reason.

######  Lemma 1.3.

For every $n,k\geq 1$,
$\mathsf{RT}^{n+1}_{k}\leq_{c}\widehat{\mathsf{RT}^{n}_{2}}$.

###### Proof.

By Brattka and Rakotoniaina [3, Corollary 3.30],
$\mathsf{WKL}^{(n)}\leq_{c}\widehat{\mathsf{RT}^{n}_{2}}$, where
$\mathsf{WKL}^{(n)}$ is the problem whose instances are $\Delta^{0}_{n+1}$
approximations of infinite binary trees, and whose solutions are infinite
paths through the trees. It follows that for every set $X$, there is an
$X$-computable instance of $\widehat{\mathsf{RT}^{n}_{2}}$ such that every
solution is of PA degree over $X^{(n)}$. By Cholak, Jockusch and Slaman [5],
for every instance $X$ of $\mathsf{RT}^{n+1}_{k}$, every PA degree over
$X^{(n)}$ computes the jump of a solution to $X$. ∎

###  1.3 Definitions and notation

We assume familiarity with computability theory (see Soare [29]) and reverse
mathematics (see any of Simpson [28], Hirschfeldt [13] or Dzhafarov and
Mummert [12]).

We identify an integer $k\in\mathbb{N}$ with the set $\\{0,\dots,k-1\\}$. The
set $[X]^{n}$ of $n$-element subsets of $X$ is in one-to-one correspondence
with the set of increasing ordered $n$-tuples over $X$. Thus, we shall write
for example $f:[\mathbb{N}]^{n}\to k$ for
$f:[\mathbb{N}]^{n}\to\\{0,\dots,k-1\\}$, and $f(x_{0},\dots,x_{n-1})$ for
$f(\\{x_{0},\dots,x_{n-1}\\})$, assuming $x_{0}<\dots<x_{n-1}$.

Given $k\in\mathbb{N}$, let $k^{\mathbb{N}}$ be the set of all infinite
$k$-valued sequences, and $k^{<\mathbb{N}}$ be the set of all finite
$k$-valued strings. We use Greek letters $\sigma,\tau,\mu,\rho,\dots$ to
denote finitary strings, capital Latin letters $X,Y,Z$ to denote finite or
infinite sets of integers, or infinite $k$-valued sequences. Given
$k,n\in\mathbb{N}$, $k^{=n}$ denotes the set of $k$-valued strings of length
exactly $n$. We define $k^{<n}$ and $k^{\leq n}$ accordingly.

Given two strings $\sigma,\tau$, we let $|\sigma|$ denote the length of
$\sigma$, and $\sigma\preccurlyeq\tau$ means that $\sigma$ is a (non-strict)
prefix of $\tau$. We also write $\sigma\prec X$ to mean that $\sigma$ is an
initial segment of $X$. We let $[\sigma]\coloneqq\\{X\in
k^{\mathbb{N}}:\sigma\prec X\\}$. The choice of $k$ will be clear from the
context. The letter $\varepsilon$ denotes the empty string.

In the whole document, we fix $r\in\mathbb{N}$, and use the following
notations. For $N\in\mathbb{N}$ and
$u\in\\{\mathbb{N},{<}\mathbb{N},{\leqslant}N,{=}N\\}$, we let
$\mathcal{X}_{u}(0)\coloneqq 3^{u}$, $\mathcal{X}_{u}(1)\coloneqq(2^{u})^{r}$
and $\mathcal{X}_{u}\coloneqq\mathcal{X}_{u}(0)\times\mathcal{X}_{u}(1)$. For
simplicity, when $u$ is omitted it means $u\coloneqq\mathbb{N}$, i.e.
$\mathcal{X}\coloneqq 3^{\mathbb{N}}\times(2^{\mathbb{N}})^{r}$.

###  1.4 Organization of the paper

We start by giving a general overview of the construction in Section 2, by
considering separations of theorems in general, then specializing to Ramsey-
type theorems, and then to the actual separation of this article. Then, in
Section 3, we introduce the main concepts, and prove a parameterized version
of the theorems of Liu’s article, justifying the study of cross-constraint
basis theorems. In Section 4, we prove several cross-constraint basis
theorems. More precisely, we reprove the $\Delta^{0}_{2}$ basis theorem as a
warm-up, give a new proof of the cone avoidance basis theorem, and prove a
preservation of non-$\Sigma^{0}_{1}$ definitions and a low basis theorem. In
Section 5, study the notion of $\Gamma$-hyperimmunity introduced by Liu, prove
that $\mathsf{COH}$ preserves this notion, and deduce from it our main
theorem, that is, $\mathsf{RT}^{n}_{3}\not\leq_{c}(\mathsf{RT}^{n}_{2})^{*}$
for $n\geq 2$.

##  2 Core ideas

In this section, we give the general picture of a proof for separating a
theorem from another over computable reducibility. Then, we specialize the
idea to the particular question of
$\mathsf{RT}^{2}_{k+1}\leq_{c}(\mathsf{RT}^{2}_{k})^{*}$ and explain the core
ideas of Liu’s technique. Note that the terminology has been freely altered
from Liu’s original article.

###  2.1 Separating theorems

Given two problems $\mathsf{P}$ and $\mathsf{Q}$, in order to prove that
$\mathsf{P}\not\leq_{c}\mathsf{Q}$, one needs to construct an instance
$X_{\mathsf{P}}$ of $\mathsf{P}$ whose solutions are difficult to compute,
and, for every $X_{\mathsf{P}}$-computable instance $X_{\mathsf{Q}}$ of
$\mathsf{Q}$, a solution $Y_{\mathsf{Q}}$ to $X_{\mathsf{Q}}$ that does not
$X_{\mathsf{P}}$-compute any solution to $X_{\mathsf{P}}$. The framework was
used in its whole generality by Lerman, Solomon, and Towsner [20], but all the
currently known separations over reverse mathematics or over computable
reduction can be done by constructing a computable instance of $\mathsf{P}$.

The construction of the instance of $\mathsf{P}$ can be done either by a
priority construction or by an effectivization of a forcing construction. In
many cases, it is constructed using the finite extension method, that is, an
effectivization of Cohen forcing. This will be the case in our article (see
Proposition 5.13).

Given a computable instance $X_{\mathsf{Q}}$ of $\mathsf{Q}$, the solution
$Y_{\mathsf{Q}}$ is usually built by forcing, in a forcing notion
$(\mathbb{P}_{X_{\mathsf{Q}}},\leq)$. The solution has to satisfy two types of
properties:

  * •

_Structural properties_ : being a solution to $X_{\mathsf{Q}}$. These
properties are generally ensured by the very definition of the notion of
forcing.

  * •

_Computational properties_ : not computing a solution to $X_{\mathsf{P}}$.
These properties are divided into countably many requirements, by considering
each Turing functional individually. Given a requirement $\mathcal{R}_{e}$,
one must prove that the set of conditions forcing $\mathcal{R}_{e}$ is dense.

There is often a tension between the structural properties which provide some
computational strength, and the computational properties which require some
weakness. There is however some degree of freedom in the computational
properties, as they are parameterized by the instance $X_{\mathsf{P}}$ of
$\mathsf{P}$ on which we have the hand.

The idea, coming from Lerman, Solomon and Towsner [20], consists in building
the instance $X_{\mathsf{P}}$ considering each tuple
$(X_{\mathsf{Q}},c,\mathcal{R}_{e})$ at a time, where $X_{\mathsf{Q}}$ is a
computable instance of $\mathsf{Q}$, $c$ is a forcing condition in
$(\mathbb{P}_{X_{\mathsf{Q}}},\leq)$, and $\mathcal{R}_{e}$ is a requirement.
Given a partial approximation of $X_{\mathsf{P}}$ and a tuple
$(X_{\mathsf{Q}},c,\mathcal{R}_{e})$, ask whether there is an extension $d\leq
c$ forcing $\Phi_{e}^{Y_{\mathsf{Q}}}$ to output enough bits of information.
If so, complete $X_{\mathsf{P}}$ so that it diagonalizes against the
functional. Otherwise, there is an extension $d\leq c$ forcing
$\Phi_{e}^{Y_{\mathsf{Q}}}$ to be partial. The counter-intuitive part of this
approach is that the satisfaction of the requirements is ensured by the
construction of $X_{\mathsf{P}}$ instead of the construction of the solutions
$Y_{\mathsf{Q}}$ to computable instances of $\mathsf{Q}$.

As explained by Patey [25], one can polish the previous construction, by
abstracting the construction steps of $X_{\mathsf{Q}}$ to consider every
operation with the same definitional properties, yielding some kind of
genericity property. For example, the separation of the Erdős-Moser theorem
and the Ascending Descending Sequence from Ramsey’s theorem for pairs [20]
were polished in [25] and [26] to obtain hyperimmunity and dependent
hyperimmunity, respectively. In this article, the polishing step yields
$\Gamma$-hyperimmunity (see Definition 5.11).

###  2.2 Separating Ramsey-type theorems

In the particular case of Ramsey-type theorems, there exists a well-
established sub-scheme of construction. Many Ramsey-type theorems are of the
form “For every $k$-coloring of the $n$-tuples of an infinite structure, there
exists an infinite isomorphic substructure over which all the $n$-tuples
satisfy some properties”. In the case of Ramsey’s theorem, the infinite
structure is $(\mathbb{N},<)$, and the property is homogeneity, but one can
consider weaker properties, such as transitivity, in which case one obtains
the Erdős-Moser theorem. One can also consider tree structures, yielding the
tree theorem [6] or Milliken’s tree theorem [1]. These theorems are usually
proven by induction, by constructing so-called pre-homogeneous substructures.
In the case of Ramsey’s theorem, an infinite set $X$ is _pre-homogeneous_ for
a coloring $f:[\mathbb{N}]^{n+1}\to k$ if for every $\vec{x}\in[X]^{n}$ and
every larger $y_{0},y_{1}\in X$, $f(\vec{x},y_{0})=f(\vec{x},y_{1})$.

Although pre-homogeneity is the natural notion to consider from a
combinatorial viewpoint, the computability-theoretic practice has shown the
interest of a weaker notion of “delayed pre-homogeneity” called cohesiveness.
Each Ramsey-type theorem has its own notion of cohesiveness. In the case of
Ramsey’s theorem, this yields the following definition.

######  Definition 2.1.

An infinite set $C$ is _cohesive_ for an infinite sequence of sets
$R_{0},R_{1},\dots$ if for every $n$, $C\subseteq^{*}R_{n}$ or
$C\subseteq^{*}\overline{R}_{n}$, where $\subseteq^{*}$ means “included up to
finite changes”. $\mathsf{COH}$ is the statement “Every infinite sequence of
sets admits an infinite cohesive set.”

Given a coloring $f:[\mathbb{N}]^{n+1}\to k$, one can consider the sequence of
sets $\vec{R}\coloneqq\langle
R_{\vec{x},z}:\vec{x}\in[\mathbb{N}]^{n},z<k\rangle$ defined by
$R_{\vec{x},z}\coloneqq\\{z\in\mathbb{N}:f(\vec{x},z)=y\\}$. Given an infinite
$\vec{R}$-cohesive set $C$, the coloring $f$ restricted to $[C]^{n+1}$ is
_stable_ , that is, for every $\vec{x}\in[\mathbb{N}]^{n}$, $\lim_{y\in
C}f(\vec{x},y)$ exists. This induces a $\Delta^{0}_{2}(C)$ coloring
$\widehat{f}:[C]^{n}\to k$. Cohesiveness is therefore a bridge between
computable instances of $\mathsf{RT}^{n+1}_{k}$ and $\Delta^{0}_{2}$ instances
of $\mathsf{RT}^{n}_{k}$.

Cohesiveness has almost no computational power. Indeed, by delaying pre-
homogeneity, the statement becomes about the jump of sets. More precisely,
$\mathsf{COH}$ is computably equivalent to the statement “For every
$\Delta^{0}_{2}$ infinite binary tree, there exists a $\Delta^{0}_{2}$ path”
(see Belanger [2]). Most of the properties used to separate Ramsey-type
statements are preserved by $\mathsf{COH}$. This phenomenon can be explained
by the fact that every set can be made $\Delta^{0}_{2}$ without affecting too
much the ground model (see Towsner [30]). This will be again the case in our
article (Theorem 5.16). Because of this, the question of the separation
$\mathsf{RT}^{2}_{k+1}\not\leq_{c}(\mathsf{RT}^{2}_{k})^{*}$ becomes a
question about separating $\Delta^{0}_{2}$ instances of
$\mathsf{RT}^{1}_{k+1}$ from finite products of $\Delta^{0}_{2}$ instances of
$\mathsf{RT}^{1}_{k}$.

More generally, given two Ramsey-type statements $\mathsf{P}^{n}$,
$\mathsf{Q}^{n}$ parameterized by the dimension of the $n$-tuples, the
question of $\mathsf{P}^{n+1}\leq_{c}\mathsf{Q}^{n+1}$ is often reduced to the
corresponding question with $\Delta^{0}_{2}$ instances of $\mathsf{P}^{n}$ and
$\mathsf{Q}^{n}$. The experience shows that almost all the known separations
consist in actually constructing a $\Delta^{0}_{2}$ instance of
$\mathsf{P}^{n}$ which defeats not only all the $\Delta^{0}_{2}$ instances of
$\mathsf{Q}^{n}$, but _all_ the instances of $\mathsf{Q}^{n}$, with no
effectiveness restriction (see [24, 23] for examples). The previous remark
about Towsner’s work shows that this apparently stronger diagonalization is
often without loss of generality. This will be again the case in our article,
and the $\Delta^{0}_{2}$ instance of $\mathsf{RT}^{1}_{k+1}$ will defeat all
the finite products of instances of $\mathsf{RT}^{1}_{k}$ (Theorem 3.13).

Building a single instance of $\mathsf{RT}^{1}_{k}$ which defeats
simultaneously uncountably many instances of $(\mathsf{RT}^{1}_{k+1})^{*}$
raises new difficulties, as the sequence of all tuples
$(X_{\mathsf{Q}},c,\mathcal{R}_{e})$ is not countable anymore. Thankfully, we
shall see that there exists a single countable notion of forcing
$(\mathbb{P},\leq)$ such that $\mathbb{P}_{X}\subseteq\mathbb{P}$ for every
$\mathsf{Q}$-instance $X$. Moreover, given a condition $c\in\mathbb{P}$, the
class $I(c)$ of all $\mathsf{Q}$-instances $X$ such that $c\in\mathbb{P}_{X}$
is a compact class. One will exploit this compactness to defeat all
$\mathsf{Q}$-instances $X\in I(c)$ simultaneously.

###  2.3 Cross-constraint techniques

The setting is therefore the following: in order to prove that
$\mathsf{P}^{n+1}\not\leq_{c}\mathsf{Q}^{n+1}$, one builds a $\Delta^{0}_{2}$
instance $X$ of $\mathsf{P}^{n}$ such that for every instance $\widetilde{X}$
of $\mathsf{Q}^{n}$, there is a $\mathsf{Q}^{n}$-solution $\widetilde{Y}$ to
$\widetilde{X}$ that does not compute any $\mathsf{P}^{n}$-solution to $X$.

The instance $X$ of $\mathsf{Q}^{n}$ is built by an effectivization of Cohen
forcing. For example, in this article, to prove that
$\mathsf{RT}^{2}_{k+1}\not\leq_{c}(\mathsf{RT}^{2}_{k})^{*}$, we will build a
$\Delta^{0}_{2}$ instance $f$ of $\mathsf{RT}^{1}_{k+1}$ using an increasing
sequence of $(k+1)$-valued strings $\sigma_{0}\prec\sigma_{1}\prec\dots$ and
let $f$ be the limit of this sequence.

Let $(\mathbb{P},\leq)$ be a countable notion of forcing used to build
solutions to every instance of $\mathsf{Q}^{n}$. At stage $s$, assuming the
Cohen condition $\sigma_{s}$ has been defined, consider the next pair
$(c,\mathcal{R}_{e})$ where $c\in\mathbb{P}$ and $\mathcal{R}_{e}$ is a
requirement saying that $\Phi_{e}^{G}$ is not a solution to the
$\mathsf{P}^{n}$-instance. Consider the class
$\mathcal{C}\subseteq\operatorname{dom}\mathsf{P}^{n}\times I(c)$ of all pairs
$(X,\widetilde{X})$ such that there is an extension $d\leq c$ with
$\widetilde{X}\in I(c)$ forcing $\Phi_{e}^{G}$ to be partial or a
$\mathsf{P}^{n}$-solution to $X$. There are two cases:

  * •

Case 1: the class $\mathcal{C}$ is _left-full_ below $\sigma_{s}$, that is,
for every instance $X$ of $\mathsf{P}^{n}$ extending $\sigma_{s}$, there
exists a $\mathsf{Q}^{n}$-instance $\widetilde{X}$ such that
$(X,\widetilde{X})\in\mathcal{C}$. Then, by some appropriate basis theorem
which depends on the combinatorics of $\mathsf{P}^{n}$ and $\mathsf{Q}^{n}$,
there exist multiple pairs
$(X_{0},\widetilde{X}_{0}),\dots,(X_{k-1},\widetilde{X}_{k-1})$ in
$\mathcal{C}$ such that $X_{0},\dots,X_{k-1}$ are _incompatible_ , in the
sense that there is no set which is a solution to all these
$\mathsf{P}^{n}$-instances simultaneously, while
$\widetilde{X}_{0},\dots,\widetilde{X}_{k-1}$ are compatible as
$\mathsf{Q}^{n}$-instances. Then, by building a solution to the
$\mathsf{Q}^{n}$-instance which will be simultaneously a solution to
$\widetilde{X}_{0},\dots,\widetilde{X}_{k-1}$, this forces $\Phi_{e}^{G}$ to
be partial, hence to satisfy $\mathcal{R}_{e}$.

  * •

Case 2: the class $\mathcal{C}$ is not left-full below $\sigma_{s}$. Then,
there exists a $\mathsf{P}^{n}$-instance $X$ extending $\sigma_{s}$ such that,
for every $\mathsf{Q}^{n}$-instance $\widetilde{X}\in I(c)$, $c$ forces
$\Phi_{e}^{G}$ not to be a $\mathsf{P}^{n}$-solution to $X$. By compactness of
$I(c)$, an initial segment $\sigma_{s+1}\prec X$ is sufficient to witness this
diagonalization, hence to satisfy $\mathcal{R}_{e}$.

The general idea of cross-constraint techniques takes its roots in Liu’s proof
of separation of Ramsey’s theorem for pairs from weak König’s lemma [21], in a
slightly different setting. Indeed, $\mathsf{P}^{n+1}$ was $\mathsf{WKL}$,
which is known to admit a maximally difficult instance, so only
$\mathsf{Q}^{n}$ was built. In that article, he considered the class
$\mathcal{C}$ of all pairs $(f,\widetilde{X})$ such that $f$ is a partial
function with finite support, and $\widetilde{X}\in I(c)$ is an instance of
$\mathsf{RT}^{1}_{2}$.

##  3 General framework

In this section, we define the fundamental notions of left-full cross-tree,
and prove the main theorems parameterized by the cross-constraint ideals. The
basis theorems proven in Section 4 will show the existence of cross-constraint
ideals with various computability-theoretic properties, and will be used to
answer the main question in Section 5.2.

###  3.1 Cross-trees

When considering $\Pi^{0}_{1}$-classes for the space $\mathcal{X}$, it is
natural to consider cross-trees which play a role analogous to binary trees in
the case of the Cantor space.

######  Definition 3.1.

We extend the _prefix relation_ on strings $\preccurlyeq$ to tuples of
strings, in the natural way. More precisely, for any $n\in\mathbb{N}$, given
integers $k_{0},\ldots,k_{n-1}$, and two tuples
$\sigma\coloneqq(\sigma_{0},\ldots,\sigma_{n-1}),\tau\coloneqq(\tau_{0},\ldots,\tau_{n-1})\in\prod_{i<n}k_{i}^{<\mathbb{N}}$,
we have $\sigma\preccurlyeq\tau$ if and only if $\forall
i<n,\sigma_{i}\preccurlyeq\tau_{i}$. For any $k\in\mathbb{N}$, the _empty
string_ of $k^{<\mathbb{N}}$ is denoted by $\varepsilon$, and we abuse the
notation to also denote any tuple $(\varepsilon,\ldots,\varepsilon)$.

Moreover, we define the set of its _infinite extensions_ by
$[\sigma]\coloneqq[\sigma_{0}]\times\ldots\times[\sigma_{n-1}]$, and its
_length_ by $|\sigma|\coloneqq\max\\{|\sigma_{i}|:i<n\\}$.

######  Definition 3.2.

A class $\mathcal{P}\subseteq\mathcal{X}$ is $\Pi^{0}_{1}$ if there is a c.e.
set $W\subseteq\mathcal{X}_{<\mathbb{N}}$ such that

$\overline{\mathcal{P}}=\bigcup_{\chi\in W}[\chi]$

######  Definition 3.3.

A _cross-tree_ is a set $T\subseteq\mathcal{X}_{<\mathbb{N}}$ which is
downward-closed for the prefix relation $\preccurlyeq$, and such that
$\forall(\rho,\sigma)\in T,\forall i{<}j{<}r,|\sigma_{i}|=|\sigma_{j}|\text{
and }|\sigma|\leqslant|\rho|$. The _height_ of $T$ is
$h(T)\coloneqq\max\\{|\chi|:\chi\in T\\}$

The class of its (infinite) _paths_ is defined as

$[T]\coloneqq\big{\\{}(X,Y)\in\mathcal{X}:\forall
n,(X\\!{\upharpoonright}_{n},Y\\!{\upharpoonright}_{n})\in T\big{\\}}$

Moreover, given a string $\rho\in\mathcal{X}_{<\mathbb{N}}(0)$, we define the
tree
$T[\rho]\coloneqq\\{\sigma\in\mathcal{X}_{<\mathbb{N}}(1):(\rho,\sigma)\in
T\\}$, which is finite since $|\sigma|\leqslant|\rho|$. A cross-tree $T$ is
said to be _right-pruned_ if
$\forall\rho\in\mathcal{X}_{<\mathbb{N}}(0),T[\rho]$ is pruned, i.e. all the
leaves of $T[\rho]$ have length $|\rho|$. Finally, for any $N\in\mathbb{N}$ we
define $T\\!{\upharpoonright}_{N}\coloneqq\\{\chi\in T:|\chi|\leqslant N\\}$.

######  Lemma 3.4.

A class $\mathcal{P}\subseteq\mathcal{X}$ is $\Pi^{0}_{1}$ if and only if
there is a computable cross-tree $T\subseteq\mathcal{X}_{<\mathbb{N}}$ such
that $[T]=\mathcal{P}$.

###### Proof.

Let $T\subseteq\mathcal{X}_{<\mathbb{N}}$ be a computable cross-tree. The set
$[T]$ is $\Pi^{0}_{1}$ as its complement is the set $\bigcup_{\chi\in
W}[\chi]$ where $W\coloneqq\mathcal{X}_{<\mathbb{N}}\smallsetminus T$ is
computable.

Now let $\mathcal{P}$ be a $\Pi^{0}_{1}$ class whose complement is
$\bigcup_{(\rho,\sigma)\in W}[\rho]\times[\sigma]$. Consider the cross-tree
$T$ such that $(\rho,\sigma)\in
T\iff\forall\mu\preccurlyeq\rho,\forall\tau\preccurlyeq\sigma,(\mu,\tau)\notin
W[|\rho|]\text{ and }|\rho|\geqslant|\sigma|$. It is computable and its paths
are exactly the elements of $\mathcal{P}$. ∎

######  Remark 3.5.

In the rest of the document, every notion or proposition related to a class
$\mathcal{P}\subseteq\mathcal{X}$, also holds for a computable cross-tree
$T\subseteq\mathcal{X}_{<\mathbb{N}}$ instead, by considering its associated
class $[T]$.

###  3.2 Left-fullness

The notion of left-fullness below is a sufficient notion of largeness such
that any left-full $\Pi^{0}_{1}$-class contains multiple members satisfying
some constraints. A key factor also lies in the fact that the complexity of
this notion is only $\Pi^{0}_{1}$.

######  Definition 3.6.

A class $\mathcal{P}\subseteq\mathcal{X}$ is _left-full_ below
$(\rho,\sigma)\in\mathcal{X}_{<\mathbb{N}}$ if

$\forall X\in[\rho],\exists Y\in[\sigma],(X,Y)\in\mathcal{P}$

Moreover, for any integer $N\in\mathbb{N}$, we say that a finite tree
$T\subseteq\mathcal{X}_{\leqslant N}$ is _left-full_ below $(\rho,\sigma)\in
T$ if for every leaf $(\mu,\tau)\in T$, $|\mu|=N$, and for every
$\mu\in\mathcal{X}_{N}(0)$ extending $\rho$, there is some
$\tau\in\mathcal{X}_{N}(1)$ extending $\sigma$, such that $(\mu,\tau)\in T$.

We simply say “left-full” to signify “left-full below
$(\varepsilon,\varepsilon)$”.

The above definition for finite trees is motivated by the following lemma. In
particular it shows that $T$ is left-full below $(\rho,\sigma)$ if and only if
for any $N\in\mathbb{N}$, $T\\!{\upharpoonright}_{N}$ is left-full below
$(\rho,\sigma)$.

######  Lemma 3.7.

Let $(\rho,\sigma)\in\mathcal{X}_{<\mathbb{N}}$, and
$\mathcal{P}\subseteq\mathcal{X}$ be a $\Pi^{0}_{1}$ class, whose associated
computable cross-tree is $T$. The statement

$\mathcal{P}\text{ is left-full below }(\rho,\sigma)$ (a)

is equivalent to

$\forall\mu\succcurlyeq\rho,\exists\tau\succcurlyeq\sigma,|\tau|=|\mu|\text{
and }(\mu,\tau)\in T$ (b)

Moreover, if $T$ is right-pruned, then the statement is equivalent to

$\forall\mu\succcurlyeq\rho,(\mu,\sigma)\in T$ (c)

###### Proof.

We first show (a)$\implies$(b). Let $\mu\succcurlyeq\rho$. Consider
$X\in[\mu]\subseteq[\rho]$. By (a), there is $Y\in[\sigma]$ such that
$(X,Y)\in\mathcal{P}$. Thus, in particular, we have that
$(\mu,Y\\!{\upharpoonright}_{|\mu|})\in T$. Hence $\tau\coloneqq
Y\\!{\upharpoonright}_{|\mu|}$ is the desired witness.

For the converse, let $X\in[\rho]$. We want to find $Y\in[\sigma]$ such that
$(X,Y)\in\mathcal{P}$. Consider the set
$S\coloneqq\\{\tau\succcurlyeq\sigma:(X\\!{\upharpoonright}_{|\tau|},\tau)\in
T\\}$. Since $T$ is a cross-tree, $S$ is a finitely-branching cross-tree, with
root $\sigma$. Moreover, it is infinite because of (b). Thus, by König’s
lemma, there is $Y\in 2^{\mathbb{N}}$ such that
$\forall\ell,(X\\!{\upharpoonright}_{\ell},Y\\!{\upharpoonright}_{\ell})\in
T$. Hence $(X,Y)\in\mathcal{P}$.

Last, we show (c)$\Leftrightarrow$(b). For all $\mu\succcurlyeq\rho$, if there
is $\tau\succcurlyeq\sigma$ such that $|\tau|=|\mu|\text{ and }(\mu,\tau)\in
T$, then in particular $(\mu,\sigma)\in T$ since $T$ is a cross-tree. As for
the converse, consider $\mu\succcurlyeq\rho$. We have $(\mu,\sigma)\in T$, and
since the cross-tree $\\{\tau:(\mu,\tau)\in T\\}$ is pruned, it means there is
$\tau\succcurlyeq\sigma$ in it of size $|\mu|$ and such that $(\mu,\tau)\in
T$. ∎

The following lemma shows how left-fullness is preserved when extending or
shortening the stems. Note that the first and second components do not play a
symmetric role.

######  Lemma 3.8.

Let $T$ be a computable cross-tree left-full below
$(\rho,\sigma)\in\mathcal{X}_{<\mathbb{N}}$. Then

  * (a)

$\forall\widehat{\rho}\succcurlyeq\rho,\forall\widehat{\sigma}\preccurlyeq\sigma,T\text{
is left-full below }(\widehat{\rho},\widehat{\sigma})$

  * (b)

For every $n\in\mathbb{N}$, there are some $\widehat{\rho}\succcurlyeq\rho$
and $\widehat{\sigma}\succcurlyeq\sigma$ such that $|\widehat{\sigma}|=n$ and
$T$ is left-full below $(\widehat{\rho},\widehat{\sigma})$

###### Proof.

Item $(a)$ can be proven directly from the definition of left-full. For Item
$(b)$, we can suppose WLOG that $|\rho|\geq n$ and $|\sigma|\leq n$, thanks to
the previous item. Consider all the extensions of $\sigma$ of length $n$,
denoted $\sigma_{0},\ldots,\sigma_{k-1}$ for some $k\in\mathbb{N}$, and define
$\rho_{0}\coloneqq\rho$. If $T$ is left-full below $(\rho_{0},\sigma_{0})$
then the assertion is proven. Otherwise, by Lemma 3.7, it means
$\exists\rho_{1}\succcurlyeq\rho_{0},\forall\tau\succcurlyeq\sigma_{0},|\tau|=|\rho_{1}|\implies(\rho_{1},\tau)\notin
T$. Now we consider the pair $(\rho_{1},\sigma_{1})$ to see if $T$ is left-
full below it. In case it is not, use Lemma 3.7 as in the previous case.
Proceed inductively like this for every $\sigma_{j}$, where $j<k$. If at some
point $T$ is left-full below $(\rho_{j},\sigma_{j})$ then the assertion is
proven. Otherwise, it means we have built a sequence of string
$\rho_{0}\preccurlyeq\ldots\preccurlyeq\rho_{k}$ such that $\forall
j<k,\forall\tau\succcurlyeq\sigma_{j},|\tau|=|\rho_{j+1}|\implies(\rho_{j+1},\tau)\notin
T$, and since $T$ is a tree we even have $\forall
j<k,\forall\tau\succcurlyeq\sigma_{j},|\tau|=|\rho_{k}|\implies(\rho_{k},\tau)\notin
T$. But the latter statement contradicts the fact that $T$ is left-full below
$(\rho,\sigma)$, by considering the string $\rho_{k}$ in Lemma 3.7. ∎

###  3.3 Parameterized theorems

Most of the computability-theoretic constructions of solutions to Ramsey-type
theorems are done by variants of Mathias forcing, with reservoirs belonging to
some Turing ideal containing only weak sets. The combinatorics of the
statement usually require some closure properties on this ideal. For example,
to construct solutions to computable instances of Ramsey’s theorem for pairs,
or to arbitrary instances of the pigeonhole principle, one requires the ideal
to be a Scott ideal, that is, a model of $\mathsf{WKL}$ (see [11, 27]). One
must then prove some basis theorem for $\mathsf{WKL}$ to construct Scott
ideals with only weak sets.

In our case, we shall need another closure property, yielding the notion of
cross-constraint ideal. The main constructions of this section will be
parameterized by cross-constraint ideals, whose existence will be proven in
Section 4.

######  Definition 3.9.

Let $X$ be an infinite set. A pair of instances $(f,g)$ of
$\mathsf{RT}^{1}_{k}$ is _finitely compatible on $X$_ if for all color $i<k$
the set $X\cap f^{-1}(i)\cap g^{-1}(i)$ is finite. Whenever $X=\mathbb{N}$, we
simply say that $(f,g)$ is finitely compatible. Also, note that the negation
of “finitely compatible” is “infinitely compatible”

######  Definition 3.10.

The _cross-constraint problem_ , denoted $\mathsf{CC}$, is the problem whose
instances are left-full cross-trees $T\subseteq\mathcal{X}_{<\mathbb{N}}$, and
a solution to $T$ is a pair of paths $(X^{i},Y^{i})_{i<2}$ such that
$(X^{0},X^{1})$ is finitely compatible, and for all $s<r$,
$(Y^{0}_{s},Y^{1}_{s})$ is infinitely compatible.

The following notion of cross-constraint ideal simply says that $\mathcal{M}$
is an $\omega$-model of $\mathsf{CC}$, where an $\omega$-model is a structure
of second-order arithmetic in which the first-order part consists of the
standard integers. An $\omega$-model is then fully characterized by its
second-order part, and is therefore often identified to it. The second-order
part of an $\omega$-structure is a model of $\mathsf{RCA}_{0}$ iff it is a
Turing ideal.

######  Definition 3.11.

A _cross-constraint ideal_ is a Turing ideal
$\mathcal{M}\subseteq\mathfrak{P}(\mathbb{N})$ such that, any instance
$T\in\mathcal{M}$ of $\mathsf{CC}$ has a solution $(X^{i},Y^{i})_{i<2}$ such
that $(X^{0},Y^{0})\oplus(X^{1},Y^{1})\in\mathcal{M}$.

Last, we define a notion of hyperimmunity for $k$-colorings $f$, which is an
intermediate notion between Cohen genericity and hyperimmunity. It implies in
particular that for every $j<k$, $\\{x:f(x)\neq j\\}$ is hyperimmune, but in a
dependent way.

######  Definition 3.12.

An instance $f$ of $\mathsf{RT}^{1}_{k}$ is _hyperimmune_ relative to
$D\subseteq\mathbb{N}$ if for every $D$-computable array of $k$-tuples of
mutually disjoint finite sets $\\{\vec{F_{n}}\\}_{n\in\mathbb{N}}$ such that
$\min\bigcup_{j<k}F_{n,j}>n$, there is $N\in\mathbb{N}$ such that $\forall
j<k,F_{N,j}\subseteq f^{-1}(j)$

In other words, an instance $f$ is hyperimmune relative to $D$ if for every
$D$-computable sequence $g_{0},g_{1},\dots$ of partial $k$-valued functions
with finite support, such that $\forall
n\in\mathbb{N},\min\operatorname{dom}g_{n}>n$, then $f$ is a completion of
some $g_{n}$. We are now ready to prove our first parameterized theorem.

######  Theorem 3.13 (Liu [22, Theorem 2.1]).

Let $\mathcal{M}$ be a countable cross-constraint ideal and let
$f\in\mathcal{X}(0)$ be hyperimmune relative to any element of $\mathcal{M}$,
then for any $g\in\mathcal{X}(1)$ there is a solution $\vec{G}$ of $g$ which,
for any $Z\in\mathcal{M}$, does not $Z$-compute any solution of $f$.

###### Proof.

The set $\vec{G}$ is constructed by a variant of Mathias forcing, using
conditions of the form $\big{(}(\vec{F_{\alpha}})_{\alpha\in
2^{r}},\vec{A}\big{)}$ where

  * •

$\vec{F_{\alpha}}$ is an $r$-tuple of finite sets $g$-homogeneous for the
colors $\alpha$, i.e. $\forall s<r,F_{\alpha,s}\subseteq
g_{s}^{-1}(\alpha(s))$

  * •

$\vec{A}$ is an $r$-tuple of infinite sets in $\mathcal{M}$ such that
$\forall\alpha\in 2^{r},\forall s<r,\min A_{s}>\max F_{\alpha,s}$

The idea is that we do not know in advance what the colors of homogeneity will
be for the solution being constructed, so we build all the possibilities in
parallel, with $\alpha$ indicating the colors, i.e. for any $i<r$, the set
$F_{\alpha,i}$ is $g_{i}$-homogeneous for the color $\alpha(i)$.

A condition $\big{(}(\vec{E_{\alpha}})_{\alpha\in 2^{r}},\vec{B}\big{)}$
_extends_ another $\big{(}(\vec{F_{\alpha}})_{\alpha\in 2^{r}},\vec{A}\big{)}$
if, for every $\alpha\in 2^{r}$ and every $s<r$, we have
$E_{\alpha,s}\supseteq F_{\alpha,s}$, $B_{s}\subseteq A_{s}$, and
$E_{\alpha,s}-F_{\alpha,s}\subseteq A_{s}$.

Every sufficiently generic filter $\mathcal{F}$ for this notion of forcing
induces a family of sets $(G^{\mathcal{F}}_{\alpha,s})_{\alpha\in 2^{r},s<r}$
defined by

$G^{\mathcal{F}}_{\alpha,s}=\bigcup\\{F_{\alpha,s}:\big{(}(\vec{F_{\alpha}})_{\alpha\in
2^{r}},\vec{A}\big{)}\in\mathcal{F}\\}$

Given an initial segment $F_{\alpha,s}$ of a condition
$\big{(}(\vec{F_{\alpha}})_{\alpha\in 2^{r}},\vec{A}\big{)}$, it is not
necessarily possible to find an extension
$\big{(}(\vec{E_{\alpha}})_{\alpha\in 2^{r}},\vec{B}\big{)}$ with
$|E_{\alpha,s}|>|F_{\alpha,s}|$, since it might be the case that $A_{s}\cap
g^{-1}_{s}(\alpha(s))$ is empty. Thus, for any sufficiently generic filter
$\mathcal{F}$, the set $G^{\mathcal{F}}_{\alpha,s}$ might not be infinite.
However, there must necessarily exist some $\alpha\in 2^{r}$ such that every
$G^{\mathcal{F}}_{\alpha,s}$, $s<r$ is infinite. Given a condition
$c=\big{(}(\vec{F_{\alpha}})_{\alpha\in 2^{r}},\vec{A}\big{)}$ and a coloring
$h\in\mathcal{X}(1)$, define the set

$V_{h}(c)\coloneqq\\{\alpha\in 2^{r}:\forall s<r,A_{s}\cap
h^{-1}_{s}(\alpha(s))\neq\emptyset\\}$

of “valid” combinations. Note that if $d\leqslant c$, then $V_{h}(d)\subseteq
V_{h}(c)$. Moreover, $V_{g}(c)\neq\emptyset$ for every condition $c$. A
“valid” combination of a condition $c$ allows us to find an extension, as the
following lemma shows.

######  Lemma 3.14.

For all conditions $c\coloneqq\big{(}(\vec{F_{\alpha}})_{\alpha\in
2^{r}},\vec{A}\big{)}$, all $\beta\in V_{g}(c)$ and all $s<r$, there is an
extension $\big{(}(\vec{E_{\alpha}})_{\alpha\in 2^{r}},\vec{B}\big{)}$ such
that $|E_{\beta,s}|>|F_{\beta,s}|$.

###### Proof.

Let $\beta\in V_{g}(c)$ and $s<r$. By definition of $\beta$ consider $n\in
A_{s}\cap g^{-1}_{s}(\alpha(s))$. Define $(\vec{E_{\alpha}})_{\alpha\in
2^{r}}$ to be equal to $(\vec{F_{\alpha}})_{\alpha\in 2^{r}}$, except for
$E_{\beta,s}\coloneqq F_{\beta,s}\cup\\{n\\}$. Accordingly, define $\vec{B}$
to be equal to $\vec{A}$, except for $B_{s}\coloneqq A_{s}-\\{0,1,\dots,n\\}$.
Then $\big{(}(\vec{E_{\alpha}})_{\alpha\in 2^{r}},\vec{B}\big{)}$ is a
condition which satisfies the lemma. ∎

Fix an enumeration of Turing functionals $(\Psi_{e})_{e\in\mathbb{N}}$. For
any $e\in\mathbb{N}$, $j<3$ and $Z\in\mathcal{M}$ let

$\mathcal{R}_{e,j}^{Z}\coloneqq\Psi_{e}^{Z\oplus\vec{G}}\text{ is not an
infinite subset of }f^{-1}(j)$

######  Lemma 3.15.

For any $2^{r}$-tuple of integers $(e_{\alpha})_{\alpha\in 2^{r}}$, any
$2^{r}$-tuple of colors $(j_{\alpha})_{\alpha\in 2^{r}}$, any
$Z\in\mathcal{M}$, and any condition $c$, there is an extension forcing
$\bigvee_{\alpha\in V_{g}(c)}\mathcal{R}_{e_{\alpha},j_{\alpha}}^{Z}$.

###### Proof.

Let $c\coloneqq\big{(}(\vec{F_{\alpha}})_{\alpha\in 2^{r}},\vec{A}\big{)}$ be
a condition, and define $U(c)$ to be the $\Pi^{0}_{1}(\vec{A})$-class whose
elements are colorings $\widetilde{g}$ such that

$\forall s<r,\forall j<3,A_{s}\cap g_{s}^{-1}(j)=\emptyset\implies
A_{s}\cap\widetilde{g_{s}}^{-1}(j)=\emptyset$

in other words
$U(c)\coloneqq\\{\widetilde{g}:V_{\widetilde{g}}(c)=V_{g}(c)\\}$. Note that it
is non-empty since $g\in U(c)$. This will ensure that the $\widetilde{g}$ we
consider later have the same behavior as $g$ regarding $\vec{A}$.

Moreover, given $\alpha\in 2^{r}$, an $r$-tuple of finite sets $\vec{G}$
_satisfies_ $(\vec{F_{\alpha}},\vec{A})$ if $\forall s<r,G_{s}\supseteq
F_{\alpha,s}\text{ and }G_{s}-F_{\alpha,s}\subseteq A_{s}$

For every $n\in\mathbb{N}$ consider the class $\mathcal{Q}_{n}$ whose elements
are colorings $\widetilde{f}\in\mathcal{X}(0)$ such that

$\displaystyle\exists\widetilde{g}\in U(c),$ $\displaystyle\forall\alpha\in
V_{g}(c),\forall\vec{G}\text{ satisfying }(\vec{F_{\alpha}},\vec{A})$
$\displaystyle\text{if }\vec{G}\text{ is }\widetilde{g}\text{-homogeneous for
the colors }\alpha,$ $\displaystyle\text{then
}\Psi_{e_{\alpha}}^{Z\oplus\vec{G}}\cap\rrbracket
n,+\infty\llbracket\subseteq\widetilde{f}^{-1}(j_{\alpha})$

Note that $\mathcal{Q}_{n}$ is a $\Pi^{0}_{1}(\vec{A})$ class uniformly in
$n$. Indeed, the above formula is $\Pi^{0}_{1}(\vec{A})$, because by
compactness, the existence of $\widetilde{g}$ is equivalent to finding an
approximation in $\mathcal{X}_{m}(1)$ for any length $m\in\mathbb{N}$.
Moreover, the set $V_{g}(c)$ depends on $g$ which might be of arbitrary
complexity, but since it is finite, it does not affect the complexity of the
formula.

Case 1, $\exists n,\mathcal{Q}_{n}=3^{\mathbb{N}}$. Thus fix such an $n$ and
consider the class
$\mathcal{P}\coloneqq\\{(\widetilde{f},\widetilde{g})\in\mathcal{X}:\widetilde{g}\text{
is a witness of }\widetilde{f}\in\mathcal{Q}_{n}\\}$. Since $\mathcal{P}$ is a
left-full $\Pi^{0}_{1}(\vec{A})$-class and $\mathcal{M}$ is a cross-constraint
ideal, there are paths $(X^{i},Y^{i})_{i<2}\in\mathcal{P}^{2}$ such that

  * •

$(X^{0},X^{1})$ is finitely compatible

  * •

for any $s<r$, $(Y^{0}_{s},Y^{1}_{s})$ is infinitely compatible on $A_{s}$

  * •

$(X^{0},Y^{0})\oplus(X^{1},Y^{1})\in\mathcal{M}$

From the second item, define $\beta\in 2^{r}$ to be colors such that $\forall
s<r,(Y^{0}_{s})^{-1}(\beta(s))\cap(Y^{1}_{s})^{-1}(\beta(s))\cap A_{s}\text{
is infinite}$. Note that $\beta\in V_{Y_{0}}(c)\cap V_{Y_{1}}(c)$. Since
$g,Y^{0},Y^{1}\in U(c)$, then $V_{Y_{0}}(c)=V_{Y_{1}}(c)=V_{g}(c)$, so
$\beta\in V_{g}(c)$. For each $s<r$, let
$B_{s}=(Y^{0}_{s})^{-1}(\beta(s))\cap(Y^{1}_{s})^{-1}(\beta(s))\cap A_{s}$,
and define $\vec{B}\coloneqq(B_{0},\ldots,B_{r-1})$. We claim that
$((\vec{F_{\alpha}})_{\alpha\in 2^{r}},\vec{B})$ is the extension we are
looking for. Indeed, since $(X^{i},Y^{i})_{i<2}\in\mathcal{P}^{2}$, then for
every $\vec{G}$ compatible with $(F_{\beta},\vec{B})$, we have
$\Psi^{Z\oplus\vec{G}}_{e_{\beta}}\cap\rrbracket
n,+\infty\llbracket\,\subseteq{X_{0}}^{-1}(j_{\beta})\cap{X_{1}}^{-1}(j_{\beta})$.
Since ${X_{0}}^{-1}(j_{\beta})\cap{X_{1}}^{-1}(j_{\beta})$ is finite, the
requirement $\mathcal{R}_{e_{\beta},j_{\beta}}^{Z}$ is satisfied, so
$\bigvee_{\alpha\in V_{g}(c)}\mathcal{R}_{e_{\alpha},j_{\alpha}}^{Z}$ is
satisfied as well.

Case 2, $\forall n,\mathcal{Q}_{n}\neq 3^{\mathbb{N}}$.

In which case, for each $n\in\mathbb{N}$, there is some
$f_{n}\notin\mathcal{Q}_{n}$ and $\ell_{n}\in\mathbb{N}$ such that

$\displaystyle\forall\widetilde{g}\in U(c),$ $\displaystyle\exists\beta\in
V_{g}(c),\exists\vec{H}\text{ satisfying }(\vec{F_{\beta}},\vec{A}),$
$\displaystyle\vec{H}\text{ is }\widetilde{g}\text{-homogeneous for the colors
}\beta$ $\displaystyle\text{ and
}\Psi_{e_{\beta}}^{Z\oplus\vec{H}}\cap\rrbracket
n,\ell_{n}\llbracket\nsubseteq f_{n}^{-1}(j_{\beta})$

This implies that there is an $\vec{A}$-computable array
$(E_{n,0},E_{n,1},E_{n,2})_{n\in\mathbb{N}}$ such that

$\displaystyle\forall\widetilde{g}\in U(c),$ $\displaystyle\exists\beta\in
V_{g}(c),\exists\vec{H}\text{ satisfying }(\vec{F_{\beta}},\vec{A}),$
$\displaystyle\vec{H}\text{ is }\widetilde{g}\text{-homogeneous for the colors
}\beta$ $\displaystyle\text{ and
}\Psi_{e_{\beta}}^{\vec{A}\oplus\vec{H}}\cap\rrbracket
n,\ell_{n}\llbracket\nsubseteq E_{n}(j_{\beta})$

Indeed, for each $n$, the set $\rrbracket n,\ell_{n}\llbracket$ can be
partitioned into $(\\{m:f_{n}(m)=j\\})_{j<3}$, so it is sufficient to search
for a coloring satisfying the above properties, as the search must end.

The coloring $f$ is hyperimmune relative to $\vec{A}$, because
$\vec{A}\in\mathcal{M}$. Hence there is some $n\in\mathbb{N}$ such that
$\forall j<3,E_{n,j}\subseteq f^{-1}(j)$. Moreover, we have
$E_{n,j}=f^{-1}(j)\cap\rrbracket n,\ell_{n}\llbracket$. So, by considering
$g$, we obtain

$\displaystyle\exists\beta\in V_{g}(c),\exists\vec{H}\text{ satisfying
}(\vec{F_{\beta}},\vec{A}),$ $\displaystyle\vec{H}\text{ is
}g\text{-homogeneous for the colors }\beta$ $\displaystyle\text{ and
}\Psi_{e_{\beta}}^{Z\oplus\vec{H}}\cap\rrbracket
n,\ell_{n}\llbracket\nsubseteq f^{-1}(j_{\beta})$

Finally, the extension we are looking for is
$\big{(}\\{\vec{F_{\alpha}}\\}_{\alpha\neq\beta\in
2^{r}}\cup\\{\vec{H}\\},\vec{A}-\\{0,\ldots,\max\vec{H}\\}\big{)}$. This
completes the proof of Lemma 3.15. ∎

Let $c_{0}$ be a condition such that $V_{g}(c_{0})$ is minimal for inclusion.
Let $V=V_{g}(c_{0})$. Let $\mathcal{F}$ be a sufficiently generic filter
containing $c_{0}$. In particular, $V=V_{g}(c)$ for every $c\in F$. By Lemma
3.14, for every $\alpha\in V$ and every $s<r$, $G^{\mathcal{F}}_{\alpha,s}$ is
infinite. Moreover, by Lemma 3.15, for every $Z\in\mathcal{M}$, for every
$2^{r}$-tuple of integers $(e_{\alpha})_{\alpha\in 2^{r}}$ and every
$2^{r}$-tuple of colors $(j_{\alpha})_{\alpha\in 2^{r}}$,
$\vec{G}^{\mathcal{F}}$ satisfies $\bigvee_{\alpha\in
V}\mathcal{R}^{Z}_{e_{\alpha},j_{\alpha}}$. By a pairing argument, for every
$Z\in\mathcal{M}$, there is some $\alpha\in V$ such that
$Z\oplus\vec{G}^{\mathcal{F}}_{\alpha}$ does not compute any infinite
$f$-homogeneous set. Since $\mathcal{M}=\\{Z_{0},Z_{1},\dots\\}$ is countable,
by the infinite pigeonhole principle, there exists some $\alpha\in V$ such
that for infinitely many $n\in\mathbb{N}$, $Z_{0}\oplus\dots\oplus
Z_{n}\oplus\vec{G}^{\mathcal{F}}_{\alpha}$ does not compute any infinite
$f$-homogeneous set. By downward-closure of this property under the Turing
reduction, it holds for every $n$. This completes the proof of Theorem 3.13. ∎

Our first parameterized theorem has applications in terms of strong non-
reducibility between non-computable instances of $\mathsf{RT}^{1}_{k+1}$ and
$(\mathsf{RT}^{1}_{k})^{*}$ (Theorem 5.20) and non-reducibility between
computable instances of $\mathsf{SRT}^{2}_{k+1}$ and
$(\mathsf{SRT}^{2}_{k})^{*}$ (Theorem 5.21). We now prove a second
parameterized theorem which enables us to prove separations between computable
instances of Ramsey’s theorem for pairs. Note that in the following theorem,
the colorings $g_{0},\dots,g_{r-1}$ are required to belong to $\mathcal{M}$,
contrary to Theorem 3.13.

######  Theorem 3.16.

Let $\mathcal{M}$ be a countable cross-constraint ideal such that
$\mathcal{M}\models\mathsf{COH}$ and let $f:\mathbb{N}\to 3$ be hyperimmune
relative to any element of $\mathcal{M}$, then for any $r\in\mathbb{N}$ and
any $g_{0},\dots,g_{r-1}:[\mathbb{N}]^{2}\to 2$ in $\mathcal{M}$, there are
infinite $g_{i}$-homogeneous sets $G_{i}$ for every $i<r$, such that
$\bigoplus_{i<r}G_{i}$ does not compute any infinite $f$-homogeneous set.

###### Proof.

First, consider the sequence of sets
$\vec{R}\coloneqq(R_{x,j,i})_{x\in\mathbb{N},j<2,i<r}$ defined by
$R_{x,j,i}\coloneqq\\{y:g_{i}(x,y)=j\\}$. This sequence is in $\mathcal{M}$,
because $\forall i<r,g_{i}\in\mathcal{M}$. And since
$\mathcal{M}\models\mathsf{COH}$, there is an infinite $\vec{R}$-cohesive set
$C\coloneqq\\{c_{0}<c_{1}<\ldots\\}\in\mathcal{M}$. By choice of $\vec{R}$,
for each $i<r$, the coloring $g_{i}\\!{\upharpoonright}_{[C]^{2}}$ is stable
Indeed, for $x\in\mathbb{N}$ and $i<r$, there is exactly one $j<2$ for which
$C\subseteq^{*}R_{x,j,i}$, and so this implies that $\lim_{y\in
C}g_{i}(x,y)=j$.

Now let $h_{i}:\mathbb{N}\to 2,n\mapsto\lim_{m}g_{i}(c_{n},c_{m})$, and
$\vec{h}\coloneqq(h_{0},\ldots,h_{r-1})$. By Theorem 3.13 with
$(f,(h_{i})_{i<r})$, there are infinite $\vec{h}$-homogeneous sets $\vec{H}$
such that, for any $Z\in\mathcal{M}$, $\vec{H}\oplus Z$ does not compute an
infinite $f$-homogeneous set. In particular this is true for
$Z\coloneqq\bigoplus_{i<r}C_{i}$, and since for any $i<r$, $H_{i}\oplus C_{i}$
computes an infinite $g_{i}$-homogeneous set $G_{i}$, we deduce that
$\bigoplus_{i<r}G_{i}$ does not compute any infinite $f$-homogeneous set. ∎

##  4 Cross-constraint basis theorems

As mentioned before, the two main theorems of Section 3 are parameterized by
cross-constraint ideals, which are themselves built using iterated
applications of the cross-constraint principle ($\mathsf{CC}$). In this
section, we prove various basis theorems for $\mathsf{CC}$, namely, the
$\Delta^{0}_{2}$, low, cone avoidance, and non-$\Sigma^{0}_{1}$ preservation
basis theorems. The $\Delta^{0}_{2}$ and cone avoidance basis theorems for
$\mathsf{CC}$ were previously proven by Liu [22], but we give a new proof of
the cone avoidance basis theorem which resembles more its classical
counterpart for $\Pi^{0}_{1}$ classes.

###  4.1 Conditions

The most famous basis theorems for $\Pi^{0}_{1}$ classes are all proven using
effective versions of forcing with binary trees. Similarly, all the basis
theorems for $\mathsf{CC}$ in this section will be proven with effective
variants of the same notion of forcing that we now describe.

######  Definition 4.1.

For $k\in\mathbb{N}$ and $m\leqslant n\in\mathbb{N}$, given chains
$\rho^{0},\rho^{1}\in k^{m}$, $\mu^{0},\mu^{1}\in k^{n}$, and
$\tau^{0},\tau^{1}\in k^{n-m}$ such that $\forall
i<2,\mu^{i}=\rho^{i}\cdot\tau^{i}$. We say that $(\mu^{0},\mu^{1})$ is
_completely incompatible over $(\rho^{0},\rho^{1})$_ if $\forall
i<n-m,\tau^{0}(i)\neq\tau^{1}(i)$. When
$(\rho^{0},\rho^{1})=(\varepsilon,\varepsilon)$, we simply say _completely
incompatible_.

######  Definition 4.2.

A _condition-tuple_ for a class $\mathcal{P}\subseteq\mathcal{X}$ is a tuple
$(\rho^{i},\sigma^{i})_{i<2}\in\mathcal{X}_{<\mathbb{N}}^{2}$ such that
$\mathcal{P}$ is left-full below $(\rho^{i},\sigma^{i})$ for both $i<2$, and
$|\rho^{0}|=|\rho^{1}|$. A condition-tuple
$(\widehat{\rho}^{i},\widehat{\sigma}^{i})_{i<2}$ _extends_ another
$(\rho^{i},\sigma^{i})_{i<2}$, written
$(\widehat{\rho}^{i},\widehat{\sigma}^{i})_{i<2}\leq(\rho^{i},\sigma^{i})_{i<2}$,
if

  1. 1.

for both $i<2$,
$(\widehat{\rho}^{i},\widehat{\sigma}^{i})\succcurlyeq(\rho^{i},\sigma^{i})$

  2. 2.

$(\widehat{\rho}^{0},\widehat{\rho}^{1})$ is completely incompatible over
$(\rho^{0},\rho^{1})$

######  Remark 4.3.

A pair $(\rho^{i},\sigma^{i})$ of a condition-tuple is seen as a finite
approximation of some $(X^{i},Y^{i})\in\mathcal{P}$ we wish to build, i.e. of
an element in $\mathcal{P}\cap\left[(\rho^{i},\sigma^{i})\right]$, such that
$(X^{0},X^{1})$ is completely incompatible over $(\rho^{0},\rho^{1})$.

###  4.2 Cross-constraint $\Delta^{0}_{2}$ basis theorem

The following $\Delta^{0}_{2}$ basis theorem is an effective analysis of the
simplest known combinatorial proof of the cross-constraint problem. It was
proven by Liu [22]. We provide the original proof as a warmup for the next
basis theorems and for the sake of completeness.

######  Theorem 4.4 (Liu [22, Lemma 2.2]).

Any left-full computable instance $T$ of $\mathsf{CC}$ has a solution
$(X^{i},Y^{i})_{i<2}$ such that
$(X^{0},Y^{0})\oplus(X^{1},Y^{1})\leqslant_{T}\emptyset^{\prime}$.

###### Proof.

Let $\mathcal{P}\coloneqq[T]$. We build a $\emptyset^{\prime}$-computable
sequence of condition-tuples
$(\rho^{i}_{0},\sigma^{i}_{0})_{i<2}\geq(\rho^{i}_{1},\sigma^{i}_{1})_{i<2}\geq\ldots$,
such that, for $i<2$ the functions $X^{i}:=\bigcup_{t}\rho^{i}_{t}$ and
$Y^{i}:=\bigcup_{t}\sigma^{i}_{t}$ are the desired witnesses. To simplify
notation, we simply say condition for condition-tuple.

Given a condition $(\rho^{i}_{t},\sigma^{i}_{t})_{i<2}$, we want to extend it
to $(\rho^{i}_{t+1},\sigma^{i}_{t+1})_{i<2}$ such that for all $s<r$,
$(\sigma^{0}_{t+1,s},\sigma^{1}_{t+1,s})$ is not completely incompatible over
$(\sigma^{0}_{t,s},\sigma^{1}_{t,s})$. We proceed as follows: say
$(\rho^{i}_{t},\sigma^{i}_{t})_{i<2}$ has been constructed, search for an
extension $(\rho^{i}_{t+1},\sigma^{i}_{t+1})_{i<2}$ such that the property
above holds. By Lemma 3.7, this search requires the use of
$\emptyset^{\prime}$ to check whether $\mathcal{P}$ is left-full below
$(\rho^{i}_{t+1},\sigma^{i}_{t+1})$ or not (for each i).

If there is always such an extension, then the construction is complete.
Otherwise, for some condition $(\rho^{i}_{t},\sigma^{i}_{t})_{i<2}$, there is
some $s<r$ such that all extensions are completely incompatible over
$(\sigma^{0}_{t,s},\sigma^{1}_{t,s})$. Such a condition is said to _exclude
component $s<r$_. Nevertheless, by considering the following lemma, the
construction can be completed.

######  Lemma 4.5.

If a condition $(\rho^{i},\sigma^{i})_{i<2}$ excludes component $s<r$, then
for every $i<2$, there is a coloring $Y\in 2^{\mathbb{N}}$ such that for every
$(\widehat{\rho},\widehat{\sigma})\leqslant(\rho^{i},\sigma^{i})$, if
$\mathcal{P}$ is left-full below $(\widehat{\rho},\widehat{\sigma})$, then
$\widehat{\sigma}_{s}$ is compatible with $Y$.

###### Proof.

Fix $(\rho^{i},\sigma^{i})_{i<2}$ such that it excludes component $s<r$ and
fix $i<2$.

Suppose first that for cofinitely many $n\in\mathbb{N}$, there exists a
$k_{n}<2$ such that for every
$(\rho^{\prime},\sigma^{\prime})\leq(\rho^{i},\sigma^{i})$ for which
$\mathcal{P}$ is left-full, if $|\sigma^{\prime}_{s}|>n$ then
$\sigma^{\prime}_{s}(n)=k_{n}$. Then let $Y(n)\coloneqq k_{n}$. This is well-
defined since by Lemma 3.8, there exist suitable extensions of every length.

Suppose now that for infinitely many $n\in\mathbb{N}$, for every $k<2$, there
is a $(\rho^{\prime},\sigma^{\prime})\leq(\rho^{i},\sigma^{i})$ for which
$\mathcal{P}$ is left-full and such that $\sigma^{\prime}_{s}(n)\neq k$. Fix
$n>|\sigma^{i}_{s}|$, and for each $k<2$, let
$(\rho_{k},\sigma_{k})\leq(\rho^{i},\sigma^{i})$ be a condition extension such
that $\sigma_{k,s}(n)\neq k$.

Since we are working in a 3-valued realm, there exists a
$\widetilde{\rho}\succcurlyeq\rho^{1-i}$ of length greater than
$\max(|\rho_{0}|,|\rho_{1}|)$ such that both $(\widetilde{\rho},\rho_{0})$ and
$(\widetilde{\rho},\rho_{1})$ are completely incompatible over
$(\rho^{1-i},\rho^{i})$. Pick any pair
$(\widehat{\rho}^{1-i},\widehat{\sigma}^{1-i})\leq(\widetilde{\rho},\sigma^{1-i})$
for which $\mathcal{P}$ is left-full and such that
$|\widehat{\sigma}_{s}^{1-i}|>n$, this is possible by Lemma 3.8. Let
$k=\widehat{\sigma}_{s}^{1-i}(n)$. Then
$(\widehat{\rho}^{1-i},\widehat{\sigma}^{1-i},\rho_{k},\sigma_{k})$ is an
extension contradicting the fact that $(\rho^{i},\sigma^{i})_{i<2}$ excludes
component $s<r$ ∎

If at some point in the construction the condition
$(\rho^{i}_{t},\sigma^{i}_{t})_{i<2}$ excludes the components of $I\subseteq
r$, then we restart the construction from the begining with
$(\rho^{i}_{0},\sigma^{i}_{0})_{i<2}:=(\rho^{0}_{t},\sigma^{0}_{t},\rho^{0}_{t},\sigma^{0}_{t})$.
The lemma ensures that $(Y^{0}_{s},Y^{1}_{s})$ will not be finitely compatible
for all $s\in I$, no matter the conditions selected for the sequence. And
since $r$ is a standard integer, the construction can only be restarted a
finite number of times. ∎

######  Remark 4.6.

The fact that $X^{i}$ is an instance of $\mathsf{RT}^{1}_{3}$ whereas each
$Y^{i}_{s}$ is an instance of $\mathsf{RT}^{1}_{2}$ is exploited in the proof
of Lemma 4.5, to ensure the existence of a 3-valued string $\widetilde{\rho}$
completely incompatible with two other strings simultaneously.

######  Corollary 4.7.

The class of all arithmetic sets is a cross-constraint ideal.

###  4.3 Combinatorial lemmas

All the remaining basis theorems will involve some kind of first-jump control.
They will require a much more involved combinatorial machinery that we now
develop. These combinatorics are all due to Liu [22], with a slightly
different organization and terminology.

######  Definition 4.8.

For $k\in\mathbb{N}$ and $m\leqslant n\in\mathbb{N}$, given chains
$\rho^{0},\rho^{1}\in k^{\leqslant m}$, a total function $\varphi:k^{m}\to
k^{n}$ _preserves incompatibility over $(\rho^{0},\rho^{1})$_ if

  1. 1.

$\forall\mu\in k^{m},\varphi(\mu)\succcurlyeq\mu$

  2. 2.

For all $\mu^{0},\mu^{1}\in k^{m}$ such that
$(\mu^{0},\mu^{1})\succcurlyeq(\rho^{0},\rho^{1})$, the pair
$(\varphi(\mu^{0}),\varphi(\mu^{1}))$ is completely incompatible over
$(\mu^{0},\mu^{1})$

######  Remark 4.9.

Note that for $\widehat{\rho}^{0},\widehat{\rho}^{1}\in k^{\leqslant n}$
extending $\rho^{0},\rho^{1}$ respectively, if $\varphi$ preserves
incompatibility over $(\rho^{0},\rho^{1})$ then it also preserves
incompatibility over $(\widehat{\rho}^{0},\widehat{\rho}^{1})$.

The following two lemmas are purely technical ones, used only locally to
obtain the main combinatorial lemmas of this section.

######  Lemma 4.10 (Liu [22, Lemma 4.3]).

For any $n\leqslant n^{\prime}\leqslant m\in\mathbb{N}$, $\widehat{\rho}\in
3^{m}$ extending $\rho\in 3^{n}$, and any map $\psi:3^{n}\to 3^{n^{\prime}}$
preserving incompatibility over $(\varepsilon,\varepsilon)$ such that
$\psi(\rho)\preccurlyeq\widehat{\rho}$, there is a map $\varphi:3^{n}\to
3^{m}$ extending $\psi$ and preserving incompatibility over
$(\varepsilon,\varepsilon)$, such that $\varphi(\rho)=\widehat{\rho}$.

###### Proof.

To give an intuition, if we just wanted to show the existence of a map
$\varphi:3^{n}\to 3^{m}$ preserving incompatibility over
$(\varepsilon,\varepsilon)$, we could have taken the function which maps
$\eta\in 3^{n}$ to $\eta\cdot a^{m-n}$ where $a\coloneqq\eta(0)$.

Fix $\rho$, $\widehat{\rho}$ and $\psi$ as in the statement of the lemma, and
let $\tau$ be such that $\rho\cdot\tau=\widehat{\rho}$. For every $a<3$, let
$\tau_{a}\in 3^{m-n^{\prime}}$ be defined by
$\tau_{a}(x)=\tau(x)+a-\rho(0)\mod 3$. In particular, $\tau_{\rho(0)}=\tau$
and for every $a\neq b$, $\tau_{a}$ and $\tau_{b}$ are preserving
incompatibility over $(\varepsilon,\varepsilon)$.

Let $\varphi$ be the function $\varphi^{\prime}\circ\psi$ where
$\varphi^{\prime}$ maps $\eta\in 3^{n}$ to $\eta\cdot\tau_{\eta(0)}$. Note
that $\varphi^{\prime}(\rho)=\rho\cdot\tau_{\rho(0)}=\widehat{\rho}$.
Moreover, if $\mu,\nu\in 3^{n}$ are completely incompatible, then
$\psi(\mu)(0)\neq\psi(\nu)(0)$, hence $\tau_{\mu(0)}$ and $\tau_{\nu(0)}$ are
completely incompatible. It follows that $\varphi(\mu)=\mu\cdot\tau_{\mu(0)}$
and $\varphi(\nu)=\nu\cdot\tau_{\nu(0)}$ are completely incompatible
themselves. ∎

######  Lemma 4.11 (Liu [22, Lemma 4.4]).

Let $N\in\mathbb{N}$ and
$f:3^{<\mathbb{N}}\to\mathfrak{P}\big{(}\mathcal{X}_{N}(1)\big{)}$ be a total
and non-increasing function. For every $n\in\mathbb{N}$, there is
$m\in\mathbb{N}$ and a map $\varphi:3^{n}\to 3^{m}$ preserving incompatibility
over $(\varepsilon,\varepsilon)$, such that $\forall\rho\in
3^{n},\forall\nu\in\mathcal{X}_{N}(1)$ either
$\forall\widehat{\rho}\succcurlyeq\varphi(\rho),\nu\in f(\widehat{\rho})$ or
$\nu\notin f(\varphi(\rho))$.

###### Proof.

We construct a finite sequence of integers $(n_{s})_{s\leqslant p}$, for some
$p\in\mathbb{N}$, along with a finite sequence of maps
$(\varphi_{s}:3^{n_{0}}\to 3^{n_{s}})_{s\leq p}$ preserving incompatibility
over $(\varepsilon,\varepsilon)$.

For each $\nu\in\mathcal{X}_{N}(1)$ and $\rho\in 3^{n}$ there is a step to
ensure that the map $\varphi$ we construct satisfies the requirement

$\mathcal{R}_{\nu,\rho}\coloneqq\forall\widehat{\rho}\succcurlyeq\varphi(\rho),\nu\in
f(\widehat{\rho})\text{ or }\nu\notin f(\varphi(\rho))$

Let $n_{0}\coloneqq n$ and $\varphi_{0}:3^{n_{0}}\to 3^{n_{0}}$ be the
identity function. At step $s<p$, consider $\nu\in\mathcal{X}_{N}(1)$ and
$\rho\in 3^{n}$. If $\forall\widehat{\rho}\succcurlyeq\varphi_{s}(\rho),\nu\in
f(\widehat{\rho})$ we are done by defining $n_{s+1}\coloneqq n_{s}$ and
$\varphi_{s+1}\coloneqq\varphi_{s}$. Otherwise there is $\eta$ extending
$\varphi_{s}(\rho)$ such that $\nu\notin f(\eta)$. Define
$n_{s+1}\coloneqq|\eta|$, and use Lemma 4.10 to find a map
$\varphi_{s+1}:3^{n}\to 3^{n_{s+1}}$ extending $\varphi_{s}$, preserving
incompatibility over $(\varepsilon,\varepsilon)$, and such that
$\varphi_{s+1}(\rho)=\eta$. So, under the assumption made on $f$ we have that
$\forall\widehat{\eta}\succcurlyeq\eta,f(\widehat{\eta})\subseteq f(\eta)$,
and thus $\forall\widehat{\eta}\succcurlyeq\eta,\nu\notin f(\widehat{\eta})$.
Then as $\varphi_{s+1}$ extends $\varphi_{s}$, $\mathcal{R}_{\nu,\rho}$ is
fulfilled.

Finally, define $m\coloneqq n_{p}$ and $\varphi\coloneqq\varphi_{p}$. By the
hypothesis made on the function $f$, for every $\nu\in\mathcal{X}_{N}(1)$, if
$\nu\in f(\varphi(\rho))$ for some $\rho\in 3^{n}$, then
$\forall\widehat{\rho}\succcurlyeq\varphi(\rho),\nu\in f(\widehat{\rho})$ ∎

The following definition should be understood in the light of the first-jump
control for $\Pi^{0}_{1}$ classes. When trying to construct an infinite path
through an infinite binary tree $T\subseteq 2^{<\omega}$, one must ensure that
at every step, the node is _extensible_ , that is, the branch below the node
is infinite. Being extensible is a $\Pi^{0}_{1}$ property, and therefore to
obtain a good first-jump control, one must resort to an overapproximation:
Given a set $A\subseteq 2^{<\omega}$, instead of asking whether there is an
extensible node in $T\cap A$, one will ask whether there is a level in the
tree such that every node at this level belongs to $A$. Among the nodes at
that level, at least one must be extendible. If $A$ is $\Sigma^{0}_{1}$, then
the former question is $\Sigma^{0}_{2}$, while the latter is $\Sigma^{0}_{1}$.

One can use a different technique, and ask whether the $\Pi^{0}_{1}$ class
$\mathcal{P}$ of infinite subtrees of $T$ disjoint from $A$ is empty. In
particular, by considering $S\subseteq T$, the pruned subtree of $T$
containing only extendible nodes, since $S\not\in\mathcal{P}$, there is an
extendible node in $S\cap A$. Here again, this overapproximation is
$\Sigma^{0}_{1}$.

In the case of cross-constraint problems, a node $(\rho,\sigma)$ is extensible
in a cross-tree $T$ if $T$ is left-full below $(\rho,\sigma)$. The notion of
$T$-sufficiency below is therefore the counterpart of the $\Sigma^{0}_{1}$
question above, mutatis mutandis.

######  Definition 4.12 (Liu [22, Definition 4.22]).

Given a tree $T\subseteq\mathcal{X}$, and a tuple
$(\rho^{i},\sigma^{i})_{i<2}\in\mathcal{X}_{<\mathbb{N}}^{2}$, a set
$A\subseteq\mathcal{X}_{<\mathbb{N}}^{2}$ is _$T$ -sufficient over
$(\rho^{i},\sigma^{i})_{i<2}$_ if, for every infinite subtree $S\subseteq T$
for which $(\rho^{i},\sigma^{i})_{i<2}$ is a condition-tuple, there is a tuple
$(\widehat{\rho}^{i},\widehat{\sigma}^{i})_{i<2}\in A\cap S^{2}$ such that
$\forall
i<2,(\widehat{\rho}^{i},\widehat{\sigma}^{i})\succcurlyeq(\rho^{i},\sigma^{i})$,
and $(\widehat{\rho}^{0},\widehat{\rho}^{1})$ is completely incompatible over
$(\rho^{0},\rho^{1})$.

Note that if $A$ is $\Sigma^{0}_{1}$, then the statement “$A$ is
$T$-sufficient over $(\rho^{i},\sigma^{i})_{i<2}$” is $\Sigma^{0}_{1}(T)$. The
combinatorics for the cross-constraint problem are more complicated than the
ones for weak König’s lemma, and one cannot simply consider the pruned tree
containing only extensible nodes. However, the following lemmas show that one
can consider a weakly pruned tree in which every node is almost extensible, in
the sense that every node can be extended into a node below which the cross-
tree is left-full.

The following lemma uses compactness to give a finite cross-tree version of
$T$-sufficiency. Recall that the notion of left-fullness was extended to
finite trees, which induces a notion of condition-tuple. Given a set
$S\subseteq\mathcal{X}_{<\mathbb{N}}$, we write $\ell_{N}(S)$ for the set of
pairs $(\rho,\sigma)\in S$ such that $|\rho|=|\sigma|=N$.

######  Lemma 4.13.

Let $T\subseteq\mathcal{X}$ be a cross-tree. If
$A\subseteq\mathcal{X}_{<\mathbb{N}}^{2}$ is $T$-sufficient over
$(\rho^{i},\sigma^{i})_{i<2}\in\mathcal{X}_{<\mathbb{N}}^{2}$, then there is
$N\in\mathbb{N}$ such that for every finite cross-subtree $S\subseteq
T\cap\mathcal{X}_{\leq N}$ for which $(\rho^{i},\sigma^{i})_{i<2}$ is a
condition-tuple, there is a tuple
$(\widehat{\rho}^{i},\widehat{\sigma}^{i})_{i<2}\in A\cap S^{2}$ such that
$\forall
i<2,(\widehat{\rho}^{i},\widehat{\sigma}^{i})\succcurlyeq(\rho^{i},\sigma^{i})$,
and $(\widehat{\rho}^{0},\widehat{\rho}^{1})$ is completely incompatible over
$(\rho^{0},\rho^{1})$.

###### Proof.

Consider the class $\mathcal{T}$ of finite subtrees $S\subseteq T$ whose
leaves are all of the same length, such that $S$ is left-full below
$(\rho^{i},\sigma^{i})$ for both $i<2$, and such that for all tuple
$(\widehat{\rho}^{i},\widehat{\sigma}^{i})_{i<2}\in S^{2}$ which extends
$(\rho^{i},\sigma^{i})$ and such that
$(\widehat{\rho}^{0},\widehat{\rho}^{1})$ is completely incompatible over
$(\rho^{0},\rho^{1})$, then $(\widehat{\rho}^{0},\widehat{\rho}^{1})\notin A$.
It forms a tree for the relation where $S_{0}\leqslant S_{1}$ if and only if
$S_{1}\\!{\upharpoonright}_{h(S_{0})}=S_{0}$.

There is no infinite path in $\mathcal{T}$, otherwise it would contradict the
assumption that $A$ is $T$-sufficient. Hence $\mathcal{T}$ is finite thanks to
König’s lemma. In other words, there is $N\in\mathbb{N}$ such that, for any
finite subtree $S\subseteq T\cap\mathcal{X}_{\leq N}$ left-full below both
$(\rho^{i},\sigma^{i})$, there is
$(\widehat{\rho}^{i},\widehat{\sigma}^{i})\in A\cap S^{2}$ witnessing the
$T$-sufficiency of $A$. ∎

The following lemma is the desired combinatorial lemma.

######  Lemma 4.14 (Liu [22, Subclaim 4.7]).

Let $T\subseteq\mathcal{X}$ be a cross-tree. If
$A\subseteq\mathcal{X}_{<\mathbb{N}}^{2}$ is $T$-sufficient over
$(\rho^{i},\sigma^{i})_{i<2}\in\mathcal{X}_{<\mathbb{N}}^{2}$ and closed under
the suffix relation, then there is a condition-tuple in $A$ which extends
$(\rho^{i},\sigma^{i})_{i<2}$.

###### Proof.

Let $N\in\mathbb{N}$ witness Lemma 4.13. For $i<2$, define the maps

$\displaystyle f_{i}:3^{<\mathbb{N}}$
$\displaystyle\to\mathfrak{P}\big{(}\mathcal{X}_{N-|\sigma^{i}|}(1)\big{)}$
$\displaystyle\tau$
$\displaystyle\mapsto\left\\{\nu:(\rho^{i}\cdot\tau,\sigma^{i}\cdot\nu)\in
T\right\\}$

And consider the map $f:\tau\mapsto f_{0}(\tau)\cup f_{1}(\tau)$.

Since $T$ is left-full below $(\rho^{i},\sigma^{i})$ for both $i<2$, then by
Lemma 3.8, $\forall\tau,f(\tau)\neq\emptyset$. Moreover, each $f_{i}$ is non-
decreasing since $T$ is a cross-tree, so $f$ is also non-decreasing. Thus we
can apply Lemma 4.11 on $f$ to obtain $L\in\mathbb{N}$ and a map
$\psi:3^{N-|\rho^{0}|}\to 3^{L}$ preserving incompatibility over
$(\rho^{0},\rho^{1})$ such that, for any
$\tau\in\mathcal{X}_{N-|\rho^{0}|}(0)$ and any
$\nu\in\mathcal{X}_{N-|\sigma^{i}|}(1)$ either $T$ is left-full below
$(\rho^{i}\cdot\psi(\tau),\sigma^{i}\cdot\nu)$ or
$(\rho^{i}\cdot\psi(\tau),\sigma^{i}\cdot\nu)\notin T$. In other word, $\psi$
is such that

$\displaystyle\big{(}\rho^{i}\cdot\psi(\tau),\sigma^{i}\cdot\nu\big{)}\in
T\implies T\text{ is left-full below
}\big{(}\rho^{i}\cdot\psi(\tau),\sigma^{i}\cdot\nu\big{)}$ (4.1)

Now for each $i<2$, define the set

$B_{i}\coloneqq\big{\\{}(\rho^{i}\cdot\tau,\sigma^{i}\cdot\nu)\in
T:(\tau,\nu)\in\mathcal{X}\text{ and
}(\rho^{i}\cdot\psi(\tau),\sigma^{i}\cdot\nu)\in T\big{\\}}$

And consider $S\subseteq T$, the downward-closure of $B_{0}\cup B_{1}$. We
claim that $S$ is a cross-subtree of $T$ for which
$(\rho^{i},\sigma^{i})_{i<2}$ is a condition-tuple.

Indeed, fix some $i<2$ and let $\tau\in 3^{N-|\rho^{i}|}$. Since $T$ is left-
full below $(\rho^{i},\sigma^{i})$, by Lemma 3.8, there is some
$\nu\in\mathcal{X}_{N-|\sigma^{i}|}(1)$ such that
$(\rho^{i}\cdot\psi(\tau),\sigma^{i}\cdot\nu)\in T$. Thus, by 4.1, $T$ is
left-full below $(\rho^{i}\cdot\psi(\tau),\sigma^{i}\cdot\nu)$ and by
definition of $B_{i}$, $(\rho^{i}\cdot\tau,\sigma^{i}\cdot\nu)\in
B_{i}\subseteq S$. Thus $S$ is left-full below $(\rho^{i},\sigma^{i})$.

By Lemma 4.13, there is a tuple
$(\widehat{\rho}^{i},\widehat{\sigma}^{i})_{i<2}\in A\cap S^{2}$ such that
$\forall
i<2,(\widehat{\rho}^{i},\widehat{\sigma}^{i})\succcurlyeq(\rho^{i},\sigma^{i})$,
and $(\widehat{\rho}^{0},\widehat{\rho}^{1})$ is completely incompatible over
$(\rho^{0},\rho^{1})$. Since $A$ is closed under suffix, we can suppose
without loss of generality that
$|\widehat{\rho}^{i}|=|\widehat{\sigma}^{i}|=N$, hence that
$(\widehat{\rho}^{i},\widehat{\sigma}^{i})\in B_{i}$. Let
$\tau^{i}\in\mathcal{X}_{N-|\rho^{i}|}(0)$ and
$\nu^{i}\in\mathcal{X}_{N-|\sigma^{i}|}(1)$ be such that
$\widehat{\rho}^{i}=\rho^{i}\cdot\tau^{i}$ and
$\widehat{\sigma}^{i}=\sigma^{i}\cdot\nu^{i}$. By definition of $B_{i}$,
$(\rho^{i}\cdot\psi(\tau^{i}),\sigma^{i}\cdot\nu^{i})\in T$, thus by Equation
4.1, $T$ is left-full below
$(\rho^{i}\cdot\psi(\tau^{i}),\sigma^{i}\cdot\nu^{i})$. Thus,
$(\rho^{i}\cdot\psi(\tau^{i}),\sigma^{i}\cdot\nu^{i})_{i<2}$ is a condition-
tuple for $[T]$. Moreover, since $\psi$ preserves incompatibility over
$(\rho^{0},\rho^{1})$,
$(\rho^{i}\cdot\psi(\tau^{i}),\sigma^{i}\cdot\nu^{i})_{i<2}$ is an extension
of $(\rho^{i},\sigma^{i})_{i<2}$. ∎

###  4.4 Cross-constraint cone avoidance basis theorem

We now prove our first cross-constraint basis theorem which requires some sort
of first-jump control, using the combinatorics developed in Section 4.3. This
basis theorem was first proven by Liu [22, Lemma 4.5] using a different
argument. Our new proof follows more closely the standard proof of the cone
avoidance basis theorem for $\Pi^{0}_{1}$ classes.

######  Theorem 4.15 (Cross-constraint cone avoidance, Liu [22, Lemma 4.5]).

Let $C$ be a non-computable set. Any left-full computable instance $T$ of
$\mathsf{CC}$ has a solution $(X^{i},Y^{i})_{i<2}$ such that
$(X^{0},Y^{0})\oplus(X^{1},Y^{1})\not\geqslant_{T}C$.

###### Proof.

To prove the theorem, we use forcing with conditions of the form
$\left((\rho^{i},\sigma^{i})_{i<2},U,B\right)$, where

  * •

$U$ is a $B$-computable cross-subtree of $T$

  * •

$(\rho^{i},\sigma^{i})_{i<2}$ is a condition-tuple for $[U]$

  * •

$B\subseteq\mathbb{N}$ and $B\not\geqslant_{T}C$

We will satisfy the following requirements for each $e\in\mathbb{N}$:

$\mathcal{R}_{e}:\Phi_{e}^{(X^{0},Y^{0})\oplus(X^{1},Y^{1})}\neq C$

A condition $\left((\rho^{i},\sigma^{i})_{i<2},U,B\right)$ _forces_
$\mathcal{R}_{\Psi}$, if $\mathcal{R}_{\Psi}$ holds for all
$(X^{i},Y^{i})\in[U]$ extending $(\rho^{i},\sigma^{i})$ for each $i<2$.

######  Lemma 4.16.

For every condition $c\coloneqq\left((\rho^{i},\sigma^{i})_{i<2},U,B\right)$
and every $e\in\mathbb{N}$, there is an extension of $c$ that forces
$\mathcal{R}_{e}$.

###### Proof.

For all $x\in\mathbb{N},v<2$, define

$A_{x,v}\coloneqq\\{(\widehat{\rho}^{i},\widehat{\sigma}^{i})_{i<2}\in\mathcal{X}_{<\mathbb{N}}^{2}:\Phi_{e}^{(\widehat{\rho}^{0},\widehat{\sigma}^{0})\oplus(\widehat{\rho}^{1},\widehat{\sigma}^{1})}(x)\downarrow=v\\}$

The set $A_{x,v}$ is upward-closed, and $\Sigma^{0}_{1}$ uniformly in $x,v$.
Consider the following $\Sigma^{0}_{1}(B)$ set:

$Q=\\{(x,v):A_{x,v}\mbox{ is }U\mbox{-sufficient over
}(\widehat{\rho}^{i},\widehat{\sigma}^{i})_{i<2}\\}$

_Case 1._ $(x,C(x))\not\in Q$ for some $x\in\mathbb{N}$. Let $\mathscr{L}$ be
the $\Pi^{0}_{1}(B)$ class of cross-trees $S$ witnessing that $A_{x,C(x)}$ is
not $U$-sufficient over $(\rho^{i},\sigma^{i})_{i<2}$. By the cone avoidance
basis theorem, there is some cross-tree $S$ such that $S\oplus
B\not\geqslant_{T}C$. The condition
$d\coloneqq\big{(}(\rho^{i},\sigma^{i})_{i<2},S,S\oplus B\big{)}$ is the
extension we are looking for. Indeed, it forces $\mathcal{R}_{e}$, because for
$(X^{i},Y^{i})_{i<2}\in[d]$, if $\Psi^{(X^{0},Y^{0})\oplus(X^{1},Y^{1})}$ is
total, then it is different from $C$ on input $x$.

_Case 2._ $(x,1-C(x))\in Q$ for some $x\in\mathbb{N}$. Unfolding the
definition, $A_{x,1-C(x)}$ is $U$-sufficient $(\rho^{i},\sigma^{i})_{i<2}$, so
by Lemma 4.14, there is a condition-tuple
$(\widehat{\rho}^{i},\widehat{\sigma}^{i})_{i<2}\in A_{x,1-C(x)}$ extending
$(\rho^{i},\sigma^{i})_{i<2}$. Thus the condition
$\big{(}(\widehat{\rho}^{i},\widehat{\sigma}^{i})_{i<2},U,B\big{)}$ is the
desired extension, as it forces $\mathcal{R}_{e}$.

_Case 3._ Neither Case 1 nor Case 2 holds. Then $Q$ is the $\Sigma^{0}_{1}(B)$
graph of the characteristic function of $C$, so $C\leq_{T}B$. Contradiction.

∎

We are now ready to prove Theorem 4.15. Let
$c_{0}=\left((\rho^{i},\sigma^{i})_{i<2},U,B\right)$ be a condition that
excludes a maximal number of components and let $\mathcal{F}$ be a
sufficiently generic filter for this notion of forcing, containing $c_{0}$.
For $i<2$, let
$X^{i}=\bigcup\\{\rho^{i}:\left((\rho^{i},\sigma^{i})_{i<2},U,B\right)\in\mathcal{F}\\}$
and
$Y^{i}=\bigcup\\{\sigma^{i}:\left((\rho^{i},\sigma^{i})_{i<2},U,B\right)\in\mathcal{F}\\}$.
By Lemma 3.8, $X^{i}$ and $Y^{i}$ are both infinite sequences. By Lemma 4.5,
for every $s<r$, $Y^{0}_{s}\cap Y^{1}_{s}$ is infinite. By Lemma 4.16,
$(X^{0},Y^{0})\oplus(X^{1},Y^{1})\not\geqslant_{T}C$. This completes the proof
of Theorem 4.15. ∎

######  Corollary 4.17.

For any non-computable set $C\subseteq\mathbb{N}$, there is a cross-constraint
ideal that does not contain $C$.

###### Proof.

We construct a sequence of sets $Z_{0}\leqslant_{T}Z_{1}\leqslant_{T}\ldots$
such that for any integer $n=\langle k,e\rangle$, $Z_{n}\not\geq_{T}C$, and if
$\Phi_{e}^{Z_{k}}$ is an instance of $\mathsf{CC}$, then $Z_{n+1}$ computes a
solution.

Define $Z_{0}\coloneqq\emptyset$. Suppose $Z_{n}$ has been defined and let
$n=\langle k,e\rangle$. If $\Phi_{e}^{Z_{k}}$ is not a left-full cross-tree,
then $Z_{n+1}\coloneqq Z_{n}$. Otherwise, by Theorem 4.15 relativized to
$Z_{n}$, there is a pair of paths $P_{0}$ and $P_{1}$, such that $P_{0}\oplus
P_{1}\oplus Z_{n}\not\geqslant_{T}C$. In which case $Z_{n+1}\coloneqq
P_{0}\oplus P_{1}\oplus Z_{n}$.

By construction, the class $\mathcal{M}\coloneqq\\{X\in 2^{\mathbb{N}}:\exists
n,X\leqslant_{T}Z_{n}\\}$ is a cross-constraint ideal containing only sets
avoiding the cone above $C$, in particular $C$ is not in the ideal. ∎

###  4.5 Cross-constraint preservation of non-$\Sigma^{0}_{1}$ definitions

We now prove a second cross-constraint basis theorem, about preservation of
non-$\Sigma^{0}_{1}$ definitions. This basis theorem for $\Pi^{0}_{1}$ classes
was first proven by Wang [31], and implies the cone avoidance basis theorem in
a straightforward way. Later, Downey et al. [9] actually proved that the two
basis theorems are equivalent, as any problem satisfying any of them,
satisfies both. Thus, the following theorem is a (non-trivial) consequence of
Theorem 4.15. However, we give a direct proof of it, to get familiar with the
combinatorics of the cross-constraint problem.

######  Theorem 4.18 (Cross-constraint preservation of non-$\Sigma^{0}_{1}$
definitions).

Let $C$ be a non-$\Sigma^{0}_{1}$ set. Any computable instance $T$ of
$\mathsf{CC}$, has a solution $(X^{i},Y^{i})_{i<2}$ such that $C$ is not
$\Sigma^{0}_{1}$ relative to $(X^{0},Y^{0})\oplus(X^{1},Y^{1})$.

###### Proof.

To prove the theorem, we use forcing with conditions of the form
$((\rho^{i},\sigma^{i})_{i<2},U,B)$ where

  * •

$U$ is a $B$-computable cross-subtree of $T$

  * •

$(\rho^{i},\sigma^{i})_{i<2}$ is a condition-tuple for $[U]$

  * •

$B\subseteq\mathbb{N}$ is such that $C$ is not $\Sigma^{0}_{1}(B)$

We want to satisfy the following requirements for every Turing index $e$:

$\mathcal{R}_{e}:W_{e}^{(X^{0},Y^{0})\oplus(X^{1},Y^{1})}\neq C$

######  Lemma 4.19.

For every condition $c\coloneqq\left((\rho^{i},\sigma^{i})_{i<2},U,B\right)$
and every $e\in\mathbb{N}$, there is an extension of $c$ forcing
$\mathcal{R}_{e}$.

###### Proof.

Given some $x\in\mathbb{N}$, consider the set

$A_{x}\coloneqq\\{(\widehat{\rho}^{i},\widehat{\sigma}^{i})_{i<2}\in\mathcal{X}_{<\mathbb{N}}^{2}:x\in
W^{(\widehat{\rho}^{0},\widehat{\sigma}^{0})\oplus(\widehat{\rho}^{1},\widehat{\sigma}^{1})}_{e}\\}$

Here again, the set $A_{x}$ is upward-closed and $\Sigma^{0}_{1}$ uniformly in
$x$. Let

$Q\coloneqq\\{x:A_{e,x}\text{ is }U\text{-sufficient over
}(\rho^{i},\sigma^{i})_{i<2}\\}$

The set $Q$ is $\Sigma^{0}_{1}(B)$, thus $Q\neq C$. This leads to two cases.

_Case 1._ There is $x\in C\smallsetminus Q$. Let $\mathscr{L}$ be the class of
all cross-trees $S\subseteq U$ which witness that $A_{x}$ is not
$U$-sufficient over $(\rho^{i},\sigma^{i})_{i<2}$. It is non-empty by
hypothesis, and since $A_{x}$ is $\Sigma^{0}_{1}$, then $\mathscr{L}$ is
$\Pi^{0}_{1}(B)$. Now since $\mathsf{WKL}$ admits preservation of
non-$\Sigma^{0}_{1}$ definitions (see [31, Theorem 3.6]), there is a cross-
tree $S\in\mathscr{L}$ such that $C$ is not $\Sigma^{0}_{1}(S\oplus B)$. The
condition $d\coloneqq\big{(}(\rho^{i},\sigma^{i})_{i<2},S,S\oplus B\big{)}$ is
the extension we are looking for, since $x\in C$ but $d$ forces that $x\notin
W^{(X^{0},Y^{0})\oplus(X^{1},Y^{1})}_{e}$.

_Case 2._ There is $x\in Q\smallsetminus C$. Unfolding the definition, $A_{x}$
is $U$-sufficient over $(\rho^{i},\sigma^{i})_{i<2}$, so by Lemma 4.14, there
is a condition-tuple $(\widehat{\rho}^{i},\widehat{\sigma}^{i})_{i<2}\in
A_{x}$ extending $(\rho^{i},\sigma^{i})_{i<2}$. The condition
$\big{(}(\widehat{\rho}^{i},\widehat{\sigma}^{i})_{i<2},U,B\big{)}$ is the
desired extension, as it forces $x\in
W^{(X^{0},Y^{0})\oplus(X^{1},Y^{1})}_{e}$ for some $x\not\in C$. ∎

We are now ready to prove Theorem 4.18. Let
$c_{0}=\left((\rho^{i},\sigma^{i})_{i<2},U,B\right)$ be a condition that
excludes a maximal number of components and let $\mathcal{F}$ be a
sufficiently generic filter for this notion of forcing, containing $c_{0}$.
For $i<2$, let
$X^{i}=\bigcup\\{\rho^{i}:\left((\rho^{i},\sigma^{i})_{i<2},U,B\right)\in\mathcal{F}\\}$
and
$Y^{i}=\bigcup\\{\sigma^{i}:\left((\rho^{i},\sigma^{i})_{i<2},U,B\right)\in\mathcal{F}\\}$.
By Lemma 3.8, $X^{i}$ and $Y^{i}$ are both infinite sequences. By Lemma 4.5,
for every $s<r$, $Y^{0}_{s}\cap Y^{1}_{s}$ is infinite. By Lemma 4.19, $C$ is
not $\Sigma^{0}_{1}((X^{0},Y^{0})\oplus(X^{1},Y^{1}))$. This completes the
proof of Theorem 4.18. ∎

######  Corollary 4.20.

For any non-$\Sigma^{0}_{1}$ set $C\subseteq\mathbb{N}$. There is a cross-
constraint ideal such that $C$ is not $\Sigma^{0}_{1}$ relative to any element
of the ideal.

###### Proof.

We construct a sequence of sets $Z_{0}\leqslant_{T}Z_{1}\leqslant_{T}\ldots$
such that for any integer $n=\langle k,e\rangle$, $C$ is not
$\Sigma^{0}_{1}(Z_{n})$, and if $\Phi_{e}^{Z_{k}}$ is an instance of
$\mathsf{CC}$, then $Z_{n+1}$ computes a solution.

Define $Z_{0}\coloneqq\emptyset$. Suppose $Z_{n}$ has been defined, and let
$n=\langle k,e\rangle$. If $\Phi_{e}^{Z_{k}}$ is not a left-full cross-tree,
then $Z_{n+1}\coloneqq Z_{n}$. Otherwise, by Theorem 4.18 relativized to
$Z_{n}$, there is a pair of paths $P_{0}$ and $P_{1}$, such that $C$ is not
$\Sigma^{0}_{1}$ relative to $P_{0}\oplus P_{1}\oplus Z_{n}$. In which case
$Z_{n+1}\coloneqq P_{0}\oplus P_{1}\oplus Z_{n}$.

By construction, the class $\mathcal{M}\coloneqq\\{X\in 2^{\mathbb{N}}:\exists
n,X\leqslant_{T}Z_{n}\\}$ is a cross-constraint ideal such that $C$ is not
$\Sigma^{0}_{1}$ relative to any element in it. ∎

######  Corollary 4.21 (Cross-constraint cone avoidance).

Let $C$ be a non-computable set. Any left-full computable instance $T$ of
$\mathsf{CC}$, has a solution $(X^{i},Y^{i})_{i<2}$ such that
$(X^{0},Y^{0})\oplus(X^{1},Y^{1})\not\geqslant_{T}C$.

###### Proof.

Suppose $C$ is non-computable. Then either $C$ or $\overline{C}$ is not
$\Sigma^{0}_{1}$. By Theorem 4.18, there is a solution
$(X^{i},Y^{i})_{i<2}\in[T]^{2}$ such that either $C$ or $\overline{C}$ is not
$\Sigma^{0}_{1}$ relative to $(X^{0},Y^{0})\oplus(X^{1},Y^{1}))$. In
particular, $(X^{0},Y^{0})\oplus(X^{1},Y^{1})\not\geqslant_{T}C$. ∎

###  4.6 Cross-constraint low basis theorem

The low basis theorem for $\Pi^{0}_{1}$ classes is one of the most famous
theorems in computability theory. We prove its counterpart for the cross-
constraint problem. However, contrary to the case of $\Pi^{0}_{1}$ classes,
where the theorem can be strengthened to obtain superlow sets, it does not
seem to be the case for cross-constraint problems.

######  Theorem 4.22 (Cross-constraint low basis).

Any left-full computable instance $T$ of $\mathsf{CC}$, has a solution
$(X^{i},Y^{i})_{i<2}$ such that $(X^{0},Y^{0})\oplus(X^{1},Y^{1})$ is low.

###### Proof.

To prove the theorem, we use forcing with conditions of the form

$\left((\rho^{i},\sigma^{i})_{i<2},U,B\right)$

where

  * •

$U$ is a $B$-computable cross-subtree of $T$

  * •

$(\rho^{i},\sigma^{i})_{i<2}$ is a condition-tuple for $[U]$

  * •

$B$ is a set of low degree

An _index_ for a condition $\left((\rho^{i},\sigma^{i})_{i<2},U,B\right)$ is a
tuple $\left((\rho^{i},\sigma^{i})_{i<2},a,b\right)$ such that
$\Phi^{B}_{a}=U$ and $\Phi^{\emptyset^{\prime}}_{b}=B^{\prime}$. An index is
therefore a finite representation of a condition. We say that a condition
$c\coloneqq\left((\rho^{i},\sigma^{i})_{i<2},U,B\right)$ _decides the jump on
$e$_ if either
$\Phi^{(\rho^{0},\sigma^{0})\oplus(\rho^{1},\sigma^{1})}_{e}(e)\downarrow$
holds or $c$ forces $\Phi^{(X^{0},Y^{0})\oplus(X^{1},Y^{1})}_{e}(e)\uparrow$.

######  Lemma 4.23.

For every condition $c\coloneqq\left((\rho^{i},\sigma^{i})_{i<2},U,B\right)$
and every $e\in\mathbb{N}$, there is an extension $d$ of $c$ deciding the jump
on $e$. Moreover, an index for $d$ can be found $\emptyset^{\prime}$-uniformly
in $e$ and an index for $c$.

###### Proof.

Consider the following $\Sigma^{0}_{1}$ set

$A_{e}\coloneqq\\{(\widehat{\rho}^{i},\widehat{\sigma}^{i})_{i<2}\in\mathcal{X}_{<\mathbb{N}}^{2}:\Phi^{(\widehat{\rho}^{0},\widehat{\sigma}^{0})\oplus(\widehat{\rho}^{1},\widehat{\sigma}^{1})}_{e}(e)\downarrow\\}$

_Case 1. $A_{e}$ is not $U$-sufficient over $(\rho^{i},\sigma^{i})_{i<2}$._
Let $\mathscr{L}$ be the class of all cross-trees $S\subseteq T$ which witness
that $A_{e}$ is not $U$-sufficient over $(\rho^{i},\sigma^{i})_{i<2}$. Since
$A_{e}$ is $\Sigma^{0}_{1}$, then $\mathscr{L}$ is $\Pi^{0}_{1}(B)$. By the
uniform low basis theorem relative to $B$ (see [16, Theorem 4.1]), there is
some $S\in\mathscr{L}$ such that $(S\oplus
B)^{\prime}\leqslant_{T}\emptyset^{\prime}$. Moreover, a lowness index of
$S\oplus B$ (an integer $a$ such that $\Phi^{\emptyset^{\prime}}_{a}=(S\oplus
B)^{\prime}$) can be $\emptyset^{\prime}$-computed from an index of
$\mathscr{L}$. The condition $d\coloneqq((\rho^{i},\sigma^{i})_{i<2},S,S\oplus
B)$ is the extension we are looking for. Indeed,
$\Phi^{(X^{0},Y^{0})\oplus(X^{1},Y^{1})}_{e}(e)\uparrow$ holds for any
$(X^{i},Y^{i})_{i<2}\in[d]$.

_Case 2. $A_{e}$ is $U$-sufficient over $(\rho^{i},\sigma^{i})_{i<2}$._ By
Lemma 4.14, there is a condition-tuple
$(\widehat{\rho}^{i},\widehat{\sigma}^{i})_{i<2}\in A_{e}$ for $[U]$ which
extends $(\rho^{i},\sigma^{i})_{i<2}$. Thus, the condition
$\big{(}(\widehat{\rho}^{i},\widehat{\sigma}^{i})_{i<2},T,B\big{)}$ is the
desired extension, since
$\Phi_{e}^{(\widehat{\rho}^{0},\widehat{\sigma}^{0})\oplus(\widehat{\rho}^{1},\widehat{\sigma}^{1})}(e)\downarrow$.

Finally, note that $\emptyset^{\prime}$ can decide whether or not it is in the
first or second case, since $A_{e}$ is $\Sigma^{0}_{1}$, and so “$A_{e}$ is
$T$-sufficient over $(\rho^{i},\sigma^{i})_{i<2}$” also is. Hence, each
extension can be uniformly computed from $\emptyset^{\prime}$. ∎

We are now ready to prove Theorem 4.22. We build a uniformly
$\emptyset^{\prime}$-computable descending sequence of conditions $c_{0}\geq
c_{1}\geq\dots$ such that for every $n$, letting
$c_{n}=\left((\rho^{i}_{n},\sigma^{i}_{n})_{i<2},U_{n},B_{n}\right)$

  * •

$c_{n+1}$ decides the jump on $n$ ;

  * •

$|\rho^{i}_{n}|\geq n$ ; $|\sigma^{i}_{n,s}|\geq n$ for every $s<r$;

  * •

$(\sigma^{0}_{n+1,s},\sigma^{1}_{n+1,s})$ is not completely incompatible over
$(\sigma^{0}_{n,s},\sigma^{1}_{n,s})$.

Let $c_{0}=\left((\rho^{i},\sigma^{i})_{i<2},U,B\right)$ be a condition which
excludes a maximal number of components. Note that $c_{0}$ does not need to be
found in $\emptyset^{\prime}$, since it is a one-time guess. Assuming $c_{n}$
has been defined, by Lemma 4.23, there is an extension $c^{1}_{n}\leq c_{n}$
deciding the jump on $n$. By Lemma 3.8, there is an extension $c^{2}_{n}\leq
c^{1}_{n}$ satisfying the second item, and by Lemma 4.5, there is an extension
$c_{n+1}\leq c^{2}_{n}$ satisfying the third item. Moreover, indices for each
of these extensions can be found $\emptyset^{\prime}$-computably uniformly in
$n$. This completes the proof of Theorem 4.22. ∎

######  Corollary 4.24.

There is a cross-constraint ideal that contains only low sets.

###### Proof.

We construct a sequence of sets $Z_{0}\leqslant_{T}Z_{1}\leqslant_{T}\ldots$
such that for any integer $n=\langle k,e\rangle$, $Z_{n}$ is low, and if
$\Phi_{e}^{Z_{k}}$ is an instance of $\mathsf{CC}$, then $Z_{n+1}$ computes a
solution.

Define $Z_{0}\coloneqq\emptyset$. Suppose $Z_{n}$ has been defined, and let
$n=\langle k,e\rangle$. If $\Phi_{e}^{Z_{k}}$ is not a left-full cross-tree,
then $Z_{n+1}\coloneqq Z_{n}$. Otherwise, by Theorem 4.22 relativized to
$Z_{n}$, there is a pair of paths $P_{0}$ and $P_{1}$, such that $(P_{0}\oplus
P_{1}\oplus Z_{n})^{\prime}\leqslant_{T}Z_{n}^{\prime}$. In which case
$Z_{n+1}\coloneqq P_{0}\oplus P_{1}\oplus Z_{n}$.

By construction, the class $\mathcal{M}\coloneqq\\{X\in 2^{\mathbb{N}}:\exists
n,X\leqslant_{T}Z_{n}\\}$ is a cross-constraint ideal containing only low
sets. ∎

###  4.7 Yet some other antibasis theorem

As noted by Liu [22, section 4.6], if two 2-colorings are completely
incompatible over a pair, then they are Turing equivalent. Then, instead of
requiring that two 2-colorings are infinitely compatible, one could strengthen
the requirement and ask them not to be Turing equivalent. He therefore asked
the following question.

######  Question 4.25 (Liu [22, Question 4.25]).

Given two incomputable oracles $D_{0}\not\geq_{T}D_{1}$, a non-empty
$\Pi^{0}_{1}$ class $\mathcal{P}\subseteq 2^{\mathbb{N}}$, does there exist an
$X\in\mathcal{P}$ such that $X\not\geq_{T}D_{0}$ and $D_{0}\oplus
X\not\geq_{T}D_{1}$?

There is a negative answer thanks to a theorem of Day and Reimann [7]:

######  Theorem 4.26 (Day and Reimann [7, Corollary 2.1]).

Suppose that $X$ has PA degree and $C$ is a c.e. set. Then either $C\oplus
X\geq_{T}\emptyset^{\prime}$, or $X\geq_{T}C$.

Thus, letting $D_{0}$ be a incomplete non-computable c.e. set,
$D_{1}=\emptyset^{\prime}$ and $\mathcal{P}$ be a non-empty $\Pi^{0}_{1}$
class of only PA degrees, there is no $X\in\mathcal{P}$ satisfying
simultaneously $X\not\geq_{T}D_{0}$ and $D_{0}\oplus X\not\geq_{T}D_{1}$.

##  5 $\Gamma$-hyperimmunity

Theorem 3.13 can be instantiated by considering the cross-constraint ideal of
all arithmetic sets and letting $f$ be a Cohen arithmetically-generic
3-coloring of the integers. However, to obtain a separation of
$\mathsf{D}^{2}_{3}$ from $(\mathsf{D}^{2}_{2})^{*}$ over computable
reduction, one needs to build a $\Delta^{0}_{2}$ such coloring $f$. Liu [22]
designed a new invariance property called preservation of
$\Gamma$-hyperimmunity, which is satisfied by weak König’s lemma and the
cross-constraint problem, but not by $\mathsf{D}^{2}_{2}$. We re-define this
notion and prove that it is preserved by $\mathsf{COH}$, which is a new
result, enabling to separate $\mathsf{D}^{2}_{3}$ from
$(\mathsf{RT}^{2}_{2})^{*}$ over computable reduction.

The notion of $\Gamma$-hyperimmunity might seem ad-hoc at first sight, but
becomes clearer when looking at the proof of preservation of
$\Gamma$-hyperimmunity of the cross-constraint problem (Liu [22, Lemma 4.2])
for which it was specifically designed.

Recall that an instance $f$ of $\mathsf{RT}^{1}_{k}$ is _hyperimmune_ relative
to $D\subseteq\mathbb{N}$ if for every $D$-computable sequence
$g_{0},g_{1},\dots$ of partial functions from $\mathbb{N}$ to $k$ with finite
support, such that $\min\operatorname{dom}g_{n}>n$, there is some
$N\in\mathbb{N}$ such that $g_{n}$ is compatible with $f$.
$\Gamma$-hyperimmunity is a strengthening of this notion of hyperimmunity,
between $\emptyset$-hyperimmunity and $\emptyset^{\prime}$-hyperimmunity, by
considering computable approximations of sequences of partial functions with
finite mind changes, for a very specific family of approximations. They seem
to be closely related to the Ershov hierarchy [14].

The following series of definitions (Definitions 5.1, 5.2, 5.3, 5.5, 5.6 and
5.7 yield the notion of $\Gamma$-approximation, from which
$\Gamma$-hyperimmunity is derived.

######  Definition 5.1.

A tree $T_{1}\subseteq\mathbb{N}^{<\mathbb{N}}$ is a _one-step variation_ of
$T_{0}\subseteq\mathbb{N}^{<\mathbb{N}}$ if there is a node $\xi\in T_{0}$ and
a non-empty finite set $F\subseteq\mathbb{N}$ such that

  * •

either $\xi\in\ell(T_{0})$ and $T_{1}=T_{0}\cup\xi\cdot F$

  * •

or $\xi\in T_{0}-\ell(T_{0})$, $T_{1}=(T_{0}-[\xi]^{\prec})\cup\xi\cdot F$ and
$F\subsetneq\\{n\in\mathbb{N}:\xi\cdot n\in T_{0}\\}$

In other words, a one-step variation of a tree consists of either extending a
leaf with finitely many immediate children, or backtracking by removing a
node, and making all its siblings leaves again. This is a non-reflexive
relation. The notion of one-step variation can be reminiscent of the Hydra
game [19].

######  Definition 5.2.

Fix a partial order $(W,\preccurlyeq)$ which is a tree of root $\zeta$. A
_computation path_ on $(W,\preccurlyeq)$ is a finite sequence
$(T_{0},\varphi_{0}),(T_{1},\varphi_{1}),\ldots,(T_{u-1},\varphi_{u-1})$
where, for all $j<u$, $T_{j}\subseteq\mathbb{N}^{<\mathbb{N}}$ is a finite
tree such that

  * •

$T_{0}=\\{\varepsilon\\}$

  * •

$j\in\mathbb{N}$, $T_{j+1}$ is a one-step variation of $T_{j}$

And, for all $j<u$, $\varphi_{j}:T_{j}\to W$ is a function such that

  * •

$\varphi_{j}(\varepsilon)=\zeta$

  * •

$\varphi_{j}$ is non-decreasing

  * •

$\varphi_{j+1}$ and $\varphi_{j}$ are compatible, i.e.
$\varphi_{j+1}=\varphi_{j}$ on the domain $T_{j+1}\cap T_{j}$

We shall consider exclusively well-founded trees $(W,\preccurlyeq)$, in which
case any computation path is of finite length. The notion of computation path
can be used as an operator to define an infinite hierarchy of well-founded
trees.

######  Definition 5.3 (Gamma spaces).

By induction, we define the partial orders $(\Gamma_{m},\preccurlyeq_{m})$
that are trees of root $\zeta_{m}$

  * •

$\Gamma_{0}\coloneqq\\{f:\mathbb{N}\to 3:\operatorname{dom}f\text{ is
finite}\\}$, forming a tree of depth 1, with the empty map $\zeta_{0}$ as its
root, and every other element as an immediate child of the root.

  * •

$\Gamma_{m+1}$ is the set of computation paths on
$(\Gamma_{m},\preccurlyeq_{m})$, its root $\zeta_{m+1}$ is the computation
path $(\\{\varepsilon\\},\varepsilon\mapsto\zeta_{m})$, and
$\preccurlyeq_{m+1}$ is the prefix relation on sequences.

Intuitively, the root of $\Gamma_{1}$ is the nowhere-defined function, the
immediate children are finite sets of functions with finite support, and the
sub-branches consist of removing elements from this finite set.

######  Lemma 5.4 (Liu [22, Lemma 4.12]).

For all $m\in\mathbb{N}$, the tree $\Gamma_{m}$ is well-founded.

###### Proof.

By induction on $m$, we show that the structure of $\Gamma_{m}$ is the
following: there are infinitely many nodes of height 1, and for each node of
height 1, the subtree above it is finite. In particular, it is a well-founded
tree.

The tree $\Gamma_{0}$ satisfies the statement, by construction. Now suppose
$\Gamma_{m}$ has the above structure for some $m\in\mathbb{N}$. A computation
path on $\Gamma_{m}$ will first select finitely many nodes, say
$\xi_{0},\ldots,\xi_{n-1}$, of height 1.

Since the function in a computation path is an embedding into $\Gamma_{m}$, it
means that the subtree above $\xi_{i}$ (for any $i<n$) is finite. Furthermore,
the “either” case can only be applied finitely many times to a node. Indeed,
the “or” case can turn an inner node back into a leaf, but it can only do so
finitely many times, because it strictly decreases the cardinal of the set of
direct successors of the node it is applied to. Hence, there can only be
finitely many computation paths. ∎

Due to the inductive nature of the definition of $\Gamma$-spaces, its elements
are relatively abstract. One must think of a computation path in
$\Gamma_{m}$-space as a finite set of partial functions from $\mathbb{N}$ to
$k$ with finite support.

######  Definition 5.5.

The _interpretation_ $\llbracket\gamma\rrbracket$ of a computation path
$\gamma\in\Gamma_{m}$ is a finite non-empty subset of $\Gamma_{0}$ defined
inductively as follows:

  * •

if $m=0$, $\llbracket\gamma\rrbracket=\\{\gamma\\}$

  * •

if $m>0$ and
$\gamma\coloneqq((T_{0},\varphi_{0}),\ldots,(T_{u-1},\varphi_{u-1}))$, then
$\llbracket\gamma\rrbracket=\bigcup_{\zeta\in\ell(T_{u-1})}\llbracket\zeta\rrbracket$

######  Definition 5.6.

For $n\in\mathbb{N}$, a set $F\subseteq\Gamma_{0}$ is _over_ $n$ if for every
$g\in F$, $\operatorname{dom}g\subseteq]n,\infty[$. By extension, for
$m,n\in\mathbb{N}$, we say $\gamma\in\Gamma_{m}$ is _over $n$_ if
$\llbracket\gamma\rrbracket$ is over $n$.

Based on the interpretation of a computation path $\gamma\in\Gamma_{m}$ as a
subset of $\Gamma_{0}$, a $\Gamma_{m}$-approximation is a
$\Delta^{0}_{2}$-approximation of a list of finite subsets of $\Gamma_{0}$,
for which the finite mind changes is ensured by an increasing sequence in a
well-founded tree, or equivalently as a decreasing sequence of ordinals.

######  Definition 5.7.

For $m\in\mathbb{N}$, a _$\Gamma_{m}$ -approximation_ is a function
$f:\mathbb{N}\times\mathbb{N}\to\Gamma_{m}$ (for some $m$) if for all
$n\in\mathbb{N}$

  * •

$f(n,0)=\zeta_{m}$

  * •

$f(n,-)$ is non-decreasing

  * •

$\forall s\in\mathbb{N},f(n,s)\text{ is over }n$

We also define its interpretation as

$\displaystyle\llbracket f\rrbracket:\mathbb{N}\times\mathbb{N}$
$\displaystyle\to\mathfrak{P}_{\text{fin}}(\Gamma_{0})$ $\displaystyle n,s$
$\displaystyle\mapsto\llbracket f(n,s)\rrbracket$

It is often useful to consider enumerations of Turing functionals which
furthermore satisfy some decidable syntactic constraint. We shall see that one
can computably list all the Turing functionals behaving as
$\Gamma_{m}$-approximations.

######  Definition 5.8.

For any $m\in\mathbb{N}$, a Turing functional $\Psi$ is a _$\Gamma_{m}$
-functional_ if and only if it is total and $\Psi^{X}$ is a
$\Gamma_{m}$-approximation for every oracle $X$.

######  Lemma 5.9.

For every $m\in\mathbb{N}$ and every Turing functional $\Xi$, there is a
$\Gamma_{m}$-functional $\Psi$ such that, for any oracle $X$, if $\Xi^{X}$ is
a $\Gamma_{m}$-approximation, then $\Psi^{X}$ has the same limit function.

###### Proof.

The functional $\Psi$ proceeds as follows. Fix an oracle $X$ and some
$n\in\mathbb{N}$. Define $\Psi^{X}(n,0)\coloneqq\zeta_{m}$. Now to define
$\Psi^{X}(n,t)$ for $t>0$, consider $s<t$ the biggest integer (if it exists)
such that $\Xi^{X}(n,s)[t]\downarrow$ and such that
$\Xi^{X}(n,s)[t]\succ\Psi^{X}(n,t-1)$. If $s$ exists then
$\Psi^{X}(n,t)\coloneqq\Xi^{X}(n,s)[t]$. Otherwise,
$\Psi^{X}(n,t)\coloneqq\Psi^{X}(n,t-1)$. ∎

As mentioned, a $\Gamma$-approximation should be thought of as a
$\Delta^{0}_{2}$-approximation of sequences of finite subsets of $\Gamma_{0}$
of a special shape, and such that the minimum of the support of its elements
is unbounded. We are now ready to define the notion of $\Gamma$-hyperimmunity.
Given a $\Gamma$-approximation, it is sufficient to be compatible with any
partial function of the limit to satisfy it.

######  Definition 5.10.

A function $f:\mathbb{N}\to 3$ (potentially partial) is _compatible with_ a
set $F\subseteq\Gamma_{0}$ if $f$ extends some element in $F$, i.e. $\exists
g\in F,\operatorname{dom}f\supseteq\operatorname{dom}g\text{ and
}f\\!{\upharpoonright}_{\operatorname{dom}g}=g$. By extension, for
$m\in\mathbb{N}$, a partial 3-coloring $f$ is _compatible with_
$\gamma\in\Gamma_{m}$, if it is compatible with $\llbracket\gamma\rrbracket$.

######  Definition 5.11.

A 3-coloring $f$ is _$\Gamma$ -hyperimmune_ relative to $D\subseteq\mathbb{N}$
if, for every $m\in\mathbb{N}$ and for every $D$-computable
$\Gamma_{m}$-approximation $g$, there is an $n\in\mathbb{N}$ such that $f$ is
compatible with $\lim_{s}g(n,s)$.

The following lemma shows that $\Gamma$-hyperimmunity is a stronger notion
than hyperimmunity. It simply comes from the fact that a computable list of
elements of $\Gamma_{0}$ with unbounded minimum support is a particular case
of $\Gamma_{0}$-approximation.

######  Lemma 5.12.

If a 3-coloring $f$ is $\Gamma$-hyperimmune relative to
$D\subseteq\mathbb{N}$, then it is also hyperimmune relative to $D$.

###### Proof.

Let $(F_{n,0},F_{n,1},F_{n,2})_{n\in\mathbb{N}}$ be a $D$-computable sequence
of mutually disjoint finite sets $(F_{n,0},F_{n,1},F_{n,2})_{n\in\mathbb{N}}$
such that $\min\bigcup_{j<3}F_{n,j}>n$.

For any $n\in\mathbb{N}$, consider we define a 3-coloring with finite support

$\gamma_{n}:x\mapsto\begin{dcases}j&\text{if }x\in F_{n,j}\\\
\uparrow&\text{otherwise}\end{dcases}$

It is well defined since the finite sets $F_{n,j}$ are mutually disjoint. And
consider the function

$\displaystyle g:\ $ $\displaystyle\mathbb{N}^{2}\to\Gamma_{0}$ $\displaystyle
n,s\mapsto\begin{dcases}\emptyset&\text{if }s=0\\\
\gamma_{n}&\text{otherwise}\end{dcases}$

It is a $D$-computable $\Gamma_{0}$-approximation, thus by
$\Gamma$-hyperimmunity of $f$ there is $N\in\mathbb{N}$ such that $f$ is
compatible with $\lim_{s}g(N,s)$, i.e. $f$ extends $\gamma_{N}$, i.e. $\forall
j<3,F_{N,j}\subseteq f^{-1}(j)$. ∎

Liu [22] proved the following lemma, which we reprove with more details.

######  Proposition 5.13 (Liu [22, Lemma 4.17]).

There is a $\Delta^{0}_{2}$ coloring which is $\Gamma$-hyperimmune.

###### Proof.

First, it is possible to computably list all computable
$\Gamma_{m}$-approximations, where $m$ is any integer. Indeed, given a
computable partial order $(W,\preccurlyeq)$, the set of its computation paths
is uniformly computable. This is because they are finite sequences composed of
finite trees, so all the constraints listed in the definition can be computed.
From there, the set of $\Gamma_{m}$-spaces is uniformly computable in $m$.
Hence, we fix an enumeration $(\Phi_{e,m})_{e\in\mathbb{N}}$ of all the
computable $\Gamma_{m}$-approximations, for any $m$.

We wish to construct $f:\mathbb{N}\to 3$ such that, for any
$e,m\in\mathbb{N}$, the following requirement is satisfied.

$\mathcal{R}_{e,m}\coloneqq f\text{ is compatible with }\Phi_{e,m}$

Suppose we have so far constructed $\rho\in 3^{<\mathbb{N}}$, we now consider
the $\Gamma_{m}$-approximation $\Phi_{e,m}$, and we are going to use
$\emptyset^{\prime}$ to find an integer $s$ such that $\Phi_{e,m}(|\rho|,s)$
is the limit value for $\Phi_{e,m}(|\rho|,-)$. Then either
$\llbracket\Phi_{e,m}(|\rho|,s)\rrbracket=\emptyset$, in which case
$\mathcal{R}_{e,m}$ is satisfied. Or
$\llbracket\Phi_{e,m}(|\rho|,s)\rrbracket\neq\emptyset$, in which case
$\mathcal{R}_{e,m}$ is satisfied for $\rho\cup\tau$ where
$\tau\in\Phi_{e,m}(|\rho|,s)$. Because, by definition of a
$\Gamma_{m}$-approximation, $\tau$ is over $|\rho|$, i.e.
$\min\operatorname{dom}\tau>|\rho|$

To find $s\in\mathbb{N}$, build a sequence of integers, starting with
$s_{0}\coloneqq 0$. If $s_{k}$ is the latest integer we have defined, then use
$\emptyset^{\prime}$ to know whether $\exists
y>s_{k},\Phi_{e,m}(|\rho|,y)\succ_{m}\Phi_{e,m}(|\rho|,s_{k})$. If the answer
is yes then $s_{k+1}$ is defined by such a witness, otherwise we stop defining
the sequence and $s\coloneqq s_{k}$.

The above procedure must end at some point, because
$\Phi_{e,m}(|\rho|,s_{0})\prec_{m}\Phi_{e,m}(|\rho|,s_{1})\prec_{m}\ldots$ is
a strictly increasing sequence in the space $\Gamma_{m}$, which is well-
founded (by Lemma 5.4). And so $\Phi_{e,m}(|\rho|,s)$ is the limit value we
were looking for, because the case that defines $s$ ensures that $\forall
y>s,\Phi_{e,m}(|\rho|,y)=\Phi_{e,m}(|\rho|,s)$. ∎

The following two theorems by Liu state that $\mathsf{WKL}$ and $\mathsf{CC}$
both admit preservation of $\Gamma$-hyperimmunity. Their proofs are quite
technical but essentially follow from the above combinatorics of the cross-
constraint problem. We therefore do not include them.

######  Theorem 5.14 (Liu [22, Lemma 4.18]).

Let $f:\mathbb{N}\to 3$ be $\Gamma$-hyperimmune. For every non-empty
$\Pi^{0}_{1}$ class $\mathcal{P}\subseteq 2^{\mathbb{N}}$, there is a member
$X\in\mathcal{P}$ such that $f$ is $\Gamma$-hyperimmune relative to $X$.

######  Theorem 5.15 (Liu [22, Lemma 4.2]).

Let $f:\mathbb{N}\to 3$ be $\Gamma$-hyperimmune. For every computable instance
of $\mathsf{CC}$, there is a solution $X$ such that $f$ is
$\Gamma$-hyperimmune relative to $X$.

###  5.1 Preservation of $\Gamma$-hyperimmunity for $\mathsf{COH}$

We now prove that $\mathsf{COH}$ admits preservation of
$\Gamma$-hyperimmunity, which is a new result, and yields in particular that
$\mathsf{D}^{2}_{3}$ is not computably reducible to
$(\mathsf{RT}^{2}_{2})^{*}$ (Theorem 5.21).

######  Theorem 5.16.

Let $g\in 3^{\mathbb{N}}$ be a $\Gamma$-hyperimmune function and
$R_{0},R_{1},\dots$ be a uniformly computable sequence of sets. Then there is
an $\vec{R}$-cohesive set $G$ such that $g$ is $\Gamma$-hyperimmune relative
to $G$.

###### Proof.

We proceed by forcing, using Mathias conditions $(F,X)$ such that $X$ is
computable.

For a $\Gamma_{m}$-functional $\Psi$, define the requirement
$\mathcal{R}_{\Psi,m}\coloneqq$ there is $n\in\mathbb{N}$ such that $g$ is
compatible with $\lim_{s}\Psi^{G}(n,s)$.

######  Lemma 5.17.

For each condition $(F,X)$, $m\in\mathbb{N}$, and $\Gamma_{m}$-functional
$\Psi$, there is an extension forcing $\mathcal{R}_{\Psi,m}$

###### Proof.

We define a computable $\Gamma_{m}$-approximation
$f:\mathbb{N}^{2}\to\Gamma_{m}$ as follows. First, for every $n$,
$f(n,0)\coloneqq\zeta_{m}$. Suppose that at step $s$, we have defined $f(n,s)$
for every $n$. Then for each $n$, if there is some $F^{\prime}\subseteq X$
with $\max F^{\prime}<s$ and some $t\leqslant s$ such that $\Psi^{F\cup
F^{\prime}}(n,t)\downarrow$ and $\Psi^{F\cup F^{\prime}}(n,t)\succ f(n,s)$,
then let $f(n,s+1)\coloneqq\Psi^{F\cup F^{\prime}}(n,t)$. Otherwise, let
$f(n,s+1)\coloneqq f(n,s)$. Then go to the next stage.

By construction, $f$ is a $\Gamma_{m}$-approximation. Since $g$ is
$\Gamma$-hyperimmune, there is $n\in\mathbb{N}$ such that $g$ is compatible
with $\lim_{s}f(n,s)$. Now by definition of $f$, there is a finite (possibly
empty) $F^{\prime}\subseteq X$ and $t\in\mathbb{N}$ such that
$\lim_{s}f(n,s)=\Psi^{F\cup F^{\prime}}(n,t)$. We claim that $(F\cup
F^{\prime},X-\\{0,\dots,\max F^{\prime}\\})$ forces $\mathcal{R}_{\Psi,m}$.
Indeed, by construction of $f$ and since we considered the limit, we have
that, for every $F^{\prime\prime}\subseteq X-\\{0,\dots,\max F^{\prime}\\}$
and cofinitely many $t^{\prime}\in\mathbb{N}$, $\Psi^{F\cup F^{\prime}\cup
F^{\prime\prime}}(n,t^{\prime})=\Psi^{F\cup F^{\prime}}(n,t)$. ∎

Let $\mathcal{F}$ be a sufficiently generic filter for computable Mathias
forcing and let $G=\bigcup_{(F,X)\in\mathcal{F}}F$. By genericity, $G$ is
$\vec{R}$-cohesive, since given a condition $(F,X)$ and a computable set
$R_{x}$, either $(F,X\cap R_{x})$ or $(F,X\cap\overline{R}_{x})$ is a valid
extension. By Lemma 5.17, for every $m$ and $\Gamma_{m}$-functional $\Gamma$,
$g$ diagonalizes against $\Gamma^{G}$. Thus, by Lemma 5.9, $g$ is
$\Gamma$-hyperimmune relative to $G$. ∎

######  Corollary 5.18.

For every $\Gamma$-hyperimmune function $f:\mathbb{N}\to 3$, there exists a
cross-constraint ideal $\mathcal{M}\models\mathsf{COH}$ such that $f$ is
$\Gamma$-hyperimmune relative to every element of $\mathcal{M}$.

###### Proof.

We construct a sequence of sets $Z_{0}\leqslant_{T}Z_{1}\leqslant_{T}\ldots$
such that for any integer $n=\langle i,k,e\rangle$,

  * •

$f$ is $\Gamma$-hyperimmune relative to $Z_{n}$.

  * •

if $n=\langle 0,k,e\rangle$, and if $\Phi_{e}^{Z_{k}}$ is an instance of
$\mathsf{CC}$, then $Z_{n+1}$ computes a solution.

  * •

if $n=\langle 1,k,e\rangle$, and if $\Phi_{e}^{Z_{k}}$ is an instance of
$\mathsf{COH}$, then $Z_{n+1}$ computes a solution.

Define $Z_{0}\coloneqq\emptyset$. Suppose $Z_{n}$ has been defined. If
$n=\langle 0,k,e\rangle$ and $\Phi_{e}^{Z_{k}}$ is not a left-full cross-tree,
then $Z_{n+1}\coloneqq Z_{n}$. Otherwise, by Theorem 5.15 relativized to
$Z_{n}$, there is a pair of paths $P_{0}$ and $P_{1}$, such that $f$ is
$\Gamma$-hyperimmune relative to $P_{0}\oplus P_{1}\oplus Z_{n}$. In which
case $Z_{n+1}\coloneqq P_{0}\oplus P_{1}\oplus Z_{n}$. If $n=\langle
1,k,e\rangle$ and $\Phi_{e}^{Z_{k}}$ is not a countable sequence of sets, then
$Z_{n+1}\coloneqq Z_{n}$. Otherwise, by Theorem 5.16 relativized to $Z_{n}$,
there is a $\Phi_{e}^{Z_{k}}$-cohesive set $C$, such that $f$ is
$\Gamma$-hyperimmune relative to $C\oplus Z_{n}$. In which case
$Z_{n+1}\coloneqq C\oplus Z_{n}$.

By construction, the class $\mathcal{M}\coloneqq\\{X\in 2^{\mathbb{N}}:\exists
n,X\leqslant_{T}Z_{n}\\}$ is a cross-constraint ideal such that $f$ is
$\Gamma$-hyperimmune relative to every element of $\mathcal{M}$. ∎

###  5.2 Reducibility results

######  Definition 5.19.

A problem $\mathsf{P}$ is _strongly omnisciently computably reducible_ to a
problem $\mathsf{Q}$, noted $\mathsf{P}\leqslant_{soc}\mathsf{Q}$, if for
every $\mathsf{P}$-instance $X$, there exists a $\mathsf{Q}$-instance
$\widehat{X}$ such that, for every $\mathsf{Q}$-solution $\widehat{Y}$ of
$\widehat{X}$, $\widehat{Y}$ computes a $\mathsf{P}$-solution to $X$.

Contrary to computable reduction, no effectiveness is imposed on the
complexity of the $\mathsf{Q}$-instance $\widehat{X}$ to solve the
$\mathsf{P}$-instance $X$. Moreover, the solution to the $\mathsf{P}$-instance
has to be computable from the solution $\widehat{Y}$ to the
$\mathsf{Q}$-instance $\widehat{X}$, without the help of $X$.

######  Theorem 5.20 (Liu [22, Theorem 2.1]).

$\mathsf{RT}^{1}_{3}\not\leqslant_{\text{soc}}(\mathsf{RT}^{1}_{2})^{*}$

###### Proof.

Let $\mathcal{M}$ be a countable cross-constraint ideal (such an ideal exists
thanks to Corollary 4.7), and let $f\in\mathcal{X}(0)$ be hyperimmune relative
to any set in $\mathcal{M}$. For any $g\in\mathcal{X}(1)$, by Theorem 3.13,
there are sets $\vec{G}$ witnessing the inequality
$\mathsf{RT}^{1}_{3}\not\leqslant_{\text{soc}}(\mathsf{RT}^{1}_{2})^{*}$. ∎

Liu [22, Theorem 4.1] proved that
$\mathsf{SRT}^{2}_{3}\not\leqslant_{c}(\mathsf{SRT}^{2}_{2})^{*}$. We
strengthen his result by proving that it holds even for non-stable instances
of $\mathsf{RT}^{2}_{2}$.

######  Theorem 5.21.

$\mathsf{SRT}^{2}_{3}\not\leqslant_{c}(\mathsf{RT}^{2}_{2})^{*}$

###### Proof.

By proposition 5.13 there exists a $\Delta^{0}_{2}$ coloring $f:\mathbb{N}\to
3$ which is $\Gamma$-hyperimmune. Using Shoenfield’s limit lemma, there is a
stable computable function $h:[\mathbb{N}]^{2}\to 3$ such that for every $x$,
$\lim_{y}h(x,y)=f(x)$. Consider $h$ as a computable instance of
$\mathsf{SRT}^{2}_{3}$. Fix any $r$-tuple of computable colorings
$g_{0},\ldots,g_{r-1}:[\mathbb{N}]^{2}\to 2$ for some $r\in\mathbb{N}$. It
suffices to show the existence of $g_{i}$-homogeneous sets $H_{i}$ for every
$i<r$ such that $\bigoplus_{j<r}H_{j}$ does not compute any infinite
$h$-homogeneous set.

By Corollary 5.18, there is a countable cross-constraint ideal
$\mathcal{M}\models\mathsf{COH}$ for which $f$ is $\Gamma$-hyperimmune
relative to any set in $\mathcal{M}$. In particular, since
$g_{0},\dots,g_{r-1}$ are computable, they belong to $\mathcal{M}$. Moreover,
by Lemma 5.12, $f$ is hyperimmune relative to every element of $\mathcal{M}$.
By Theorem 3.16, there exists $g_{i}$-homogeneous sets $H_{i}$ for every
$i<r$, such that $\bigoplus_{j<r}H_{j}$ does not compute any infinite
$f$-homogeneous set. Since any $h$-homogeneous set is $f$-homogeneous, then
$\bigoplus_{j<r}H_{j}$ does not compute any infinite $h$-homogeneous set. ∎

######  Definition 5.22.

A set $H\subseteq\mathbb{N}$ is _pre-homogeneous_ for a coloring
$f:[\mathbb{N}]^{n+1}\to k$ if $\forall\sigma\in[H]^{n},\forall
z{>}y{>}\max\sigma,f(\sigma,y)=f(\sigma,z)$

Jockusch [17, Lemma 5.4] proved that for every computable coloring
$f:[\mathbb{N}]^{n+1}\to k$, every PA degree relative to $\emptyset^{\prime}$
computes an infinite pre-homogeneous set for $f$. Moreover, for $n\geq 2$,
Hirschfeldt and Jocksuch [15, Theorem 2.1] proved a reversal.

######  Theorem 5.23.

For every $n\geq 2$,
$\mathsf{SRT}^{n}_{3}\not\leqslant_{c}(\mathsf{RT}^{n}_{2})^{*}$

###### Proof.

We prove by induction on $n\geq 2$ that for every set $P$, there exists a
$\Delta^{0}_{n}(P)$ coloring $f:\mathbb{N}\to 3$ such that for every $r\geq 1$
every $r$-tuple of $P$-computable colorings
$g_{0},\dots,g_{r-1}:[\mathbb{N}]^{n}\to 2$, there are infinite
$\vec{g}$-homogeneous sets $G_{0},\dots,G_{r-1}$ such that $\vec{G}\oplus P$
does not compute any infinite $f$-homogeneous set.

The case $n=2$ corresponds to a relativized form of Theorem 5.21. Now suppose
the hypothesis holds for some $n\in\mathbb{N}$. Fix some set $P$, and let
$Q\gg P^{\prime}$ be such that $Q^{\prime}\leqslant_{T}P^{\prime\prime}$
(which exists by relativization of the low basis theorem (Jockusch and Soare
[18])).

By induction hypothesis relativized to $Q$, there exists a $\Delta^{0}_{n}(Q)$
(i.e. $\Delta^{0}_{n+1}(P)$) coloring $f:\mathbb{N}\to 3$ such that for every
$r\geq 1$ every $r$-tuple of $Q$-computable colorings
$g_{0},\dots,g_{r-1}:[\mathbb{N}]^{n}\to 2$, there are infinite
$\vec{g}$-homogeneous sets $G_{0},\dots,G_{r-1}$ such that $\vec{G}\oplus Q$
does not compute any infinite $f$-homogeneous set.

Now, consider an $r$-tuple of $P$-computable colorings
$h_{0},\dots,h_{r-1}:[\mathbb{N}]^{n+1}\to 2$. By Jockusch [17, Lemma 5.4],
$Q$ computes infinite sets $C_{0},\dots,C_{r-1}\subseteq\mathbb{N}$ pre-
homogeneous for $\widetilde{h}_{0},\dots,\widetilde{h}_{r-1}$. For $s<r$, let
$g_{s}:[\mathbb{N}]^{n}\to 2$ be the $Q$-computable coloring defined by
$g_{s}(i_{0},\dots,i_{n-1})=h_{s}(x^{s}_{i_{0}},\dots,x^{s}_{i_{n-1}},y)$,
where $C_{s}=\\{x^{s}_{0}<x^{s}_{1}<\dots\\}$ and $y\in C_{s}$ is any element
bigger than $x^{s}_{i_{n-1}}$.

By choice of $f$, there are infinite $\vec{g}$-homogeneous sets
$G_{0},\dots,G_{r-1}$ such that $\vec{G}\oplus Q$ does not compute any
infinite $f$-homogeneous set. In particular, letting $H_{s}=\\{x^{s}_{i}:i\in
G_{s}\\}$, $H_{s}$ is $h_{s}$-homogeneous, and since $\vec{H}\oplus
P\leq_{T}\vec{G}\oplus Q$, then $\vec{H}\oplus P$ does not compute any
infinite $f$-homogeneous set. This completes our induction.

Finally, by Shoenfield’s limit lemma, for every $n\geq 2$, there exists a
stable computable coloring $\widehat{f}:[\mathbb{N}]^{n}\to 3$ such that any
infinite $\widehat{f}$-homogeneous set is $f$-homogeneous, where
$f:\mathbb{N}\to 3$ is the function witnessed by the inductive proof.

∎

## References

  * [1] Paul-Elliot Anglès d’Auriac, Peter Cholak, Damir Dzhafarov, Benoît Monin, and Ludovic Patey.  Milliken’s Tree Theorem and Its Applications: A Computability-Theoretic Perspective.  Mem. Amer. Math. Soc., 293(1457), 2024.
  * [2] David R. Bélanger.  Conservation theorems for the cohesiveness principle.  2022\.
  * [3] Vasco Brattka and Tahina Rakotoniaina.  On the uniform computational content of Ramsey’s theorem.  J. Symb. Log., 82(4):1278–1316, 2017.
  * [4] Peter A. Cholak, Damir D. Dzhafarov, Denis R. Hirschfeldt, and Ludovic Patey.  Some results concerning the $\mathsf{SRT}^{2}_{2}$ vs. $\mathsf{COH}$ problem.  Computability, 9(3-4):193–217, 2020.
  * [5] Peter A. Cholak, Carl G. Jockusch, and Theodore A. Slaman.  On the strength of ramsey’s theorem for pairs.  The Journal of Symbolic Logic, 66(1):1–55, 2001.
  * [6] Jennifer Chubb, Jeffry L. Hirst, and Timothy H. McNicholl.  Reverse mathematics, computability, and partitions of trees.  J. Symbolic Logic, 74(1):201–215, 2009.
  * [7] Adam R. Day and Jan Reimann.  Independence, relative randomness, and PA degrees.  Notre Dame J. Form. Log., 55(1):1–10, 2014.
  * [8] François G. Dorais, Damir D. Dzhafarov, Jeffry L. Hirst, Joseph R. Mileti, and Paul Shafer.  On uniform relationships between combinatorial problems.  Trans. Amer. Math. Soc., 368(2):1321–1359, 2016.
  * [9] Rod Downey, Noam Greenberg, Matthew Harrison-Trainor, Ludovic Patey, and Dan Turetsky.  Relationships between computability-theoretic properties of problems.  J. Symb. Log., 87(1):47–71, 2022.
  * [10] Damir D. Dzhafarov, Jun Le Goh, Denis R. Hirschfeldt, Ludovic Patey, and Arno Pauly.  Ramsey’s theorem and products in the Weihrauch degrees.  Computability, 9(2):85–110, 2020.
  * [11] Damir D. Dzhafarov and Carl G. Jockusch, Jr.  Ramsey’s theorem and cone avoidance.  J. Symbolic Logic, 74(2):557–578, 2009.
  * [12] Damir D. Dzhafarov and Carl Mummert.  Reverse mathematics—problems, reductions, and proofs.  Theory and Applications of Computability. Springer, Cham, [2022] ©2022.
  * [13] Benedict Eastaugh.  Slicing the truth: on the computability theoretic and reverse mathematical analysis of combinatorial principles [book review of MR3244278].  Studia Logica, 105(4):873–879, 2017.
  * [14] Ju. L. Eršov.  A certain hierarchy of sets. II.  Algebra i Logika, 7(4):15–47, 1968.
  * [15] Denis R. Hirschfeldt and Carl G. Jockusch, Jr.  On notions of computability-theoretic reduction between $\Pi_{2}^{1}$ principles.  J. Math. Log., 16(1):1650002, 59, 2016.
  * [16] Denis R. Hirschfeldt, Carl G. Jockusch, Jr., Bjø rn Kjos-Hanssen, Steffen Lempp, and Theodore A. Slaman.  The strength of some combinatorial principles related to Ramsey’s theorem for pairs.  In Computational prospects of infinity. Part II. Presented talks, volume 15 of Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap., pages 143–161. World Sci. Publ., Hackensack, NJ, 2008.
  * [17] Carl G. Jockusch, Jr.  Ramsey’s theorem and recursion theory.  J. Symbolic Logic, 37:268–280, 1972.
  * [18] Carl G. Jockusch, Jr. and Robert I. Soare.  $\Pi^{0}_{1}$ classes and degrees of theories.  Trans. Amer. Math. Soc., 173:33–56, 1972.
  * [19] Laurie Kirby and Jeff Paris.  Accessible independence results for Peano arithmetic.  Bull. London Math. Soc., 14(4):285–293, 1982.
  * [20] Manuel Lerman, Reed Solomon, and Henry Towsner.  Separating principles below Ramsey’s theorem for pairs.  J. Math. Log., 13(2):1350007, 44, 2013.
  * [21] Jiayi Liu.  Rt22 does not imply wkl0.  The Journal of Symbolic Logic, 77(2):609–620, 2012.
  * [22] Lu Liu.  The coding power of a product of partitions.  Israel J. Math., 255(2):645–683, 2023.
  * [23] Ludovic Patey.  The strength of the tree theorem for pairs in reverse mathematics.  J. Symb. Log., 81(4):1481–1499, 2016.
  * [24] Ludovic Patey.  The weakness of being cohesive, thin or free in reverse mathematics.  Israel J. Math., 216(2):905–955, 2016.
  * [25] Ludovic Patey.  Iterative forcing and hyperimmunity in reverse mathematics.  Computability, 6(3):209–221, 2017.
  * [26] Ludovic Patey.  Partial orders and immunity in reverse mathematics.  Computability, 7(4):323–339, 2018.
  * [27] David Seetapun and Theodore A. Slaman.  On the strength of Ramsey’s theorem.  volume 36, pages 570–582. 1995.  Special Issue: Models of arithmetic.
  * [28] Stephen G. Simpson.  Subsystems of Second Order Arithmetic.  Perspectives in Logic. Cambridge University Press, 2 edition, 2009.
  * [29] Robert I. Soare.  Turing computability.  Theory and Applications of Computability. Springer-Verlag, Berlin, 2016\.  Theory and applications.
  * [30] Henry Towsner.  On maximum conservative extensions.  Computability, 4(1):57–68, 2015.
  * [31] Wei Wang.  The definability strength of combinatorial principles.  J. Symb. Log., 81(4):1531–1554, 2016.