Ramsey’s theorem asserts that every k-coloring of
$[\omega ]^n$
admits an infinite monochromatic set, where
$[X]^n$
denotes the set of the unordered n-tuples over X. This theorem plays an central role in reverse mathematics, as Ramsey’s theorem for pairs is historically the first example of a theorem escaping the structural phenomenon known as the “Big Five” phenomenon. See Simpson [Reference Simpson27] for a reference on the early reverse mathematics. In his celebrated theorem, Seetapun [Reference Seetapun and Slaman26] proved that Ramsey’s theorem for pairs admits cone avoidance, that is, for any fixed noncomputable set C, every computable k-coloring of
$[\omega ]^2$
admits an infinite monochromatic set H which does not compute C. Since then, many consequences of Ramsey’s theorem have been studied from a computability-theoretic viewpoint, including the
$\operatorname {\mathrm {{\mathsf {EM}}}}$
theorem [Reference Bovykin and Weiermann1], the Ascending Descending sequence principle [Reference Hirschfeldt and Shore14], the free set and thin set theorems [Reference Cholak, Giusto, Hirst and Jockusch2] and the rainbow Ramsey theorem [Reference Csima, Hirschfeldt, Knight and Soare6]. Seeing these statements as problems, in terms of instances and solutions, the community studied basis theorems for various computability-theoretic properties, including cone avoidance for computable instances, but also for arbitrary instances. This latter property is known as strong cone avoidance.
In this article, we generalize the above analysis by designing a general class of Ramsey-like statements encompassing the above examples, and providing general criteria to decide whether any such statement admits (strong) cone avoidance. We start with a short survey on cone avoidance for Ramsey’s theorem in §1. Then, we define in §2 the class of Ramsey-like statements to be those of the form “For every coloring
$\,f : [\omega ]^n \to k$
, there is an infinite set
$H \subseteq \omega $
avoiding some set of forbidden patterns relative to f.” This class contains Ramsey’s theorem, but also the
$\operatorname {\mathrm {{\mathsf {EM}}}}$
theorem. We prove that this class contains a maximal statement admitting strong cone avoidance (
${\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k)$
and cone avoidance (
${\mathsf {CA}}\mbox {-}{\mathsf {RT}}^n_k$
) and characterize the statements admitting strong cone avoidance and cone avoidance as those identically reducible to
${\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
and
${\mathsf {CA}}\mbox {-}{\mathsf {RT}}^n_k$
, respectively. In §3, we define the class of promise Ramsey-like statements which generalizes the class of Ramsey-like statements by restricting the instances to those satisfying some property. These statements as then of the form “For every coloring
$\,f : [\omega ]^n \to k$
such that
$\omega $
avoids some set of forbidden patterns relative to f, there is an infinite set
$H \subseteq \omega $
avoiding some other set of forbidden patterns relative to f.” This enables us to express statements about other structures, such as linear orders and partial orders, including the Ascending Descending sequence and the Chain Antichain principle, but also statements about
$\omega $
-colorings over
$[\omega ]^n$
, such as the free set or the rainbow Ramsey theorem. In §4, we apply the previous analysis to reprove many existing theorems, including cone avoidance of Ramsey’s theorem for pairs [Reference Seetapun and Slaman26], strong cone avoidance of Ramsey’s theorem for singletons [Reference Dzhafarov and Jockusch9], strong cone avoidance of the
$\operatorname {\mathrm {{\mathsf {EM}}}}$
theorem [Reference Patey20], strong cone avoidance of the thin set and free set theorems [Reference Wang29], among others. Last, in §5, we state some remaining open questions and suggest further developments.
Put aside the practical application of this general framework to obtain forcing-free proofs of cone and strong cone avoidance, the actual statements of
${\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
and
${\mathsf {CA}}\mbox {-}{\mathsf {RT}}^n_k$
and the resulting decidability criteria provide some further insights on the nature of computation of Ramsey-like statements. One can see a function
$\mu : \omega \to \omega $
as a measure of largeness of the intervals over
$\omega $
, by saying that
$[x, y]$
is
$\mu $
-large if
$\mu (x) \leq y$
. The statements
${\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
and
${\mathsf {CA}}\mbox {-}{\mathsf {RT}}^n_k$
are both of the form “For every coloring
$\,f : [\omega ]^n \to k$
, there is a function
$\mu : \omega \to \omega $
and an infinite set
$H \subseteq \omega $
such that for every
$D \in [H]^n$
,
$\,f(D)$
depends only on the
$\mu $
-largeness analysis over D.” This gives further evidence that Ramsey-like theorems get their computational power out of the sparsity of the solutions, and more generally that Ramsey-like theorems compute through moduli.
1 A short survey on encodability by Ramsey’s theorem
For the sake of clarity, we will adopt a thematic presentation, independently of the historical aspects of these discoveries. Ramsey’s theorem is a combinatorial theorem at the foundation of Ramsey’s theory. This theory studies the conditions under which given a sufficiently large amount of data, one can see the emergence of some structure. A k-coloring of
$[\omega ]^n$
is a function
$\,f : [\omega ]^n \to k$
. A set
$H \subseteq \omega $
is f-homogeneous if f is constant on
$[H]^n$
.
Statement 1.1 (Ramsey’s theorem)
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
: Every coloring
$\,f : [\omega ]^n \to k$
admits an infinite f-homogeneous set.
Ramsey’s theorem plays a central role in reverse mathematics. It is historically the first theorem which does not belong to the empirical structural observation of mathematics. This motivated the computability-theoretic analysis of Ramsey’s theorem and its consequences.
One can see Ramsey’s theorem as a mathematical problem, expressed in terms of instances and solutions. Here, an instance of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
is a coloring
$\,f : [\omega ]^n \to k$
. A solution to an
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-instance f is an infinite f-homogeneous set. The computable analysis of Ramsey’s theorem consists of, given an instance of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
, studying the complexity of its solutions from a computable and a proof-theoretic viewpoint. This study started with Jockusch [Reference Jockusch15], who proved that every computable instance of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
admits an arithmetical solution.
In this article, we are interested in the ability of Ramsey’s theorem to compute Turing degrees, that is, the existence of (computable or not) instances of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
such that every solution computes a fixed Turing degree.
1.1 Encodability by Ramsey’s theorem
Given a problem
$\mathsf {P}$
with instances and solutions, we say that a set A is encodable by
$\mathsf {P}$
, or
$\mathsf {P}$
-encodable, if there is an (arbitrary) instance of
$\mathsf {P}$
such that every solution computes A.
The study of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-encodable sets is closely bound to the ability of Ramsey’s theorem to compute fast-growing functions. Suppose a set A admits a modulus, that is, a function
$\mu : \omega \to \omega $
such that every function dominating
$\mu $
computes A. Then, define the
${\operatorname {\mathrm {{\mathsf {RT}}}}}^2_2$
-instance
$\,f : [\omega ]^2 \to 2$
for each
$x < y$
by
$\,f(x, y) = 1$
if and only if
$y \geq \mu (x)$
, that is, if the interval
$[x, y]$
is sufficiently large. Every infinite f-homogeneous set H must be of color 1, and its principal function
$p_H : \omega \to \omega $
, which on n associates the nth element of H, dominates
$\mu $
and therefore computes A.
Such an argument shows that if a set A admits a modulus, then it is
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-encodable, for
$n \geq 2$
and
$k \geq 2$
. Moreover, this encodability is witnessed by constructing an instance of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
whose solutions are sparse enough so that their principal functions are fast-growing. The concept of modulus was introduced by Groszek and Slaman [Reference Groszek and Slaman12], who proved, building up on Solovay’s work, that the sets admitting a modulus are precisely the hyperarithmetical sets (see Theorem 1.3). On the other hand, Solovay [Reference Solovay28] proved that no other degree can be encoded by Ramsey’s theorem, using the notion of computable encodability. Given a set
$X \subseteq \omega $
, we let
$[X]^\omega $
be the collection of all the infinite subsets of X.
Definition 1.2. A set A is computably encodable if for every set
$X \in [\omega ]^\omega $
, there is a set
$Y \in [X]^\omega $
such that
$Y \geq _T A$
.
Suppose that a set A is computed by an instance
$\,f : [\omega ]^n \to k$
of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
, in other words, every infinite f-homogeneous set computes A. In particular, since for every set
$X \in [\omega ]^\omega $
, there is an infinite f-homogeneous set
$H \subseteq X$
, then the set A is computably encodable. The following equivalence proves that the only Turing degrees which can be computed by an instance of Ramsey’s theorem are the ones which admit a modulus, hence those who can be computed using fast-growing functions.
Theorem 1.3 (Solovay [Reference Solovay28], Groszek and Slaman [Reference Groszek and Slaman12])
Given a set A, the following are equivalent
-
(a) A is computably encodable.
-
(b) A is hyperarithmetic.
-
(c) A admits a modulus.
One case however remains, namely, Ramsey’s theorem for singletons. Intuitively, one cannot build an instance of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^1_2$
whose solutions are sparse everywhere, so that their principal functions are sufficiently fast-growing. Indeed, given a
${\operatorname {\mathrm {{\mathsf {RT}}}}}^1_2$
-instance
$\,f : \omega \to 2$
, in order to ensure that the f-homogeneous sets for color 0 are all sparse, one has to set
$\,f(x) = 1$
for many
$x \in \omega $
. But then, one can construct nonsparse f-homogeneous sets for color 1. Actually, Ramsey’s theorem for singletons has no encodability power, as formalized by the notion of strong cone avoidance.
Definition 1.4. A problem
$\mathsf {P}$
admits strong cone avoidance if for every set Z, every
$C \not \leq _T Z$
and every
$\mathsf {P}$
-instance X, there is a
$\mathsf {P}$
-solution Y to X such that
$C \not \leq _T Z \oplus Y$
.
Building on the work of Seetapun and Slaman [Reference Seetapun and Slaman26] and of Cholak et al. [Reference Cholak, Jockusch and Slaman3], Dzhafarov and Jocksuch [Reference Dzhafarov and Jockusch9] proved that Ramsey’s theorem for singletons (
${\operatorname {\mathrm {{\mathsf {RT}}}}}^1_k$
) admits strong cone avoidance, thereby completing the picture of which sets are encodable by Ramsey’s theorem. To summarize, a set is encodable by
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
with
$n \geq 2$
if and only if it is hyperarithmetic, and is encodable by
${\operatorname {\mathrm {{\mathsf {RT}}}}}^1_k$
if and only if it is computable.
1.2 Encodability by computable instances
One may naturally want to refine the previous analysis, and study the
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-encodable sets with respect to the computational complexity of its instances. Jockusch [Reference Jockusch15] proved that every computable instance of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
admits an arithmetical solution. On the lower bound side, he proved that for every
$n \geq 3$
, there is computable instance of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_2$
such that every solution computes
$\emptyset ^{(n-2)}$
. The proof is a simple effectivization of the previous section.
In the other direction, Seetapun and Slaman [Reference Seetapun and Slaman26] proved that Ramsey’s theorem for pairs (
${\operatorname {\mathrm {{\mathsf {RT}}}}}^2_k$
) has no encodability power when restricted to computable instances, in the following sense.
Definition 1.5. A problem
$\mathsf {P}$
admits cone avoidance if for every set Z, every
$C \not \leq _T Z$
and every Z-computable
$\mathsf {P}$
-instance X, there is a
$\mathsf {P}$
-solution Y to X such that
$C \not \leq _T Z \oplus Y$
.
While strong cone avoidance expresses the combinatorial failure of
$\mathsf {P}$
to encode any noncomputable set, cone avoidance only expresses the computational weakness of
$\mathsf {P}$
. There is a deep link between the combinatorial features of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
and the computational features of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^{n+1}_k$
, as expressed by Cholak and Patey [Reference Cholak and Patey4, Theorem 1.5]. One can deduce cone avoidance of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^2_k$
from strong cone avoidance of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^1_k$
, although historically, Seetapun and Slaman [Reference Cholak, Jockusch and Slaman3] first proved cone avoidance of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^2_k$
. Cholak et al. [Reference Cholak, Jockusch and Slaman3, theorem 12.2] (proof fixed in [Reference Hirschfeldt and Jockusch13, appendix A]), relativized cone avoidance of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^2_k$
to prove that for every
$n \geq 2$
, if a set A is not
$\Delta ^0_{n-1}$
, then every computable instance of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
admits a solution H such that
$A \not \leq _T H$
. This completes the study of the sets encodable by computable instances of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
. Indeed, for every
$n \geq 2$
, a set A is encodable by a computable instance of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
if and only if A is
$\Delta ^0_{n-1}$
.
1.3 Encodability by the thin set theorems
The previous sections give a complete picture of which sets are encodable by Ramsey’s theorem, with or without restricting the complexity of the instances. This could be the end of the story. However, Wang [Reference Wang29] surprisingly showed that by weakening the notion of homogeneity to allow sufficiently many colors in the solutions, one obtains strong cone avoidance.
Statement 1.6 (Thin set theorem)
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_{<\infty,\ell }$
: For every coloring
$\,f : [\omega ]^n \to k$
, there is an infinite set
$H \subseteq \omega $
such that
$|f[H]^n| \leq \ell $
.
Wang [Reference Wang29] proved that for every
$n \geq 1$
and every sufficiently large
$\ell \in \omega $
,
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_{<\infty, \ell }$
admits strong cone avoidance. On the other hand, Cholak and Patey [Reference Cholak and Patey4, theorem 3.2], adapting Dorais et al. [Reference Dorais, Dzhafarov, Hirst, Mileti and Shafer8, proposition 5.5], proved that if
$\ell < 2^{n-1}$
,
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_{<\infty, \ell }$
can still compute arbitrarily fast-growing functions, and therefore computes all the hyperarithmetic sets. More precisely.
Theorem 1.7 (Cholak and Patey)
Fix
$n \geq 1$
.
-
(a) For every function
$\mu : \omega \to \omega $
, there is an instance of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_{<\infty, 2^{n-1}-1}$
such that every solution computes a function dominating
$\mu $
. -
(b) If A is not arithmetical, then every instance of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_{<\infty, 2^{n-1}}$
has a solution which does not compute A.
Using the previous sections, whenever a set A is not hyperarithmetical, it is not
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_2$
-encodable, hence not
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_{<\infty, \ell }$
-encodable for any
$\ell \geq 1$
. Whenever A is hyperarithmetical, but not arithmetical, then it is
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_{<\infty, \ell }$
-encodable if and only if
$\ell < 2^{n-1}$
. The case of the the arithmetical sets must be treated independently.
Consider the halting set
$\emptyset '$
. The standard modulus of
$\emptyset '$
is defined by letting
$\mu (n)$
be the smallest time t at which for every
$e < n$
, if
$\Phi _e(e)\downarrow $
, then
$\Phi _e(e)$
halts before stage t. One can in particular computably approximate the function
$\mu $
from below. This is the notion of left-c.e. function.
Definition 1.8. A function
$\mu : \omega \to \omega $
is left-c.e. if there is a uniformly computable sequence of functions
$\mu _0, \mu _1, \dots $
with
$\mu _s : \omega \to \omega $
such that for every
$s \in \omega $
,
$\mu _s \leq \mu _{s+1}$
, and for every
$x \in \omega $
,
$\lim _s \mu _s(x) = \mu (x)$
.
The notion relativizes, and we say that a function is left-X-c.e. if the sequence of functions is uniformly X-computable. When mentioning a left-c.e. function, we will always assume that the sequence of its approximations is specified. This is why we will sometime talk about relative left-c.e. function simply to say that a sequence of lower approximations of the function is fixed, no matter the effectiveness of the sequence.
Cholak and Patey [Reference Cholak and Patey4] studied the threshold of
$\ell $
under which, given a left-c.e. function
$\mu $
, there is an instance of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_{<\infty, \ell }$
such that every solution computes a function dominating
$\mu $
. This happens to be exactly the Catalan sequence, inductively defined by
$C_0 = 1$
and
$$\begin{align*}C_{n+1} = \sum_{i=0}^n C_i C_{n-i}. \end{align*}$$
In particular,
$C_0 = 1$
,
$C_1 = 1$
,
$C_2 = 2$
,
$C_3 = 5$
,
$C_4 = 14$
,
$C_5 = 42$
,
$C_6 = 132$
,
$C_7 = 429$
,
$\dots $
Note that this sequence corresponds to the OEIS sequenceFootnote
1
A000108.
Theorem 1.9 (Cholak and Patey [Reference Cholak and Patey4])
Fix
$n \geq 1$
.
-
(a) For every left-c.e. function
$\mu : \omega \to \omega $
, there is an instance of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_{<\infty, C_n-1}$
such that every solution computes a function dominating
$\mu $
. -
(b) If A is not computable, then every instance of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_{<\infty, C_n}$
has a solution which does not compute A.
By iterating the notion of left-c.e. function, one can
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_{<\infty, C_n-1}$
-encode all the arithmetical sets for every
$n \geq 2$
. This completes the picture of the
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_{<\infty, \ell }$
-encodable sets, depending on the value of n and
$\ell $
. There are actually three classes of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_{<\infty, \ell }$
-encodable sets: the computable, arithmetical, and hyperarithmetical sets. One can also deduce which sets are encodable by computable instances of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_{<\infty, \ell }$
, using the bridge between the combinatorics of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_{<\infty, \ell }$
and the computations of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^{n+1}_{<\infty, \ell }$
. See Cholak and Patey [Reference Cholak and Patey4] for this analysis.
2 Ramsey-like theorems
As explained,
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_2$
does not admit strong cone avoidance for any
$n \geq 2$
. However, there exist some weakenings of Ramsey’s theorem which admit strong cone avoidance. The thin set theorem is an example, but also the
$\operatorname {\mathrm {{\mathsf {EM}}}}$
theorem. Given a coloring
$\,f : [\omega ]^2 \to 2$
, the
$\operatorname {\mathrm {{\mathsf {EM}}}}$
theorem asserts the existence of an infinite set
$H \subseteq \omega $
over which f is transitive, that is, for every
$x < y < z$
and
$i < 2$
, if
$\,f(x, y) = i$
and
$\,f(y, z) = i$
then
$\,f(x, z) = i$
. The author [Reference Patey20] proved that
$\operatorname {\mathrm {{\mathsf {EM}}}}$
admits strong cone avoidance. Ramsey’s theorem, the thin set theorem and the
$\operatorname {\mathrm {{\mathsf {EM}}}}$
theorem are all of the form “For every coloring
$\,f : [\omega ]^n \to k$
, there exists an infinite set
$H \subseteq \omega $
avoiding some set of forbidden patterns relative to f.” In this section, we design a general class of Ramsey-like theorems, and provide a criterion to decide which statements admit strong cone avoidance.
Definition 2.1. Fix a countable collection of variables
$x_0, x_1, \dots $
An
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-pattern P is a finite conjunction of formulas of the form
$\mathtt {f}_v(\{x_i : i \in D\})$
for some
$D \in [\omega ]^n$
and
$v < k$
, where
$\mathtt {f}_0, \dots, \mathtt {f}_{k-1}$
are n-ary relation symbols. Given an actual coloring
$\,f : [\omega ]^n \to k$
, a set of integers
$E = \{n_0 < n_1 < \dots < n_{r-1}\}\,f$
-satisfies an
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-pattern
$P \equiv \mathtt {f}_{v_0}(\{x_i : i \in D_0\}) \wedge \dots \wedge \mathtt {f}_{v_{\ell -1}}(\{x_i : i \in D_{\ell -1}\})$
if for every
$s < \ell $
, letting
$E_s = \{n_i : i \in D_s\}$
,
$\,f(E_s) = v_s$
. A set
$H \subseteq \omega\, f$
-meets P if H contains an finite subset f-satisfying P. Otherwise,
$H\, f$
-avoids P.
In the remainder of this article, we shall write
$\mathtt {f}(\{x_i : i \in D\}) = v$
for
$\mathtt {f}_v(\{x_i : i \in D\})$
for the sake of readability. For example,
$\mathtt {f}(x_5, x_6) = 0 \wedge \mathtt {f}(x_6, x_7) = 1 \wedge \mathtt {f}(x_5, x_7) = 0$
is the
${\operatorname {\mathrm {{\mathsf {RT}}}}}^2_2$
-pattern
$\mathtt {f}_0(x_5, x_6) \wedge \mathtt {f}_1(x_6, x_7) \wedge \mathtt {f}_0(x_5, x_7)$
.
Definition 2.2. Given a collection W of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-patterns, the
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-like problem
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
is the problem whose instances are colorings
$\,f : [\omega ]^n \to k$
. An
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
-solution to an instance f is an infinite set
$H \subseteq \omega\, f$
-avoiding every pattern in W.
In particular,
${\operatorname {\mathrm {{\mathsf {RT}}}}}^2_2$
is the
${\operatorname {\mathrm {{\mathsf {RT}}}}}^2_2$
-like problem
${\operatorname {\mathrm {{\mathsf {RT}}}}}^2_2(W_{{\operatorname {\mathrm {{\mathsf {RT}}}}}^2_2})$
with
$W_{{\operatorname {\mathrm {{\mathsf {RT}}}}}^2_2} = \{ \mathtt {f}(x_0, x_1) = 0 \ \wedge\ \mathtt {f}(x_2, x_3)\ =\ 1, \mathtt {f}(x_0, x_1)\ =\ 1 \wedge \mathtt {f}(x_2, x_3)\ =\ 0, \mathtt {f}(x_0, x_2)\ =\ 0 \wedge \mathtt {f}(x_1, x_3)\ =\ 1,$
$\mathtt {f}(x_0, x_2) = 1 \wedge \mathtt {f}(x_1, x_3) = 0 \}$
. Similarly,
$\operatorname {\mathrm {{\mathsf {EM}}}}$
is the
${\operatorname {\mathrm {{\mathsf {RT}}}}}^2_2$
-like problem
${\operatorname {\mathrm {{\mathsf {RT}}}}}^2_2(W_{\operatorname {\mathrm {{\mathsf {EM}}}}})$
with
$W_{\operatorname {\mathrm {{\mathsf {EM}}}}} = \{ \mathtt {f}(x_0, x_1) = 0 \wedge \mathtt {f}(x_1, x_2) = 0 \wedge \mathtt {f}(x_0, x_2) = 1, \mathtt {f}(x_0, x_1) = 1 \wedge \mathtt {f}(x_1, x_2) = 1 \wedge \mathtt {f}{(x_0, x_2) = 0}\}$
.
2.1 True Ramsey-like problems
We say that a problem is true if every instance has a solution. Intuitively, Ramsey’s theorem is the strongest structural property we can get out of a k-coloring of
$[X]^n$
, where X is an abstract set. We formalize this intuition by proving that Ramsey’s theorem is the maximal true Ramsey-like theorem.
Definition 2.3. Let
$\mathsf {P}$
and
$\mathsf {Q}$
be two problems with
$\operatorname {\mathrm {dom}}(\mathsf {P}) \subseteq \operatorname {\mathrm {dom}}(\mathsf {Q})$
. We say that
$\mathsf {P}$
is identically reducible to
$\mathsf {Q}$
(written
$\mathsf {P} \leq _{id} \mathsf {Q}$
) if for every
$I \in \operatorname {\mathrm {dom}}(\mathsf {P})$
, every
$\mathsf {Q}$
-solution to I is a
$\mathsf {P}$
-solution to I.
Theorem 2.4. Fix
$n, k \geq 1$
and a collection W of
$\,{\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-patterns. Then
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
is true if and only if
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \leq _{id} {\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
.
Proof.
$\Rightarrow $
: Suppose
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \not \leq _{id} {\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
. Let
$\,f : [\omega ]^n \to k$
be an instance of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
and let H be an infinite f-homogeneous set for some color
$i < 2$
which f-meets some
$P \in W$
. Then P is of the form
$\mathtt {f}(\{x_j : j \in D_0\}) = i \wedge \dots \wedge \mathtt {f}(\{x_j : j \in D_{\ell -1}\}) = i$
. Then, letting
$g : [\omega ]^n \to k$
be defined for every
$D \in [\omega ]^n$
by
$g(D) = i$
, g has no
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
-solution, therefore
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
is not true.
$\Leftarrow $
: Suppose
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \leq _{id} {\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
. Given an instance
$\,f : [\omega ]^n \to k$
of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
, by the classical Ramsey’s theorem, there is an infinite f-homogeneous set H. In particular, H is an
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
-solution to f, so f admits an
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
-solution and
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
is true.⊣
Before starting the analysis of cone avoidance for Ramsey-like theorems, let us introduce an important concept which will be implicitly used all over the article.
Definition 2.5. A problem
$\mathsf {P}$
is zoomable if for every
$\mathsf {P}$
-instance I and every infinite set
$X = \{x_0 < x_1 < \cdots \}$
, there is a
$\mathsf {P}$
-instance
$I_X$
such that for every
$\mathsf {P}$
-solution Y to
$I_X$
,
$\{x_n : n \in Y \}$
is a
$\mathsf {P}$
-solution to I.
One can see zoomable problems as saying that given an instance I and an infinite set X, we can zoom in on the set X and consider it as the new set
$\omega $
by renaming the elements of X. Then, after having built a solution within X seen as
$\omega $
, we can zoom out and see it as a subset of X. For example, Ramsey’s theorem is a zoomable problem, while Hindman’s theorem is not, since the zoom operation changes the semantics of the addition.
The following lemma which is implicitly used everywhere asserts that whenever a zoomable problem
$\mathsf {P}$
admits strong cone avoidance, then one can apply this strong cone avoidance within the scope of a cone avoiding reservoir.
Lemma 2.6. Let
$\mathsf {P}$
be a zoomable problem which admits strong cone avoidance. For every set Z, every set
$C \not \leq _T Z$
, every infinite Z-computable set X and every
$\mathsf {P}$
-instance I, there is a
$\mathsf {P}$
-solution
$Y \subseteq X$
such that
$C \not \leq _T Z \oplus Y$
.
Proof. Fix Z, C and X. Since
$\mathsf {P}$
is zoomable, there is a
$\mathsf {P}$
-instance
$I_X$
such that for every
$\mathsf {P}$
-solution Y to
$I_X$
,
$\{x_n : n \in Y \}$
is a
$\mathsf {P}$
-solution to I. By strong cone avoidance of
$\mathsf {P}$
applied to
$I_X$
, there is a
$\mathsf {P}$
-solution Y to
$I_X$
such that
$C \not \leq _T Z \oplus Y$
. The set
$Y_X = \{x_n : n \in Y\}$
is a
$Z \oplus Y$
-computable
$\mathsf {P}$
-solution to I. In particular,
$Y_X \subseteq X$
and
$C \not \leq _T Z \oplus Y_X$
.⊣
Similar lemmas can be proven for cone avoidance and strong cone avoidance for nonarithmetical cones (see Definition 2.15). We will use these lemmas without any further mention.
2.2 Strongly avoiding nonarithmetical cones
Recall that given a modulus
$\mu : \omega \to \omega $
of a set A, one can define a coloring
$\,f : [\omega ]^2 \to 2$
by
$\,f(x, y) = 1$
if and only if
$\mu (x) \leq y$
. Any infinite f-homogeneous set computes a function dominating
$\mu $
. Cholak and Patey [Reference Cholak and Patey4] generalized this coding in the following sense.
Definition 2.7. A graph
$\mathcal {G} = (\{0, \dots, n-1\}, E)$
of size n is a vector graph if
$E \subseteq \{ \{i, i+1\} : i < n-1\}$
.
A vector graph of size n is just a representation of a
$\{0,1\}$
-valued vector of size
$n-1$
. The choice of a graph representation is for uniformity with the later sections. Given
$n \geq 1$
, we let
$\mathcal {V}_n$
be the set of all vector graphs of size n. In particular,
$|\mathcal {V}_n| = 2^{n-1}$
. We shall actually consider functions
$\mu : \omega \to \omega ^{+}$
, where
$\omega ^{+}$
is the successor ordinal of
$\omega $
.
Definition 2.8. Let
$\mu : \omega \to \omega ^{+}$
be a function. For every
$n \geq 1$
and
$D = \{x_0 < \dots < x_{n-1}\} \in [\omega ]^n$
, let
$\mathcal {V}_n(\mu, D)$
be the graph
$\mathcal {G} = (\{0, \dots, n-1\}, E)$
such that for each
$i < n-1$
,
$\{i, i+1\} \in E$
if and only if
$\mu (x_i) \leq x_{i+1}$
.
An interval
$[x, y]$
is
$\mu $
-large if
$\mu (x) \leq y$
. Otherwise, it is
$\mu $
-small. Given a finite set
$D = \{x_0 < \dots < x_{n-1}\}$
,
$\mathcal {V}_n(\mu, D)$
is supposed to code the whole
$\mu $
-largeness information over D. Actually,
$\mathcal {V}_n(\mu, D)$
contains only the information about the adjacent intervals, namely, intervals of the form
$[x_i, x_{i+1}]$
. What about the largeness information about nonadjacent ones? For example, if
$[x, y]$
and
$[y, z]$
are both
$\mu $
-small, is
$[x, z]\ \mu $
-small or
$\mu $
-large? We shall see through the notion of
$\mu $
-transitivity that we can always restrict ourselves to sets over which the whole information of
$\mu $
-largeness is already fully specified by the
$\mu $
-largeness information on the adjacent intervals. A set
$H \subseteq \omega $
is
$\mu $
transitive if for every
$x < y < z \in H$
,
$\mu (x)> y$
and
$\mu (y)> z$
if and only if
$\mu (x)> z$
.
Lemma 2.9. Fix
$\mu : \omega \to \omega ^{+}$
and
$\rho : \omega \to \omega ^{+}$
. Given
$n \geq 1$
, let
$E = \{x_0 < \dots < x_{n-1} \}$
be a
$\mu $
-transitive set, and
$F = \{y_0 < \dots < y_{n-1} \}$
be a
$\rho $
-transitive set such that
$\mathcal {V}_n(\mu, E) = \mathcal {V}_n(\rho, F)$
. Then for every
$i < j < n$
,
$[x_i, x_j]$
is
$\mu $
-large if and only if
$[y_i, y_j]$
is
$\rho $
-large.
Proof. We prove by induction over
$m \geq 1$
that for every i,
$[x_i, x_{i+m}]$
is
$\mu $
-large if and only if
$[y_i, y_{i+m}]$
is
$\rho $
-large. The base case
$m = 1$
is the lemma hypothesis. Suppose it holds up to m. Since E is
$\mu $
-transitive, then
$[x_i, x_{i+m+1}]$
is
$\mu $
-large if and only if either
$[x_i, x_{i+m}]$
or
$[x_{i+m}, x_{i+m+1}]$
is
$\mu $
-large. By induction hypothesis, this holds if and only if either
$[y_i, y_{i+m}]$
or
$[y_{i+m}, y_{i+m+1}]$
is
$\rho $
-large. Since F is
$\rho $
-transitive, this holds if and only if
$[y_i, y_{i+m+1}]$
is
$\rho $
-large.⊣
Cholak and Patey [Reference Cholak and Patey4, theorem 3.2] proved the following theorem. Note that
$\mu $
ranges over
$\omega $
and not
$\omega ^{+}$
.
Theorem 2.10 (Cholak and Patey [Reference Cholak and Patey4])
Let
$\mu : \omega \to \omega $
be a function. For every
$n \geq 1$
, define
$\,f_n : D \mapsto \mathcal {V}_n(\mu, D)$
. For every infinite set
$H \subseteq \omega $
such that
$\mathcal {V}_n \not \subseteq f_n[H]^n$
, H computes a function dominating
$\mu $
.
In particular, this proves that for every hyperarithmetical set A, there is an
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_{<\infty, 2^{n-1}-1}$
-instance such that every solution computes A. Moreover, this coding technique is optimal for nonarithmetical sets from the viewpoint of the number of colors, in the sense that if A is nonarithmetical, then every
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_{<\infty, 2^{n-1}}$
-instance admits a solution which does not compute A.
We now prove that this optimality is not only about the number of colors, but also on the nature of the coding, by proving that for every coloring
$\,f : [\omega ]^n \to k$
and every nonarithmetical set A, there exists an infinite subdomain
$H \subseteq \omega $
such that
$A \not \leq _T H$
, and over which
$\,f {\upharpoonright } [H]^n$
behaves exactly like our function
$D \mapsto \mathcal {V}_n(\mu, D)$
, up to a renaming of the colors.
Statement 2.11.
${\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
: For every function
$\,f : [\omega ]^n \to k$
, there is a function
$\mu : \omega \to \omega ^{+}$
, an infinite
$\mu $
-transitive set
$H \subseteq \omega $
, and a coloring
$\chi : \mathcal {V}_n \to k$
such that for every
$D \in [H]^n$
,
$\,f(D) = \chi (\mathcal {V}_n(\mu, D))$
.
For
$n = 1$
, there is only one vector graph of size 1, namely
$\mathcal {G} = (\{0\}, \emptyset \}$
. Therefore
$|\mathcal {V}_1| = 1$
, and
${\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^1_k$
states the existence, for every function
$\,f : \omega \to k$
, of a unique color
$i < k$
such that for every
$x \in H$
,
$\,f(x) = i$
. Thus
${\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^1_k$
is
${\operatorname {\mathrm {{\mathsf {RT}}}}}^1_k$
. The case
$n = 2$
yields a new principle.
Statement 2.12.
${\mathsf {LARGE}}_k$
: For every coloring
$\,f : [\omega ]^2 \to k$
, there are some colors
$i_s,i_\ell < k$
and an infinite set
$H \subseteq \omega $
such that
$\,f[H]^2 \subseteq \{i_s,i_\ell \}$
and for every
$x < y < z \in H$
,
$\,f(x, y) = f(y, z) = i_s$
if and only if
$\,f(x, z) = i_s$
.
Intuitively,
$i_s$
and
$i_\ell $
are the colors of small and large intervals, respectively.
Lemma 2.13.
${\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^2_k$
is the statement
${\mathsf {LARGE}}_k$
.
Proof. We first prove that
${\mathsf {LARGE}}_k \leq _{id} {\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^2_k$
. Let
$\,f : [\omega ]^2 \to k$
be a coloring, and let H be an infinite
${\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^2_k$
-solution. By definition of
${\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^2_k$
, there is some function
$\mu : \omega \to \omega ^{+}$
and a coloring
$\chi : \mathcal {V}_2 \to k$
such that H is
$\mu $
-transitive, and for every
$x < y \in H$
,
$\,f(x, y) = \chi (\mathcal {V}_2(\mu, \{x,y\}))$
. Let
$\mathcal {G}_0 = (\{0,1\}, \emptyset \}$
and
$\mathcal {G}_1 = (\{0,1\}, \{\{0,1\}\})$
. In particular,
$\mathcal {V}_2 = \{\mathcal {G}_0, \mathcal {G}_1\}$
. Let
$i_s = \chi (\mathcal {G}_0)$
and
$i_\ell = \chi (\mathcal {G}_1)$
. Since for every
$x < y \in H$
,
$\,f(x, y) = \chi (\mathcal {V}_2(\mu, \{x,y\}))$
,
$\,f[H]^2 \subseteq \{i_s, i_\ell \}$
. We claim that for every
$x < y < z \in H$
,
$\,f(x, y) = f(y, z) = i_s$
if and only if
$\,f(x, z) = i_s$
. If
$i_s = i_\ell $
, then H is f-homogeneous for color
$i_s$
, and satisfies the property, so suppose
$i_s \neq i_\ell $
. In other words,
$\chi $
is one-to-one. Fix
$x < y < z \in H$
. Then
$\,f(x, y) = f(y, z) = i_s$
if and only if
$\mathcal {V}_2(\mu, \{x,y\}) = \mathcal {V}_2(\mu, \{y,z\}) = \mathcal {G}_0$
, if and only if
$\mu (x)> y$
and
$\mu (y)> z$
. By
$\mu $
-transitivity of H, this holds if and only if
$\mu (x)> z$
, hence
$\mathcal {V}_2(\mu, \{x,z\}) = \mathcal {G}_0$
. Since
$\chi $
is one-to-one, this holds if and only if
$\,f(x, z) = \chi (\mathcal {V}_2(\mu, \{x,z\})) = \chi (\mathcal {G}_0) = i_s$
.
We now prove that
${\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^2_k \leq _{id} {\mathsf {LARGE}}_k$
. Let
$\,f : [\omega ]^2 \to k$
be a coloring, and let
$H \subseteq \omega $
and
$i_s, i_\ell < 2$
be such that
$\,f[H]^2 \subseteq \{i_s, i_\ell \}$
and for every
$x < y < z \in H$
,
$\,f(x, y) = f(y, z) = i_s$
if and only if
$\,f(x, z) = i_s$
. Let
$\chi (\mathcal {G}_0) = i_s$
and
$\chi (\mathcal {G}_1) = i_\ell $
. For every
$x \in \omega $
, let
$\mu (x)$
be either
$\min \{ y> x : y \in H \wedge f(x, y) = i_\ell \}$
if it exists, and
$\mu (x) = \omega $
otherwise. We first claim that H is
$\mu $
-transitive. Indeed, for every
$x < y < z \in H$
,
$\mu (x)> y$
and
$\mu (y)> z$
if and only if
$\,f(x, y) = f(y, z) = i_s$
. Since H is a
$\mathsf {P}$
-solution to f, this holds if and only if
$\,f(x, z) = i_s$
, hence if and only if
$\mu (x)> z$
. Last, we claim that H is an
${\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^2_k$
-solution to f with witness
$\chi $
and
$\mu $
. Fix
$x < y \in H$
. Then
$\,f(x, y) = i_s$
if and only if
$\mu (x)> y$
, if and only if
$\mathcal {V}_2(\mu, \{x,y\}) = \mathcal {G}_0$
, if and only if
$\chi (\mathcal {V}_2(\mu, \{x,y\})) = \chi (\mathcal {G}_0) = i_s$
. Thus
$\,f(x, y) = \chi (\mathcal {V}_2(\mu, \{x,y\}))$
.⊣
By compactness, if we don’t consider
$\mu $
and
$\chi $
as part of the solution, then
${\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
can be seen as an
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-like problem, as states the following lemma.
Lemma 2.14. There is a c.e. set of
$\,{\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-like patterns W such that
${\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
is the problem
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
.
Proof. Fix a coloring
$\,f : [\omega ]^n \to k$
. By compactness, a set
$H \subseteq \omega $
is an
${\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution if and only if for every finite set
$F \subseteq H$
, there is a function
$\mu : F \to \omega ^{+}$
and a coloring
$\chi : \mathcal {V}_n \to k$
such that F is
$\mu $
-transitive and for every
$D \in [F]^n$
,
$\,f(D) = \chi (\mathcal {V}_n(\mu, D))$
. Let W be the set of all
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-patterns such that the above property does not hold. Then
${\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
is the statement
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
.⊣
Definition 2.15. A problem
$\mathsf {P}$
admits strong cone avoidance for nonarithmetical cones if for every set Z, every non-Z-arithmetical set C, and every
$\mathsf {P}$
-instance X, there is a
$\mathsf {P}$
-solution Y such that
$C \not \leq _T Z \oplus Y$
.
Theorem 2.16.
${\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
admits strong cone avoidance for nonarithmetical cones.
Proof. Fix a set Z, a non-Z-arithmetical set C and a coloring
$\,f : [\omega ]^n \to k$
.
Suppose first that C is not Z-hyperarithmetical. By Solovay [Reference Solovay28], C is not computably encodable relative to Z. Since for every infinite set
$X \subseteq \omega $
, there is an infinite
${\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution
$Y \subseteq X$
to f, there is an
${\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution H to f such that
$C \not \leq _T Z \oplus H$
.
Suppose now that C is Z-hyperarithmetical. By Groszek and Slaman [Reference Groszek and Slaman12], there is a modulus
$\mu : \omega \to \omega $
relative to Z, that is, for every function g dominating
$\mu $
,
$C \leq _T Z \oplus g$
. Let
$\,f_1$
be defined for each
$D \in [\omega ]^n$
by
$\,f_1(D) = \langle f(D), \mathcal {V}_n(\mu, D) \rangle $
. By strong cone avoidance of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_{<\infty, 2^{n-1}}$
for nonarithmetical cones (see Cholak and Patey [Reference Cholak and Patey4, theorem 4.15]), there is an infinite set
$H \subseteq X$
such that
$C \not \leq _T Z \oplus H$
and
$|f_1[H]^n| \leq 2^{n-1}$
. In particular,
$H \oplus Z$
does not compute a function dominating
$\mu $
, so by Theorem 2.10, for every
$\mathcal {G} \in \mathcal {V}_n$
, there is some
$i < k$
and some
$D \in [H]^n$
such that
$\,f_1(D) = \langle i, \mathcal {G} \rangle $
. Since
$|\mathcal {V}_n| = 2^{n-1}$
, this i is unique. For each
$\mathcal {G} \in \mathcal {V}_n$
, let
$\chi (\mathcal {G})$
be this unique i.
We claim that for every
$D \in [H]^n$
,
$\,f(D) = \chi (\mathcal {V}_n(\mu, D))$
. By definition of
$\chi $
,
$\,f_1(D) = \langle f(D), \mathcal {V}_n(\mu, D) \rangle = \langle \chi (\mathcal {V}_n(\mu, D)), \mathcal {V}_n(\mu, D) \rangle $
. It follows that
$\,f(D) = \chi (\mathcal {V}_n(\mu, D))$
. By Cholak and Patey [Reference Cholak and Patey4, corollary 5.5], there is an infinite
$\mu $
-transitive subset
$H_1 \subseteq H$
such that
$C \not \leq _T Z \oplus H_1$
. Therefore,
$H_1$
is an
${\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution to f.⊣
The following technical lemma will be useful for Theorem 2.18, Lemma 3.3 and Lemma 3.4. Note that
$\mu _0$
ranges over
$\omega ^{+}$
while
$\mu _1$
ranges over
$\omega $
.
Lemma 2.17. Fix
$\chi : \mathcal {V}_n \to k$
, and let
$\,f_0 : [\omega ]^n \to k$
and
$\,f_1 : [\omega ]^n \to k$
be two colorings. Let
$H_0$
be an infinite
${\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution to
$\,f_0$
with witnesses
$\chi $
and
$\mu _0 : \omega \to \omega ^{+}$
, and let
$H_1$
be an infinite
${\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution to
$\,f_1$
with witnesses
$\chi $
and
$\mu _1 : \omega \to \omega $
. If
$H_0\, f_0$
-meets some
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-pattern P but
$H_1\, f_1$
-avoids P, then
$H_1$
computes a function dominating
$\mu _1$
.
Proof. Since
$H_0\, f_0$
-meets some
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-pattern P, there is a finite set
$E_0 = \{x_0 < \dots < x_{r-1} \} \subseteq H_0$
which
$\,f_0$
-meets P. Suppose for the sake of contradiction that
$H_1$
does not compute a function dominating
$\mu _1$
. By Theorem 2.10, there is a finite set
$E_1 = \{y_0 < \dots < y_{r-1}\} \subseteq H_1$
of size r such that
$\mathcal {V}_r(\mu _0, E_0) = \mathcal {V}_r(\mu _1, E_1)$
. By Lemma 2.9, since
$H_0$
is
$\mu _0$
-transitive and
$H_1$
is
$\mu _1$
-transitive, for every
$I \in [r]^n$
, letting
$D_0 = \{x_i : i \in I\}$
and
$D_1 = \{y_i : i \in I\}$
,
$\mathcal {V}_n(\mu _0, D_0) = \mathcal {V}_n(\mu _1, D_1)$
. Since
$\,f_0(D_0) = \chi (\mathcal {V}_n(\mu _0, D_0))$
and
$\,f_1(D_1) = \chi (\mathcal {V}_n(\mu _1, D_1))$
, then
$\,f_0(D_0) = f_1(D_1)$
. Thus
$\,f_0 {\upharpoonright } [E_0]^n$
and
$\,f_1 {\upharpoonright } [E_1]^n$
have the same function graph. It follows that
$E_1\, f_1$
-meets P, so
$H_1\, f_1$
-meets P. Contradiction.⊣
Theorem 2.18. Let W be a collection of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-patterns such that
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \not \leq _{id} {\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
. Then for every function
$\mu : \omega \to \omega $
, there is an
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
-instance such that every solution computes a function dominating
$\mu $
.
Proof. Since
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \not \leq _{id} {\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
, there is a coloring
$\,f_{\textit{fail}} : [\omega ]^n \to k$
and an
${\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution
$H_{\textit{fail}}$
to
$\,f_{\textit{fail}}$
witnessed by a function
$\mu _{\textit{fail}} : \omega \to \omega ^{+}$
and a coloring
$\chi : \mathcal {V}_n \to k$
, and such that
$H_{\textit{fail}}$
meets some
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-pattern
$P \in W$
. Let
$\mu : \omega \to \omega $
be a function. Let
$\,f : [\omega ]^n \to k$
be an instance of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
defined by
$\,f(D) = \chi (\mathcal {V}_n(\mu, D))$
. We claim that every
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
-solution
$H \subseteq \omega $
to f computes a function dominating
$\mu $
. Let H be an
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
-solution to f. In particular,
$H\, f$
-avoids P. If H does not compute a function dominating
$\mu $
, then by Cholak and Patey [Reference Cholak and Patey4, Theorem 5.11], there is an infinite
$\mu $
-transitive subset
$H_1 \subseteq H$
such that
$H_1$
does not compute a function dominating
$\mu $
. In particular,
$H_1$
is an infinite
${\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution to f with witnesses
$\chi $
and
$\mu $
, and such that
$H_1\, f$
-avoids P. By Lemma 2.17, H computes a function dominating
$\mu $
, contradiction.⊣
Actually,
${\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
is the strongest
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-like problem which admits this avoidance property. The following theorem therefore provides a simple criterion to decide whether an
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-like problem admits strong cone avoidance for nonarithmetical cones.
Theorem 2.19. A problem
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
admits strong cone avoidance for nonarithmetical cones if and only if
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \leq _{id} {\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
.
Proof.
$\Leftarrow $
: Suppose
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \leq _{id} {\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
. Fix a set Z, a non-Z-arithmetical set C and a coloring
$\,f : [\omega ]^n \to k$
. By Theorem 2.16, there is an
${\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution H to f such that
$C \not \leq _T Z \oplus H$
. In particular, H is an
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
-solution to f.
$\Rightarrow $
: Suppose
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \not \leq _{id} {\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
. Let
$\mu : \omega \to \omega $
be a modulus of some nonarithmetical set C. By Theorem 2.18, there is an
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
-instance such that every solution computes a function dominating
$\mu $
, hence computes C. Therefore
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
does not admit strong cone avoidance for nonarithmetical cones.⊣
2.3 Strongly avoiding noncomputable cones
Whenever the modulus
$\mu : \omega \to \omega $
is left-c.e., that is, there is a uniformly computable sequence of functions
$\mu _0 \leq \mu _1 \leq \cdots $
pointwise limiting to
$\mu $
, one can exploit more information to compute functions dominating
$\mu $
. For example, let
$\,f : [\omega ]^3 \to 2$
be defined by
$\,f(x, y, z) = \langle b_0, b_1, b_2 \rangle $
, where
$b_0 = 1$
if and only if
$\mu (x) \leq y$
,
$b_1 = 1$
if and only if
$\mu (y) \leq z$
, and
$b_2 = 1$
if and only if
$\mu _z(x) \leq y$
. Cholak and Patey [Reference Cholak and Patey4, theorem 3.17] proved that every infinite set
$H \subseteq \omega $
such that
$|f[H]^3| \leq 4$
computes a function dominating
$\mu $
. We refine again their analysis to obtain a maximal
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-like principle admitting strong cone avoidance.
Definition 2.20 (Cholak and Patey [Reference Cholak and Patey4])
A largeness graph of size n is a graph
$(\{0,\ldots,n-1\}, E)$
such that
-
(a) If
$\{i,i+1\} \in E$
, then for every
$j> i+1$
,
$\{i, j\} \not \in E.$
-
(b) If
$i < j < n$
,
$\{i,i+1\} \not \in E$
and
$\{j,j+1\} \in E$
, then
$\{i, j+1\} \in E.$
-
(c) If
$i +1 < j < n - 1$
and
$\{i,j\} \in E$
, then
$\{i, j+1\} \in E.$
-
(d) If
$i+1 < j < k < n$
and
$\{i, j\} \not \in E$
but
$\{i,k\} \in E$
, then
$\{j-1, k\} \in E.$
Let us explain the intuition behind the definition of a largeness graph. Given a left-c.e. function
$\mu : \omega \to \omega $
and a finite
$\mu $
-transitive set
$D = \{x_0 < x_1 < \dots < x_{n-1}\}$
, one can define a graph
$\mathcal {G} = (\{0, \dots, n-1\}, E)$
which will represent the whole information about the largeness of the intervals
$[x_i, x_j]$
for each
$i < j < n$
. Since D is
$\mu $
-transitive, the information about
$\mu $
-largeness of the intervals
$[x_i, x_j]$
for every
$i < j$
is already fully specified by the information about
$\mu $
-largeness of
$[x_i, x_{i+1}]$
. Therefore, this information is coded only into the adjacent edges. We then set
$\{i,i+1\} \in E$
if and only if
$[x_i, x_{i+1}]$
is
$\mu $
-large.
Whenever
$[x_i, x_{i+1}]$
is
$\mu $
-small, this is witnessed after a finite approximation stage
$\mu _s$
, that is,
$[x_i, x_{i+1}]$
is
$\mu _s$
-small for all but finitely many
$s \in \omega $
. We can therefore code in
$\mathcal {G}$
the information whether some
$x_j$
(with
$j> i+1$
) is large enough to witness this fact, in the sense that
$\mu _{x_j}(x_i)> x_{i+1}$
. This information is coded into the edges
$\{i,j\}$
with
$i+1 < j$
. We then set
$\{i,j\} \in E$
if
$[x_i, x_{i+1}]$
is
$\mu _{x_j}$
-small. Although this coding does not seem consistent with the adjacent edges since the existence of an adjacent edge gives a largeness information, one should really see
$\mu _{x_j}$
-smallness of
$[x_i, x_{i+1}]$
as an information of how big the number
$x_j$
is and not on how small the interval
$[x_i, x_{i+1}]$
is.
Let us now look at the properties (a)–(d), successively. Property (a) says that if the interval
$[x_i, x_{i+1}]$
is
$\mu $
-large, then it is never
$\mu _{x_j}$
-small. This property is ensured by construction. Property (b) says that if
$[x_i, x_{i+1}]$
is
$\mu $
-small and
$[x_j, x_{j+1}]$
is
$\mu $
-large, then the approximation time
$x_{j+1}$
is large enough to witness the smallness of
$[x_i, x_{i+1}]$
. In other words,
$[x_i, x_{i+1}]$
is
$\mu _{x_{j+1}}$
-small. This property is not structurally ensured, and must be obtained by some extra assumptions on the function
$\mu $
. Property (c) simply says that if
$[x_i, x_{i+1}]$
is
$\mu _{x_j}$
-small, then it is
$\mu _{x_{j+1}}$
-small. This property is structurally ensured by the fact that
$\mu _{x_j} \leq \mu _{x_{j+1}}$
, which is true of all left-c.e. approximations. Property (d) says that if
$x_k$
is large enough to witness the
$\mu $
-smallness of
$[x_i,x_{i+1}]$
, but that
$x_j$
was not large enough to witness it, then not only by property (b),
$[x_{j-1}, x_j]$
cannot be
$\mu $
-large, but furthermore
$x_k$
is large enough to witness the smallness of
$[x_{j-1}, x_j]$
. In some sense, Property (d) is a refinement of property (b). This property must be also ensured by some extra assumptions on
$\mu $
.
Let
$\mathcal {L}_n$
be the set of all largeness graphs of size n. Recall that
$C_n$
is the nth Catalan number. Cholak and Patey [Reference Cholak and Patey4, Lemma 3.16] proved that for every
$n \geq 1$
,
$|\mathcal {L}_n| = C_n$
.
Definition 2.21. Given a relative left-c.e. function
$\mu : \omega \to \omega ^{+}$
with approximations
$\mu _0, \mu _1, \dots $
and a set
$D = \{x_0, \dots, x_{n-1}\} \subseteq \omega $
, let
$\mathcal {L}_n(\mu, D)$
be the graph
$(\{0, \dots, n-1\}, E)$
where
$E = \{ \{p, q\} : \mu _{x_q}(x_p)> x_{p+1} \wedge p+1 < q < n \} \cup \{ \{p, p+1\} : \mu (x_p) \leq x_{p+1} \}$
.
Note that
$\mathcal {L}_n(\mu, D)$
is not a largeness graph in general, because the properties (b) and (d) are not structurally satisfied. We give a sufficient property to ensure
$\mathcal {L}_n(\mu, D) \in \mathcal {L}_n$
.
Definition 2.22. A relative left-c.e. function
$\mu : \omega \to \omega $
is strongly increasing if for every
$s \in \omega $
and
$x < y \in \omega $
,
$\mu _s(x) \leq \mu _s(y)$
, and if
$\mu _{s+1}(x)> \mu _s(x)$
then
$\mu _{s+1}(y)> s$
.
Lemma 2.23. Fix a strongly increasing relative left-c.e. function
$\mu : \omega \to \omega ^{+}$
. For every
$n \geq 1$
and
$D \in [\omega ]^n$
,
$\mathcal {L}_n(\mu, D) \in \mathcal {L}_n$
.
Proof.
Claim 1: For every
$w < x < y < z$
, if
$\mu _y(w) \leq x$
and
$\mu _z(w)> x$
then
$\mu _z(x)> y$
. Let
$s \in [y, z)$
be such that
$\mu _s(w) \leq x$
and
$\mu _{s+1}> x$
. Then since
$\mu $
is strongly increasing,
$\mu _{s+1}(x)> s \geq y$
. In particular,
$\mu _z(x) \geq y$
. This proves Claim 1.
Claim 2: For every
$w < x < y$
, if
$\mu (w)> x$
and
$\mu (x) \leq y$
, then
$\mu _y(w)> x$
. Suppose that Claim 2 does not hold. Then there is some
$w < x < y$
such that
$\mu (w)> x$
,
$\mu (x) \leq y$
and
$\mu _y(w) \leq x$
. Then there is a stage
$z> y$
such that
$\mu _z(w)> x$
and
$\mu _z(x) \leq y$
. Since
$\mu _y(w) \leq x$
and
$\mu _z(w)> x$
, but
$\mu _z(x) \leq y$
, we contradict Claim 1. This proves Claim 2.
Fix
$n \geq 1$
and
$D = \{x_0 < \dots < x_{n-1}\} \in [\omega ]^n$
. We check properties
$(a-d)$
of Definition 2.20 for
$\mathcal {L}_n(\mu, D) = (\{0, \dots, n-1\}, E)$
. (a): If
$\{i,i+1\} \in E$
, then
$\mu (x_i) \leq x_{i+1}$
. In particular, for every
$j> i+1$
, since
$\mu _{x_j} \leq \mu $
,
$\mu _{x_j}(x_i) \leq x_{i+1}$
, so
$\{i,j\} \not \in E$
. (b): If
$i < j < n$
and
$\{i,i+1\} \not \in E$
and
$\{j,j+1\} \in E$
. Then
$\mu (x_i)> x_{i+1}$
and
$\mu (x_j) \leq x_{j+1}$
. Since
$\mu $
is increasing,
$\mu (x_{i+1}) \leq x_{j+1}$
. Then by Claim 2,
$\mu _{x_{j+1}}(x_i)> x_{i+1}$
. Thus
$\{i,j+1\} \in E$
. (c): If
$i+1 < j < n-1$
and
$\{i,j\} \in E$
, then
$\mu _{x_j}(x_i)> x_{i+1}$
. Since
$\mu _{x_j} \leq \mu _{x_{j+1}}$
, then
$\mu _{x_{j+1}}(x_i)> x_{i+1}$
, so
$\{i,j+1\} \in E$
. (d): If
$i+1 < j < k < n$
and
$\{i,j\} \not \in E$
but
$\{i,k\} \in E$
. Then
$\mu _{x_j}(x_i) \leq x_{i+1}$
but
$\mu _{x_k}(x_i)> x_{i+1}$
. By Claim 1,
$\mu _{x_k}(x_{i+1})> x_j$
. Since
$\mu _{x_k}$
is increasing,
$\mu _{x_k}(x_{j-1})> x_j$
. Thus
$\{j-1, k\} \in E$
.⊣
We now prove that whenever we choose a left-c.e. modulus for a set, we can always assume that it is strongly increasing, without loss of generality.
Lemma 2.24. Every left-c.e. function
$\mu : \omega \to \omega $
is dominated by a strongly increasing left-c.e. function
$g : \omega \to \omega $
.
Proof. Fix
$\mu : \omega \to \omega $
with approximations
$\mu _0, \mu _1, \dots $
. We define a uniformly computable sequence of functions
$g_0 \leq g_1 \leq \dots : \omega \to \omega $
pointwisely, that is, at stage x, we define
$g_s(x)$
for every
$s \in \omega $
. During the construction, for each approximation time s and value x, we associate a moving threshold
$t_{s, x} \in \omega $
which can only increase, starting with
$t_{s,x} = 0$
. We will ensure that
$g_s(x) \geq t_{s,x}$
.
At stage x, suppose we have defined
$g_s(y)$
for every
$y < x$
and
$s \in \omega $
. We define
$g_s(x)$
for every
$s \in \omega $
. At approximation time s, having defined
$g_u(x)$
for every
$u < s$
, we define
$g_s(x)$
to be the maximum value among
$\{ g_s(y) : y < x\}$
,
$\{ g_u(x) : u < s\}$
,
$t_{s,x}$
and
$\mu _s(x)$
. If
$s> 0$
and
$g_s(x)> g_{s-1}(x)$
, then set
$t_{s, y} = \max (t_{s, y}, s)$
for every
$y> x$
. Then go to the next approximation time
$s+1$
. Once all the approximations
$\langle g_s(x) : s \in \omega \rangle $
are defined, then go to the next stage
$x+1$
.
Claim 1: g is a strongly increasing left-c.e. function. By making
$g_s(x)$
larger than
$\{ g_s(y) : y < x\}$
, we have ensured that the function
$g_s$
is nondecreasing, that is, for every
$x < y$
,
$g_s(x) \leq g_s(y)$
. By making
$g_s(x)$
larger than
$\{ g_u(y) : u < s\}$
, we have ensured that
$g_s \leq g_{s+1}$
, hence that
$g_0, g_1, \dots $
are left-c.e. approximations. By making
$g_s(x)$
larger than
$t_{s,x}$
, we have ensured that if there is some
$y < x$
such that
$g_{s-1}(y) < g_s(y)$
, then
$g_s(x)> s-1$
. This proves Claim 1.
By making
$g_s(x)$
larger than
$\mu _s(x)$
, we have ensured that
$g(x) = \lim _s g_s(x) \geq \lim _s \mu _s(x) = \mu (x)$
. So g dominates
$\mu $
.
Claim 2: For every x,
$g(x) < \omega $
. We prove it by induction over x. Indeed, by induction hypothesis, there is a time
$v \in \omega $
such that for every
$y < x$
and
$s> v$
,
$g_s(y) = g_v(y)$
. For every
$s> v$
, the maximum value among
$\{ g_s(y) : y < x\}$
is bounded by maximum value among
$\{g(y) : y < x\}$
, which is a finite number by induction hypothesis. Moreover,
$t_{s,x} = 0$
since only stages
$y < x$
at time s can change the threshold
$t_{s,x}$
. Moreover,
$\mu _s(x)$
is bounded by
$\mu (x)$
which is again a finite number. Let m be the maximum value among
$\{g(y) : y < x\}$
,
$\{g_u(x) : u < v \}$
and
$\mu (x)$
. Then
$g_s(x) \leq m$
for every
$s> v$
. It follows that
$\lim _s g_s(x) \leq m$
. This completes the proof of Lemma 2.24.⊣
By Lemma 2.23, taking a strongly increasing relative left-c.e. modulus
$\mu $
ensures that
$\mathcal {L}_n(\mu, D)$
is a largeness graph (Definition 2.20). As seen in Lemma 2.9,
$\mu $
-transitivity ensures that
$\mu $
-largeness of the intervals over a set D is fully specified by the
$\mu $
-largeness of its adjacent intervals. However, some information still seems to be missing in
$\mathcal {L}_n(\mu, D)$
. Indeed, suppose that
$[x_i, x_{i+1}]$
and
$[x_{i+1}, x_{i+2}]$
are both
$\mu _{x_j}$
-small, that is,
$\{i, j\}$
and
$\{i+1, j\}$
are both edges on
$\mathcal {L}_n(\mu, D)$
. By
$\mu $
-transitivity, we know that
$[x_i, x_{i+2}]$
is
$\mu $
-small. However, is it
$\mu _{x_j}$
-small? Thanks to a stronger notion of
$\mu $
-transitivity, we can ensure that it will always be the case. A set
$H \subseteq \omega $
is strongly
$\mu $
-transitive if it is
$\mu $
-transitive, and for every
$w < x < y < z \in H$
such that
$\mu _z(w)> x$
and
$\mu _z(x)> y$
, then
$\mu _z(w)> y$
. In other words, if z witnesses
$\mu $
-smallness of both
$[w, x]$
and
$[x, y]$
, then it witnesses
$\mu $
-smallness of
$[w, y]$
.
Lemma 2.25. Fix two relative left-c.e. functions
$\mu : \omega \to \omega ^{+}$
and
$\rho : \omega \to \omega ^{+}$
. Given
$n \geq 1$
, let
$E = \{x_0 < \dots < x_{n-1} \}$
be a strongly
$\mu $
-transitive set, and
$F = \{y_0 < \dots < y_{n-1} \}$
be a strongly
$\rho $
-transitive set such that
$\mathcal {L}_n(\mu, E) = \mathcal {L}_n(\rho, F)$
. Then for every
$i < j < k < n$
,
$[x_i, x_j]$
is
$\mu _k$
-large if and only if
$[y_i, y_j]$
is
$\rho _k$
-large.
Proof. We prove by induction over
$m \geq 1$
that for every
$i, k$
such that
$i+m < k$
,
$[x_i, x_{i+m}]$
is
$\mu _k$
-large if and only if
$[y_i, y_{i+m}]$
is
$\rho _k$
-large. The base case
$m = 1$
is the lemma hypothesis. Suppose it holds up to m. Since E is strongly
$\mu $
-transitive, then
$[x_i, x_{i+m+1}]$
is
$\mu _k$
-large if and only if either
$[x_i, x_{i+m}]$
or
$[x_{i+m}, x_{i+m+1}]$
is
$\mu _k$
-large. By induction hypothesis, this holds if and only if either
$[y_i, y_{i+m}]$
or
$[y_{i+m}, y_{i+m+1}]$
is
$\rho _k$
-large. Since F is strongly
$\rho $
-transitive, this holds if and only if
$[y_i, y_{i+m+1}]$
is
$\rho _k$
-large.⊣
We now prove that we can computably thin out an infinite
$\mu $
-transitive set to obtain a strongly
$\mu $
-transitive infinite subset.
Lemma 2.26. Let
$\mu : \omega \to \omega ^{+}$
be a strongly increasing left-c.e. function. Every infinite
$\mu $
-transitive set
$X \subseteq \omega $
has an infinite X-computable strongly
$\mu $
-transitive subset
$Y \subseteq X$
.
Proof. Fix
$\mu $
and X. We build an infinite subsequence
$y_0 < y_1 < \dots \in X$
as follows. At stage
$0$
, let
$y_0 = \min X$
. At stage
$s> 0$
, suppose we have defined a strongly
$\mu $
-transitive finite sequence
$y_0 < \dots < y_{s-1}$
. Let
$y_s> y_{s-1}$
be the least element of X such that for every
$i < j < k < s$
, if
$[y_i, y_j]$
and
$[y_j, y_k]$
are
$\mu _{y_s}$
-small, then
$[y_i, y_k]$
is
$\mu _{y_s}$
-small. Such
$y_s$
must be found, since given a fixed tuple
$i < j < k < s$
if
$[y_i, y_j]$
and
$[y_j, y_k]$
are
$\mu $
-small, then
$[y_i, y_k]$
is
$\mu $
-small, and therefore for all but finitely many y,
$[y_i, y_k]$
is
$\mu _k$
-small. Taking a value in X bigger than the max of the thresholds for each tuple
$i < j < k < s$
, we obtain a
$y_s$
with the desired property.⊣
In the following theorem, note again that
$\mu $
ranges over
$\omega $
and not
$\omega ^{+}$
.
Theorem 2.27. Let
$\mu : \omega \to \omega $
be a strongly increasing left-c.e. function. For every
$n \geq 1$
, define
$\,f_n : D \mapsto \mathcal {L}_n(\mu, D)$
. For every infinite set
$H \subseteq \omega $
such that
$\mathcal {L}_n \not \subseteq f_n[H]^n$
, H computes a function dominating
$\mu $
.
Proof. Fix
$\mu $
,
$n \geq 1$
and H. By Lemma 2.23,
$\,f_n[H]^n \subseteq \mathcal {L}_n$
. By Cholak and Patey [Reference Cholak and Patey4, Lemma 3.16],
$|\mathcal {L}_n| = C_n$
. If
$\mathcal {L}_n \not \subseteq f_n[H]^n$
, then
$|f_n[H]^n| < C_n$
. Then by Cholak and Patey [Reference Cholak and Patey4, theorem 3.17], H computes a function dominating
$\mu $
.⊣
In the following statement, note that we state the existence of a relative left-c.e. function, which is another way of stating the existence of a sequence of functions
$\mu _0, \mu _1, \dots $
which satisfy the properties of a left-c.e. function independently of its effectiveness.
Statement 2.28.
${\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
: For every function
$\,f : [\omega ]^n \to k$
, there is a strongly increasing relative left-c.e. function
$\mu : \omega \to \omega ^{+}$
, an infinite strongly
$\mu $
-transitive set
$H \subseteq \omega $
and a coloring
$\chi : \mathcal {L}_n \to k$
such that for every
$D \in [H]^n$
,
$\,f(D) = \chi (\mathcal {L}_n(\mu, D))$
.
Again, for
$n = 1$
,
$|\mathcal {L}_n| = 1$
and
${\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^1_k$
is the statement
${\operatorname {\mathrm {{\mathsf {RT}}}}}^1_k$
. Similarly, for
$n = 2$
,
$\mathcal {L}_2 = \mathcal {V}_2$
, and
${\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^2_k$
is the same statement as
${\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^2_k$
, or equivalently
${\mathsf {LARGE}}_k$
, that is, the statement “For every coloring
$\,f : [\omega ]^2 \to k$
, there is an infinite set
$H \subseteq \omega $
and two colors
$i_s, i_\ell < k$
such that
$\,f[H]^2 \subseteq \{i_s,i_\ell \}$
and for every
$x < y < z \in H$
,
$\,f(x, y) = f(y, z) = i_s$
if and only if
$\,f(x, z) = i_s$
.”
Theorem 2.29.
${\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
admits strong cone avoidance.
Proof. Fix two sets Z and C with
$C \not \leq _T Z$
and let
$\,f : [\omega ]^n \to k$
be an instance of
${\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
.
By Lerman [Reference Lerman16, theorem 4.18], there is a set
$Z_1 \geq _T Z$
such that C is
$\Delta ^0_2(Z_1)$
but
$C \not \leq _T Z_1$
. Since C is
$\Delta ^0_2(Z_1)$
, there is a left
$Z_1$
-c.e. modulus
$\mu : \omega \to \omega $
for C. By Lemma 2.24, we can assume that
$\mu $
is strongly increasing.
Let
$\,f_1 : [\omega ]^n \to k \times \mathcal {L}_n$
be defined for each
$D \in [\omega ]^n$
by
$\,f_1(D) = \langle f(D), \mathcal {L}_n(\mu, D) \rangle $
. By strong cone avoidance of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_{<\infty, C_n}$
(Cholak and Patey [Reference Cholak and Patey4, theorem 4.18]), there is an infinite set
$H \subseteq \omega $
such that
$C \not \leq _T Z_1 \oplus H$
and
$|f_1[H]^n| \leq C_n$
. In particular,
$Z_1 \oplus H$
does not compute a function dominating
$\mu $
, so by Theorem 2.27, for every
$\mathcal {G} \in \mathcal {L}_n$
, there is some
$i < k$
and some
$D \in [H]^n$
such that
$\,f_1(D) = \langle i, \mathcal {G} \rangle $
. Since
$|\mathcal {L}_n| = C_n$
(Cholak and Patey [Reference Cholak and Patey4, Lemma 3.16]), this i is unique. For each
$\mathcal {G}$
, let
$\chi (\mathcal {G})$
be such an i.
We claim that for every
$D \in [H]^n$
,
$\,f(D) = \chi (\mathcal {L}_n(\mu, D))$
. By definition of
$\chi $
,
$\,f_1(D) = \langle f(D), \mathcal {L}_n(\mu, D)\rangle = \langle \chi (\mathcal {L}_n(\mu, D)), \mathcal {L}_n(\mu, D)\rangle $
. It follows that
$\,f(D) = \chi (\mathcal {L}_n(\mu, D))$
. By Cholak and Patey [Reference Cholak and Patey4, corollary 5.5], there is an infinite
$\mu $
-transitive subset
$H_1 \subseteq H$
such that
$C \not \leq _T Z \oplus H_1$
. By Lemma 2.26, there is an infinite strongly
$\mu $
-transitive subset
$H_2 \subseteq H_1$
such that
$C \not \leq _T Z \oplus H_2$
. Therefore,
$H_2$
is a
${\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution to f.⊣
The following technical lemma will be useful for Theorem 2.31, Lemma 3.8 and Lemma 3.9.
Lemma 2.30. Fix
$\chi : \mathcal {L}_n \to k$
, and let
$\,f_0 : [\omega ]^n \to k$
and
$\,f_1 : [\omega ]^n \to k$
be two colorings. Let
$H_0$
be an infinite
${\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution to
$\,f_0$
with witnesses
$\chi $
and
$\mu _0 : \omega \to \omega ^{+}$
, and let
$H_1$
be an infinite
${\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution to
$\,f_1$
with witnesses
$\chi $
and
$\mu _1 : \omega \to \omega $
. If
$H_0\, f_0$
-meets some
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-pattern P but
$H_1\, f_1$
-avoids P and
$\mu _1$
is left-c.e. then
$H_1$
computes a function dominating
$\mu _1$
.
Proof. Since
$H_0\, f_0$
-meets some
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-pattern P, there is a finite set
$E_0 = \{{x_0 < \dots < x_{r-1}}\} \subseteq H_0$
which
$\,f_0$
-meets P. Suppose for the sake of contradiction that
$H_1$
does not compute a function dominating
$\mu _1$
. By Theorem 2.27, there is a finite set
$E_1 = \{y_0 < \dots < y_{r-1}\} \subseteq H_1$
of size r such that
$\mathcal {L}_r(\mu _0, E_0) = \mathcal {L}_r(\mu _1, E_1)$
. By Lemma 2.9 and Lemma 2.25, since
$H_0$
is strongly
$\mu _0$
-transitive and
$H_1$
is strongly
$\mu _1$
-transitive, for every
$I \in [r]^n$
, letting
$D_0 = \{x_i : i \in I\}$
and
$D_1 = \{y_i : i \in I\}$
,
$\mathcal {L}_n(\mu _0, D_0) = \mathcal {L}_n(\mu _1, D_1)$
. Since
$\,f_0(D_0) = \chi (\mathcal {L}_n(\mu _0, D_0))$
and
$\,f_1(D_1) = \chi (\mathcal {L}_n(\mu _1, D_1))$
, then
$\,f_0(D_0) = f_1(D_1)$
. Thus
$\,f_0 {\upharpoonright } [E_0]^n$
and
$\,f_1 {\upharpoonright } [E_1]^n$
have the same function graph. It follows that
$E_1\, f_1$
-meets P, so
$H_1\, f_1$
-meets P. Contradiction.⊣
Theorem 2.31. Let W be a collection of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
patterns such that
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \not \leq _{id} {\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
. Then for every left-c.e. function
$\mu : \omega \to \omega $
, there is an
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
-instance such that every solution computes a function dominating
$\mu $
.
Proof. Since
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \not \leq _{id} {\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
, there is a coloring
$\,f_{\textit{fail}} : [\omega ]^n \to k$
and a
${\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution
$H_{\textit{fail}}$
to
$\,f_{\textit{fail}}$
witnessed by a strongly increasing relative left-c.e. function
$\mu _{\textit{fail}}$
and a coloring
$\chi : \mathcal {L}_n \to k$
, such that
$H_{\textit{fail}}$
is strongly
$\mu _{\textit{fail}}$
-transitive, and such that
$H_{\textit{fail}}$
meets some
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-pattern
$P \in W$
.
Let
$\mu : \omega \to \omega $
be a left-c.e. function. By Lemma 2.24, there is a strongly increasing left-c.e. function
$g : \omega \to \omega $
dominating
$\mu $
. Let
$\,f : [X]^n \to k$
be an instance of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
defined by
$\,f(D) = \chi (\mathcal {L}_n(g, D))$
. We claim that every
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
-solution
$H \subseteq X$
to f computes a function dominating g, hence dominating
$\mu $
. Fix H and suppose for the contradiction that H does not compute a function dominating g. By Cholak and Patey [Reference Cholak and Patey4, theorem 5.11] and Lemma 2.26, there is an infinite strongly g-transitive subset
$H_1 \subseteq H$
such that
$H_1$
does not compute a function dominating g. In particular,
$H_1$
is an infinite
${\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution to f with witnesses
$\chi $
and g, and such that
$H_1\, f$
-avoids P. By Lemma 2.30, H computes a function dominating g, contradiction.⊣
Theorem 2.32. A problem
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
admits strong cone avoidance if and only if
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \leq _{id} {\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
.
Proof.
$\Leftarrow $
: Suppose
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \leq _{id} {\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
. Fix a set Z, a non-Z-computable set C and a coloring
$\,f : [\omega ]^n \to k$
. By Theorem 2.29, there is an
${\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution H to f such that
$C \not \leq _T Z \oplus H$
. In particular, H is an
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
-solution to f.
$\Rightarrow $
: Suppose
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \not \leq _{id} {\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
. Let
$\mu : \omega \to \omega $
be a left-c.e. modulus of
$\emptyset '$
. By Theorem 2.31, there is a
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
-instance such that every solution computes a function dominating
$\mu $
, hence computes
$\emptyset '$
. Therefore
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
does not admit strong cone avoidance.⊣
Interestingly, Theorem 2.32 admits multiple abstract consequences of which one might expect to have a more direct proof. However, there does not seem to be any simpler proof of these facts than proving Theorem 2.32.
The following corollary states that the question of strong cone avoidance of a collection of patterns can be reduced to strong cone avoidance of each pattern individually.
Corollary 2.33. If
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(\{P\})$
admits strong cone avoidance for every
$P \in W$
, then
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
admits strong cone avoidance.
Proof. If
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(\{P\})$
admits strong cone avoidance for every
$P \in W$
, then by Theorem 2.32,
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(\{P\}) \leq _{id} {\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
for every
$P \in W$
. It follows that
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \leq _{id} {\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
, so again by Theorem 2.32,
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
admits strong cone avoidance.⊣
The following corollary gives an external definition of the maximal Ramsey-like problem which admits strong cone avoidance.
Corollary 2.34. Let
$W_{n,k} = \bigcup \{W : {\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \mbox { admits strong cone avoidance}\}$
. Then
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W_{n,k})$
admits strong cone avoidance.
Proof. By Corollary 2.33, it suffices to prove that
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(\{P\})$
admits strong cone avoidance for every
$P \in W_{n,k}$
. Fix some
$P \in W_{n,k}$
. By definition,
$P \in W$
for some collection W such that
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
admits strong cone avoidance. In particular,
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(\{P\})$
admits strong cone avoidance.⊣
2.4 Avoiding noncomputable cones
As explained in §1.2, there is a deep relation between the combinatorial features of the colorings over
$[\omega ]^n$
and the computational features the colorings over
$[\omega ]^{n+1}$
. This link is formalized in the case of cone avoidance by Cholak and Patey in [Reference Cholak and Patey4, theorem 1.5]. We prove the existence of a maximal Ramsey-like principle which admits cone avoidance. For this, we must restrict ourselves to a particular type of largeness graphs, namely, packed graphs.
Definition 2.35 (Cholak and Patey [Reference Cholak and Patey4])
A largeness graph
$\mathcal {G} = (\{0, \dots, n-1\}, E)$
is packed if for every
$i < n-2$
,
$\{i,i+1\} \not \in E$
.
Let
$\mathcal {P}_n$
be the set of all packed largeness graphs of size n. The definition of
$\mathcal {L}_n(\mu, D)$
, and more precisely the adjacent edges, codes some
$\mu $
-largeness information. However, in a computable setting, we only have access to the left-c.e. approximations of
$\mu $
. This is why we must restrict ourselves to
$\mu $
-largeness approximations
$\mathcal {P}_n(\mu, D)$
, which can be computably coded.
Definition 2.36. Given a relative left-c.e. function
$\mu : \omega \to \omega ^{+}$
with approximations
$\mu _0, \mu _1, \dots $
and a set
$D = \{x_0, \dots, x_{n-1}\} \subseteq \omega $
, let
$\mathcal {P}_n(\mu, D)$
be the graph
$(\{0, \dots, n-1\}, E)$
where
$E = \{ \{p, q\} : \mu _{x_q}(x_p)> x_{p+1} \wedge p+1 < q < n \}$
.
The following two lemmas are obtained by the exact same proof as Lemmas 2.23 and 2.25, respectively.
Lemma 2.37. Fix a strongly increasing relative left-c.e. function
$\mu : \omega \to \omega ^{+}$
. For every
$n \geq 1$
and
$D \in [\omega ]^n$
,
$\mathcal {P}_n(\mu, D) \in \mathcal {P}_n$
.
Lemma 2.38. Fix
$\mu : \omega \to \omega ^{+}$
and
$\rho : \omega \to \omega ^{+}$
. Given
$n \geq 1$
, let
$E = \{x_0 < \dots < x_{n-1} \}$
be a strongly
$\mu $
-transitive set, and
$F = \{y_0 < \dots < y_{n-1} \}$
be a strongly
$\rho $
-transitive set such that
$\mathcal {P}_n(\mu, E) = \mathcal {P}_n(\rho, F)$
. Then for every
$i < j < k < n$
,
$[x_i, x_j]$
is
$\mu _k$
-large if and only if
$[y_i, y_j]$
is
$\rho _k$
-large.
A coloring
$\,f : [\omega ]^{n+1} \to k$
is stable if for every
$D \in [\omega ]^n$
,
$\lim _y f(D \cup \{y\})$
exists. Given a set
$D = \{x_0 < \dots < x_{n-1}\}$
, if we take some
$y \in \omega $
sufficiently large, then
$\mu _y$
and
$\mu $
will coincide over
$[D]^2$
. Then, looking at the packed largeness graph
$\mathcal {P}_{n+1}(\mu, D \cup \{y\})$
, this graph codes exactly the information of the packed largeness graph
$\mathcal {P}_n(\mu, D)$
and the
$\mu _y$
-largeness information over
$[D]^2$
, which is by assumption the
$\mu $
-largeness information over
$[D]^2$
. These two kinds of information are exactly the ones coded by
$\mathcal {L}_n(\mu, D)$
. Then,
$\mathcal {P}_{n+1}(\mu, D \cup \{y\})$
and
$\mathcal {L}_n(\mu, D)$
are in one-to-one correspondence.
Let us define explicitly the one-to-one mapping. Given a packed largeness graph
$\mathcal {G} = (\{0, \dots, n\}, E)$
of size
$n+1$
, let
$\mathcal {L}_n(\mathcal {G})$
be the largeness graph of size
$n (\{0, \dots, n-1\}, E_1)$
where
$E_1 = \{\{i, j\} \in E : j < n\} \cup \{\{i,i+1\} : \{i, n\} \not \in E\}$
. The following lemma uses this one-to-one correspondence to relate stable colorings over
$[\omega ]^{n+1}$
to colorings over
$[\omega ]^n$
.
Lemma 2.39. Let
$\mu : \omega \to \omega ^{+}$
be a strongly increasing relative left-c.e. function. Fix
$n \geq 1$
and define
$\,f_{n+1} : D \mapsto \mathcal {P}_{n+1}(\mu, D)$
. Let H be an infinite strongly
$\mu $
-transitive set over which
$\,f_{n+1}$
is stable. For every
$D \in [H]^n$
, letting
$\mathcal {G} = \lim _{y \in H} \mathcal {P}_{n+1}(\mu, D \cup \{y\})$
,
$\mathcal {L}_n(\mu, D) = \mathcal {L}_n(\mathcal {G})$
.
Proof. Fix
$D = \{x_0 < \dots < x_{n-1}\} \in [H]^n$
, and let
$x_n \in H$
be sufficiently large so that
$\mathcal {P}_{n+1}(\mu, D \cup \{x_n\}) = \lim _{y \in H} \mathcal {P}_{n+1}(\mu, D \cup \{y\})$
. Let
$\mathcal {G} = (\{0, \dots, n\}, E)$
be the packed largeness graph
$\mathcal {P}_{n+1}(\mu, D \cup \{x_n\})$
and
$(\{0, \dots, n-1\}, E_1) = \mathcal {L}_n(\mathcal {G})$
. We first prove that the adjacent edges in
$\mathcal {L}_n(\mathcal {G})$
are exactly the adjacent edges in
$\mathcal {L}_n(\mu, D)$
. For every
$i < n-1$
, by definition of
$\mathcal {L}_n(\mathcal {G})$
,
$\{i, i+1\} \in E_1$
if and only if
$\{i, n\} \not \in E$
. By definition of
$\mathcal {P}_{n+1}(\mu, D \cup \{x_n\})$
,
$\{i, n\} \not \in E$
if and only if
$[x_i, x_{i+1}]$
is
$\mu _y$
-large, hence if and only if
$[x_i, x_{i+1}]$
is
$\mu $
-large. We now prove that the nonadjacent adjacent edges in
$\mathcal {L}_n(\mathcal {G})$
are exactly the nonadjacent edges in
$\mathcal {L}_n(\mu, D)$
. For every
$i +1 < j < n$
,
$\{i,j\} \in E_1$
if and only if
$\{i, j\} \in E$
, hence if and only if
$[x_i, x_{i+1}]$
is
$\mu _{x_j}$
-large. Therefore
$\mathcal {L}_n(\mathcal {G}) = \mathcal {L}_n(\mu, D)$
.⊣
Theorem 2.40. Let
$\mu : \omega \to \omega $
be a strongly increasing left-c.e. function. For every
$n \geq 1$
, define
$\,f_n : D \mapsto \mathcal {P}_n(\mu, D)$
. For every infinite set
$H \subseteq \omega $
such that
$\mathcal {P}_n \not \subseteq f_n[H]^n$
, H computes a function dominating
$\mu $
.
Proof. Fix
$\mu $
,
$n \geq 1$
and H. For
$n = 1$
, then
$|\mathcal {P}_1| = 1$
. For every infinite set
$H \subseteq \omega $
,
$|f_1[H]^1| = 1$
, so
$\mathcal {P}_1 \subseteq f_1[H]^1$
, and the property vacuously holds. For
$n> 1$
. Suppose for the contradiction that H does not compute a function dominating
$\mu $
. By Patey [Reference Patey25, theorem 12], there is an infinite subset
$H_1 \subseteq H$
over which
$\,f_n$
is stable and such that
$H_1$
does not compute a function dominating
$\mu $
. Let
$\tilde {f} : [\omega ]^{n-1} \to \mathcal {P}_n$
be defined by
$\tilde {f}(D) = \lim _{y \in H_1}f_n(D \cup \{y\}) = \lim _{y \in H_1} \mathcal {P}_n(\mu, \cup \{y\})$
. By Lemma 2.39, for every
$D \in [H_1]^{n-1}$
,
$\mathcal {L}_{n-1}(\mu, D) = \mathcal {L}_n(\tilde {f}(D))$
.
By Lemma 2.37,
$\,f_n[H_1]^n \subseteq \mathcal {P}_n$
. By Cholak and Patey [Reference Cholak and Patey4, Lemmas 3.15 and 3.16],
$|\mathcal {P}_n| = C_{n-1}$
. Since
$\mathcal {P}_n \not \subseteq f_n[H]^n$
, then
$|f_n[H]^n| < C_{n-1}$
. It follows that, letting
$g_{n-1} : D \mapsto \mathcal {L}_{n-1}(\mu, D)$
,
$|g_{n-1}[H]^{n-1}| = |f_n[H]^n| < C_{n-1}$
. By Cholak and Patey [Reference Cholak and Patey4, Lemma 3.16],
$|\mathcal {L}-{n-1}| = C_{n-1}$
, therefore,
$\mathcal {L}_{n-1} \not \subseteq g_{n-1}[H]^{n-1}$
, so by Theorem 2.27,
$H_1$
computes a function dominating
$\mu $
. Contradiction.⊣
Statement 2.41.
${\mathsf {CA}}\mbox {-}{\mathsf {RT}}^n_k$
: For every function
$\,f : [\omega ]^n \to k$
, there is a strongly increasing relative left-c.e. function
$\mu : \omega \to \omega ^{+}$
, an infinite strongly
$\mu $
-transitive set
$H \subseteq \omega $
and a coloring
$\chi : \mathcal {P}_n \to k$
such that for every
$D \in [H]^n$
,
$\,f(D) = \chi (\mathcal {P}_n(\mu, D))$
.
In the cases
$n = 1$
and
$n = 2$
, there is exactly one packed largeness graph of size n, namely, the graph with no edges. Therefore
$|\mathcal {P}_n| = 1$
, and
${\mathsf {CA}}\mbox {-}{\mathsf {RT}}^1_k$
and
${\mathsf {CA}}\mbox {-}{\mathsf {RT}}^2_k$
are exactly
${\operatorname {\mathrm {{\mathsf {RT}}}}}^1_k$
and
${\operatorname {\mathrm {{\mathsf {RT}}}}}^2_k$
, respectively. The case
$n = 3$
yields a new principle.
Statement 2.42.
${\mathsf {PACKED}}_k$
: “For every coloring
$\,f : [\omega ]^3 \to k$
, there are two colors
$i_s,i_\ell < k$
and an infinite set
$H \subseteq \omega $
such that
$\,f[H]^3 \subseteq \{i_s,i_\ell \}$
and for every
$w < x < y < z \in H$
,
-
(a)
$\,f(w, x, z) = f(x, y, z) = i_s$
if and only if
$\,f(w, y, z) = i_s$
, -
(b) if
$\,f(w, x, y) = i_s$
then
$\,f(w, x, z) = i_s$
, -
(c) if
$\,f(w, x, y) = i_\ell $
and
$\,f(w, x, z) = i_s$
then
$\,f(x, y, z) = i_s$
.”
Informally,
$\,f(x, y, z) = i_s$
if
$[x, y]$
is
$\mu _z$
-small, and
$\,f(x, y, z) = i_\ell $
otherwise. We now prove that
${\mathsf {CA}}\mbox {-}{\mathsf {RT}}^3_k$
and
${\mathsf {PACKED}}_k$
are the same statement by bi-reduction.
Lemma 2.43.
${\mathsf {PACKED}}_k \leq _{id} {\mathsf {CA}}\mbox {-}{\mathsf {RT}}^3_k$
.
Proof. Let
$\,f : [\omega ]^3 \to k$
be a coloring, and let H be an infinite
${\mathsf {CA}}\mbox {-}{\mathsf {RT}}^3_k$
-solution to f. By definition of
${\mathsf {CA}}\mbox {-}{\mathsf {RT}}^3_k$
, there is a strongly increasing relative left-c.e. modulus
$\mu : \omega \to \omega ^{+}$
and a function
$\chi : \mathcal {P}_3 \to k$
such that H is strongly
$\mu $
-transitive, and for every
$D \in [H]^3$
,
$\,f(D) = \chi (\mathcal {P}_3(\mu,D))$
. Let
$\mathcal {G}_0 = (\{0,1,2\}, \emptyset )$
and
$\mathcal {G}_1 = (\{0,1,2\}, \{\{0,2\}\})$
. In particular,
$\mathcal {P}_3 = \{\mathcal {G}_0, \mathcal {G}_1\}$
. Let
$i_s = \chi (\mathcal {G}_1)$
and
$i_\ell = \chi (\mathcal {G}_0)$
. We have
$\,f[H]^3 \subseteq \{i_s, i_\ell \}$
. If
$i_s = i_\ell $
, then H is f-homogeneous, and H is an
${\mathsf {PACKED}}_k$
-solution to f, so suppose
$i_s \neq i_\ell $
. In particular,
$\chi $
is one-to-one. We now prove properties (a-c) of Statement 2.42. Fix
$w < x < y < z \in H$
.
(a):
$\,f(w, x, z) = f(x, y, z) = i_s$
if and only if
$\chi (\mathcal {P}_3(\mu, \{w, x, z\})) = \chi (\mathcal {P}_3(\mu, \{x, y, z\})) = i_s$
if and only if
$\mathcal {P}_3(\mu, \{w, x, z\}) = \mathcal {P}_3(\mu, \{x, y, z\}) = \mathcal {G}_1$
if and only if
$[w, x]$
and
$[x, y]$
are
$\mu _z$
-small. Since H is strongly
$\mu $
-transitive, this holds if and only if
$[w, y]$
is
$\mu _z$
-small, if and only if
$\mathcal {P}_3(\mu, \{w, y, z\}) = \mathcal {G}_1$
if and only if
$\,f(w, y, z) = \chi (\mathcal {P}_3(\mu, \{w, y, z\})) = \chi (\mathcal {G}_1) = i_s$
.
(b): If
$\,f(w, x, y) = i_s$
, then
$\chi (\mathcal {P}_3(\mu, \{w, x, y\})) = i_s$
, so
$\mathcal {P}_3(\mu, \{w, x, y\}) = \mathcal {G}_1$
. In particular,
$[w, x]$
is
$\mu _y$
-small, hence is
$\mu _z$
-small. Therefore,
$\mathcal {P}_3(\mu, \{w, x, z\}) = \mathcal {G}_1$
, so
$\,f(w, x, z) = \chi (\mathcal {P}_3(\mu, \{w, x, z\})) = \chi (\mathcal {G}_1) = i_s$
.
(c): If
$\,f(w, x, y) = i_\ell $
and
$\,f(w, x, z) = i_s$
, then
$\chi (\mathcal {P}_3(\mu, \{w, x, y\})) = i_\ell $
and
$\chi (\mathcal {P}_3(\mu, \{w, x, z\})) = i_s$
. Therefore,
$\mathcal {P}_3(\mu, \{w, x, y\}) = \mathcal {G}_0$
and
$\mathcal {P}_3(\mu, \{w, x, z\}) = \mathcal {G}_1$
. It follows that
$[w, x]$
is
$\mu _y$
-large but
$\mu _z$
-small. By Claim 1 in the proof of Lemma 2.23, since
$\mu $
is strongly increasing,
$[x, y]$
is
$\mu _z$
-small. Thus
$\mathcal {P}_3(\mu, \{x, y, z\}) = \mathcal {G}_1$
, so
$\,f(x, y, z) = \chi (\mathcal {P}_3(\mu, \{x, y, z\})) = \chi (\mathcal {G}_1) = i_s$
.⊣
Lemma 2.44.
${\mathsf {CA}}\mbox {-}{\mathsf {RT}}^3_k \leq _{id} {\mathsf {PACKED}}_k$
.
Proof. Let
$\,f : [\omega ]^3 \to k$
be a coloring, and let H be an infinite
${\mathsf {PACKED}}_k$
-solution, that is, there are some colors
$i_s, i_\ell < k$
such that
$\,f[H]^3 \subseteq \{i_s, i_\ell \}$
and properties (a-c) of Statement 2.42 hold. For every
$x, z \in \omega $
, let
$x_0$
and
$z_0$
be the least elements of
$H \cap [x, \infty )$
and
$H \cap [z, \infty )$
, respectively. Let
$\mu _z(x)$
be the least element
$y_0$
of
$H \cap (x_0, z_0)$
such that
$\,f(x_0, y_0, z_0) = i_\ell $
if it exists. Otherwise
$\mu _z(x) = z$
.
Claim 1: For every
$x, z \in \omega $
,
$\mu _z(x) \leq z$
. Indeed, let
$x_0$
and
$z_0$
be the least elements of
$H \cap [x, \infty )$
and
$H \cap [z, \infty )$
, respectively. If there is a least element
$y_0$
of
$H \cap (x_0, z_0)$
such that
$\,f(x_0, y_0, z_0) = i_\ell $
, then
$y_0 < z_0$
and by definition of
$z_0$
,
$y_0 < z$
. It follows that
$\mu _z(x) = y_0 < z$
. If there is no such
$y_0$
, then
$\mu _z(x) = z \leq z$
. This proves Claim 1.
Claim 2: For every
$x \in \omega $
and
$u \leq v \in \omega $
,
$\mu _u(x) \leq \mu _v(x)$
. Let
$x_0$
,
$u_0$
and
$v_0$
be the least elements of
$H \cap [x, \infty )$
,
$H \cap [u, \infty )$
and
$H \cap [v, \infty )$
, respectively. In particular,
$u_0 \leq v_0$
. Case 1: there is no
$y_u \in H \cap (x_0, u_0)$
such that
$\,f(x_0, y_u, u_0) = i_\ell $
. Then
$\mu _u(x) = u$
. If there is no
$y_v \in H \cap (x_0, v_0)$
such that
$\,f(x_0, y_v, v_0) = i_\ell $
, then
$\mu _v(x) = v \geq u = \mu _u(x)$
, and we are done. So suppose there is such a
$y_v \in H \cap (x_0, v_0)$
. If
$y_v \geq u_0$
, then
$\mu _v(x) = y_v \geq u_0 \geq u = \mu _u(u)$
and we are done. If
$y_v < u_0$
, then
$\,f(x_0, y_v, v_0) = i_\ell $
and since
$y_u$
does not exist,
$\,f(x_0, y_v, u_0) = i_s$
. This contradicts property (b) of Statement 2.42. Case 2:
$y_u$
exists. Then
$y_u < u_0$
, so
$y_u < u$
and for every
$y \in H \cap (x_0, y_u)$
,
$\,f(x_0, y, u_0) = i_s$
. By property (b) of Statement 2.42, for every
$y \in H \cap (x_0, y_u)$
,
$\,f(x_0, y, v_0) = i_s$
. Therefore if
$y_v$
exists, then
$y_v \geq y_u$
and
$\mu _u(x) \leq \mu _v(x)$
. If
$y_v$
does not exist, then
$\mu _v(x) = v \geq u> y_u = \mu _u(x)$
. This proves Claim 2.
Claim 3: For every
$z \in \omega $
and
$u \leq v$
,
$\mu _z(u) \leq \mu _z(v)$
. Let
$u_0, v_0$
and
$z_0$
be the least elements of
$H \cap [u, \infty )$
,
$H \cap [v, \infty )$
and
$H \cap [z, \infty )$
, respectively. In particular,
$u_0 \leq v_0$
. Case 1: there is no
$y_v \in H \cap (v_0, z_0)$
such that
$\,f(v_0, y_v, z_0) = i_\ell $
. Then
$\mu _v(x) = v$
. Since by Claim 1,
$\mu _u(x) \leq u \leq v = \mu _v(x)$
, we are done. Case 2: there is such a
$y_v$
. In particular,
$\,f(v_0, y_v, z_0) = i_\ell $
. By property (a) of Statement 2.42,
$\,f(u_0, y_v, z_0) = i_\ell $
, so there is a least
$y_u \in H \cap (u_0, z_0)$
such that
$\,f(u_0, y_u, z_0) = i_\ell $
and
$y_u \leq y_v$
. Then
$\mu _z(u) = y_u \leq y_v = \mu _z(v)$
. This proves Claim 3.
Claim 4: For every
$z \in \omega $
and
$u < v \in \omega $
, if
$\mu _{z+1}(u)> \mu _z(u)$
, then
$\mu _{z+1}(v)> z$
. Let
$z_0, z_1, u_0, v_0$
be the least elements of
$H \cap [z, \infty )$
,
$H \cap [z+1, \infty )$
,
$H \cap [u, \infty )$
and
$H \cap [v, \infty )$
, respectively. If
$z_0 = z_1$
, we are done, so suppose
$z_0 < z_1$
. In particular,
$z_1$
is the immediate successor of
$z_0$
in H. If there is no least
$y_v \in H \cap (v_0, z_1)$
such that
$\,f(v_0, y_v, z_1) = i_\ell $
, then
$\mu _{z+1}(v) = z+1$
and we are done as well. So suppose there is such a
$y_v$
. By property (a) of Statement 2.42,
$\,f(u_0, y_v, z_1) = i_\ell $
, so there is a least
$y_u \in H \cap (u_0, z_1)$
such that
$\,f(u_0, y_u, z_1) = i_\ell $
. Since
$z_1$
is the immediate successor of
$z_0$
in H, either
$y_u = z_0$
, or
$y_u < z_0$
. Case 1:
$y_u = z_0$
. By Claim 3,
$\mu _{z+1}(v) \geq \mu _{z+1}(u) = y_u = z_0$
. If
$z_0> z$
, we are done, so suppose
$y_u = z_0 = z$
. If
$\mu _z(u) = z$
, then Claim 4 is vacuously satisfied, so suppose
$\mu _z(u) < z$
. It follows that there is a least
$y \in H \cap (u_0, z_0)$
such that
$\,f(u_0, y, z_0) = i_\ell $
. By minimality of
$y_0$
,
$\,f(u_0, y, z_1) = i_s$
. Then by property (c) of Statement 2.42,
$\,f(y, z_0, z_1) = i_s$
. Since
$\,f(u_0, y_u, z_1) = i_\ell $
, and
$y_u = z_0 = z$
, then
$\,f(y, z, z_1) = i_s$
and
$\,f(u_0, z, z_1) = i_\ell $
. So by property (a) of Statement 2.42,
$\,f(u_0, y, z_1) = i_\ell $
, contradiction. Case 2:
$y_u < z_0$
. Then there is some some
$y \in H \cap (u_0, z_0)$
such that
$\,f(u_0, y, z_0) = i_\ell $
, with
$y < y_u$
. By definition of
$y_u$
being a least element,
$\,f(u_0, y, z_1) = i_s$
. Then by property (c) of Statement 2.42,
$\,f(y, z_0, z_1) = i_s$
, and since
$y < y_u < z_0$
, and
$\,f(u_0, y_u, z_1) = i_\ell $
, then by property (a) of Statement 2.42,
$\,f(u_0, y, z_1) = i_\ell $
or
$\,f(y, y_u, z_1) = i_\ell $
. The former case does not hold, so
$\,f(y, y_u, z_1) = i_\ell $
. Again by property (a) of Statement 2.42,
$\,f(y, z_0, z_1) = i_\ell $
. Contradiction.
Claim 5: For
$w < x < y < z \in H$
such that
$\mu _z(w)> x$
and
$\mu _z(x)> y$
, then
$\mu _z(w)> y$
. By definition of
$\mu $
,
$\,f(w, x, z) = f(x, y, z) = i_s$
. By property (a) of Statement 2.42,
$\,f(w, y, z) = i_s$
. Therefore,
$\mu _z(w)> y$
. This proves Claim 5.
By Claim 2, 3 and 4,
$\mu $
is a strongly increasing left-c.e. function. Moreover, for every
$x < y < z \in H$
,
$\,f(x, y, z) = i_\ell $
if and only if
$\mu _z(x) \leq y$
, so
$\,f(x, y, z) = \chi (\mathcal {P}_3(\mu, \{x, y, z\}))$
. By Claim 5, H is strongly
$\mu $
-transitive. Therefore H is a
${\mathsf {CA}}\mbox {-}{\mathsf {RT}}^3_k$
-solution to f with witnesses
$\chi $
and
$\mu $
.⊣
Theorem 2.45.
${\mathsf {CA}}\mbox {-}{\mathsf {RT}}^n_k$
admits cone avoidance.
Proof. Fix two sets Z and C with
$C \not \leq _T Z$
and let
$\,f : [\omega ]^n \to k$
be a Z-computable instance of
${\mathsf {CA}}\mbox {-}{\mathsf {RT}}^n_k$
.
By Lerman [Reference Lerman16, theorem 4.18], there is a set
$Z_1 \geq _T Z$
such that C is
$\Delta ^0_2(Z_1)$
but
$C \not \leq _T Z_1$
. Since C is
$\Delta ^0_2(Z_1)$
, there is a left
$Z_1$
-c.e. modulus
$\mu : \omega \to \omega $
for C. By Lemma 2.24, we can assume that
$\mu $
is strongly increasing.
Let
$\,f_1 : [\omega ]^n \to k \times \mathcal {P}_n$
be defined for each
$D \in [\omega ]^n$
by
$\,f_1(D) = \langle f(D), \mathcal {P}_n(\mu, D) \rangle $
. By cone avoidance of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_{<\infty, C_{n-1}}$
(Cholak and Patey [Reference Cholak and Patey4, corollary 4.19]), there is an infinite set
$H \subseteq \omega $
such that
$C \not \leq _T Z_1 \oplus H$
and
$|f_1[H]^n| \leq C_{n-1}$
. In particular,
$Z_1 \oplus H$
does not compute a function dominating
$\mu $
, so by Theorem 2.27, for every
$\mathcal {G} \in \mathcal {P}_n$
, there is some
$i < k$
and some
$D \in [H]^n$
such that
$\,f_1(D) = \langle i, \mathcal {G} \rangle $
. Since
$|\mathcal {P}_n| = C_{n-1}$
(Cholak and Patey [Reference Cholak and Patey4, Lemma 3.15 and 3.16]), this i is unique. For each
$\mathcal {G}$
, let
$\chi (\mathcal {G})$
be such an i.
We claim that for every
$D \in [H]^n$
,
$\,f(D) = \chi (\mathcal {P}_n(\mu, D))$
. By definition of
$\chi $
,
$\,f_1(D) = \langle f(D), \mathcal {P}_n(\mu, D)\rangle = \langle \chi (\mathcal {P}_n(\mu, D)), \mathcal {P}_n(\mu, D) \rangle $
. It follows that
$\,f(D) = \chi (\mathcal {P}_n(\mu, D))$
. By Cholak and Patey [Reference Cholak and Patey4, corollary 5.5], there is an infinite
$\mu $
-transitive subset
$H_1 \subseteq H$
such that
$C \not \leq _T Z \oplus H_1$
. By Lemma 2.26, there is an infinite strongly
$\mu $
-transitive subset
$H_2 \subseteq H_1$
such that
$C \not \leq _T Z \oplus H_2$
. Therefore,
$H_2$
is a
${\mathsf {CA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution to f.⊣
The following technical lemma will be useful for Theorem 2.47, Lemma 3.13 and Lemma 3.14.
Lemma 2.46. Fix
$\chi : \mathcal {P}_n \to k$
, and let
$\,f_0 : [\omega ]^n \to k$
and
$\,f_1 : [\omega ]^n \to k$
be two colorings such that
$\,f_1$
is computable. Let
$H_0$
be an infinite
${\mathsf {CA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution to
$\,f_0$
with witnesses
$\chi $
and
$\mu _0 : \omega \to \omega $
, and let
$H_1$
be an infinite
${\mathsf {CA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution to
$\,f_1$
with witnesses
$\chi $
and
$\mu _1 : \omega \to \omega $
. If
$H_0\, f_0$
-meets some
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-pattern P but
$H_1\, f_1$
-avoids P and
$\mu _1$
is left-c.e., then
$H_1$
computes a function dominating
$\mu _1$
.
Proof. Since
$H_0\, f_0$
-meets some
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-pattern P, there is a finite set
$E_0 = \{x_0 < \dots < x_{r-1} \} \subseteq H_0$
which
$\,f_0$
-meets P. Suppose for the sake of contradiction that
$H_1$
does not compute a function dominating
$\mu _1$
. By Theorem 2.40, there is a finite set
$E_1 = \{y_0 < \dots < y_{r-1}\} \subseteq H_1$
of size r such that
$\mathcal {P}_r(\mu _0, E_0) = \mathcal {P}_r(\mu _1, E_1)$
. By Lemma 2.38, since
$H_0$
is strongly
$\mu _0$
-transitive and
$H_1$
is strongly
$\mu _1$
-transitive, for every
$I \in [r]^n$
, letting
$D_0 = \{x_i : i \in I\}$
and
$D_1 = \{y_i : i \in I\}$
,
$\mathcal {P}_n(\mu _0, D_0) = \mathcal {P}_n(\mu _1, D_1)$
. Since
$\,f_0(D_0) = \chi (\mathcal {P}_n(\mu _0, D_0))$
and
$\,f_1(D_1) = \chi (\mathcal {P}_n(\mu _1, D_1))$
, then
$\,f_0(D_0) = f_1(D_1)$
. Thus
$\,f_0 {\upharpoonright } [E_0]^n$
and
$\,f_1 {\upharpoonright } [E_1]^n$
have the same function graph. It follows that
$E_1\, f_1$
-meets P, so
$H_1\, f_1$
-meets P. Contradiction.⊣
Theorem 2.47. Let W be a collection of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-patterns such that
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \not \leq _{id} {\mathsf {CA}}\mbox {-}{\mathsf {RT}}^n_k$
. Then for every left-c.e. function
$\mu : \omega \to \omega $
, there is a computable
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
-instance such that every solution computes a function dominating
$\mu $
.
Proof. Since
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \not \leq _{id} {\mathsf {CA}}\mbox {-}{\mathsf {RT}}^n_k$
, there is a coloring
$\,f_{\textit{fail}} : [\omega ]^n \to k$
and a
${\mathsf {CA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution
$H_{\textit{fail}}$
to
$\,f_{\textit{fail}}$
witnessed by strongly increasing left-c.e. function
$\mu _{\textit{fail}} : \omega \to \omega ^{+}$
and a coloring
$\chi : \mathcal {P}_n \to k$
, such that
$H_{\textit{fail}}$
is strongly
$\mu _{\textit{fail}}$
-transitive, and
$H_{\textit{fail}}$
meets some
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-pattern
$P \in W$
.
Let
$\mu : \omega \to \omega $
be a left-c.e. function. By Lemma 2.24, there is a strongly increasing left-c.e. function
$g : \omega \to \omega $
dominating
$\mu $
. Let
$\,f : [X]^n \to k$
be a computable instance of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
defined by
$\,f(D) = \chi (\mathcal {P}_n(g, D))$
. We claim that every
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
-solution H to f computes a function dominating g, hence dominating
$\mu $
. Fix H and suppose for the contradiction that H does not compute a function dominating g. By Cholak and Patey [Reference Cholak and Patey4, theorem 5.11] and Lemma 2.26, there is an infinite strongly g-transitive subset
$H_1 \subseteq H$
such that
$H_1$
does not compute a function dominating g. In particular,
$H_1$
is an infinite
${\mathsf {CA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution to f with witnesses
$\chi $
and g, and such that
$H_1\, f$
-avoids P. By Lemma 2.46, H computes a function dominating g, contradiction.⊣
Theorem 2.48. A problem
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
admits cone avoidance if and only if
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \leq _{id} {\mathsf {CA}}\mbox {-}{\mathsf {RT}}^n_k$
.
Proof.
$\Leftarrow $
: Suppose
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \leq _{id} {\mathsf {CA}}\mbox {-}{\mathsf {RT}}^n_k$
. Fix a set Z, a non-Z-computable set C and a Z-computable coloring
$\,f : [\omega ]^n \to k$
. By Theorem 2.45, there is a
${\mathsf {CA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution H to f such that
$C \not \leq _T Z \oplus H$
. In particular, H is an
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
-solution to f.
$\Rightarrow $
: Suppose
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \not \leq _{id} {\mathsf {CA}}\mbox {-}{\mathsf {RT}}^n_k$
. Let
$\mu : \omega \to \omega $
be a left-c.e. modulus of
$\emptyset '$
. By Theorem 2.47, there is a computable
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
-instance such that every solution computes a function dominating
$\mu $
, hence computes
$\emptyset '$
. Therefore
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
does not admit cone avoidance.⊣
3 Promise Ramsey-like theorems
The class of Ramsey-like problems encompasses Ramsey’s theorem and the
$\operatorname {\mathrm {{\mathsf {EM}}}}$
theorem [Reference Bovykin and Weiermann1] since both statements are of the form “For every coloring
$\,f : [\omega ]^n \to k$
, there is an infinite set H which avoids some set of patterns.” There are however two kinds of consequences of Ramsey’s theorem which do not fit within this framework.
First, some statements have a restricted class of instances. For example, the Ascending Descending Sequence [Reference Hirschfeldt and Shore14] (
$\operatorname {\mathrm {{\mathsf {ADS}}}}$
) principle asserts that every infinite linear order admits an infinite ascending or descending sequence. A linear order
$\mathcal {L} = (\omega, {\prec }_{\mathcal {L}})$
can be formalized as a coloring
$\,f : [\omega ]^2 \to 2$
such that for every
$x < y$
,
$\,f(x, y) = 1$
if and only if
$x {\prec }_{\mathcal {L}} y$
. Such a coloring is called transitive, since for every
$x < y < z$
and
$i < 2$
, if
$\,f(x, y) = i$
and
$\,f(y, z) = i$
then
$\,f(x, z) = i$
.
$\operatorname {\mathrm {{\mathsf {ADS}}}}$
can therefore be formulated as the statement “For every transitive coloring
$\,f : [\omega ]^2 \to 2$
, there exists an infinite f-homogeneous set.” The Chain AntiChain [Reference Hirschfeldt and Shore14] (
$\operatorname {\mathrm {{\mathsf {CAC}}}}$
) principle provides another example of a classical theorem studied in reverse mathematics, whose instances are subject to restrictions.
$\operatorname {\mathrm {{\mathsf {CAC}}}}$
asserts that every infinite partial order admits an infinite chain or an infinite antichain. Here, a partial order
$\mathcal {P} = (\omega, {\prec }_{\mathcal {P}})$
can be represented by a coloring
$\,f : [\omega ]^2 \to 3$
such that for every
$x < y$
,
$\,f(x, y)$
equals 0 if
$x \succ _{\mathcal {P}} y$
, 1 if
$x {\prec }_{\mathcal {P}} y$
and 2 if x and y are incomparable. Such a coloring is transitive for colors 0 and 1, but not 2.
Second, some consequences of Ramsey’s theorem such as the Free Set theorem [Reference Cholak, Giusto, Hirst and Jockusch2] involve
$\omega $
-colorings of
$[\omega ]^n$
. The free set theorem for n-tuples is the statement “For every coloring
$\,f : [\omega ]^n \to \omega $
, there is an infinite set H such that for every
$x \in H$
,
$x \not \in f[H \smallsetminus \{x\}]^n$
.” Suppose that for every
$D \in [\omega ]^n$
,
$\,f(D) \leq \min D$
. We can define a coloring
$g : [\omega ]^{n+1} \to 2$
by
$g(x_0, x_1, \dots, x_n) = 1$
if and only if
$\,f(x_1, \dots, x_n) = x_0$
. Every g-homogeneous set must be of color 0, and therefore be a free set solution to f. Note that by functionality of f, the coloring g enjoys some structural properties, in that for every
$x \in \omega $
, there is at most one
$D \in [\omega ]^n$
with
$x \leq \min D$
such that
$g(\{x\} \cup D) = 1$
. Then one can formulate this restricted version of the free set theorem as the statement “For every coloring
$g : [\omega ]^{n+1} \to 2$
such that for every
$x \in \omega $
, there is at most one
$D \in [\omega ]^n$
with
$x \leq \min D$
and such that
$g(\{x\} \cup D) = 1$
, there is an infinite g-homogeneous set.” The full free set theorem can also fit within this framework with additional technicalities.
In these three examples, the problems can be formulated as statements “For every coloring
$\,f : [\omega ]^n \to k$
which avoids some set of patterns, there is an infinite set H which avoids another set of patterns.” In computational complexity, problems whose class of instances is restricted by some properties are known as promise problems. This motivates the following definition.
Definition 3.1. Given two collections V and W of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-patterns, the promise
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-like problem
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V, W)$
is the problem whose instances are colorings
$\,f : [\omega ]^n \to k$
such that
$\omega\, f$
-avoids every pattern in V. An
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V,W)$
-solution to an instance f is an infinite set
$H \subseteq \omega\, f$
-avoiding every pattern in W.
For example,
$\operatorname {\mathrm {{\mathsf {ADS}}}}$
is the promise
${\operatorname {\mathrm {{\mathsf {RT}}}}}^2_2$
-like problem
${\operatorname {\mathrm {{\mathsf {RT}}}}}^2_2(W_{\operatorname {\mathrm {{\mathsf {ADS}}}}}, W_{{\operatorname {\mathrm {{\mathsf {RT}}}}}^2_2})$
with
$W_{\operatorname {\mathrm {{\mathsf {ADS}}}}} = \{ \mathtt {f}(x_0, x_1) = 1 \wedge \mathtt {f}(x_1, x_2) = 1 \wedge \mathtt {f}(x_0, x_2) = 0, \mathtt {f}(x_0, x_1) = 0 \wedge \mathtt {f}(x_1, x_2) = 0 \wedge \mathtt {f}(x_0, x_2) = 1 \}$
. We interpret a function
$\,f : [\omega ]^2 \to 2$
such that
$\omega\, f$
-avoids the pattern
$W_{\operatorname {\mathrm {{\mathsf {ADS}}}}}$
as a linear order
$\prec $
defined by
$x \prec y$
if and only if
$x <_{\mathbb {N}} y$
and
$\,f(x, y) = 1$
or
$x>_{\mathbb {N}} y$
and
$\,f(x, y) = 0$
.
Similarly,
$\operatorname {\mathrm {{\mathsf {CAC}}}}$
is the promise
${\operatorname {\mathrm {{\mathsf {RT}}}}}^2_3$
-like problem
${\operatorname {\mathrm {{\mathsf {RT}}}}}^2_3(W_{\operatorname {\mathrm {{\mathsf {CAC}}}}}, W_{{\operatorname {\mathrm {{\mathsf {RT}}}}}^2_2})$
with
$W_{\operatorname {\mathrm {{\mathsf {CAC}}}}} = W_{\operatorname {\mathrm {{\mathsf {ADS}}}}}$
. We interpret a function
$\,f : [\omega ]^2 \to 3$
such that
$\omega\, f$
-avoids the pattern
$W_{\operatorname {\mathrm {{\mathsf {ADS}}}}}$
as a partial order
$\prec $
defined by
$x \prec y$
if and only if
$x <_{\mathbb {N}} y$
and
$\,f(x, y) = 1$
or
$x>_{\mathbb {N}} y$
and
$\,f(x, y) = 0$
.
3.1 Strongly avoiding nonarithmetical cones
We now extend our analysis of strong cone avoidance for nonarithmetical cones to the class of promise Ramsey-like problems. For this, we need to define a restricted version of
${\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
, in which the coloring
$\chi : \mathcal {V}_n \to k$
must belong to a predefined set of colorings.
Statement 3.2. Let
$\mathcal {R}$
be a set of functions of type
$\chi : \mathcal {V}_n \to k$
.
$\mathcal {R}\mbox {-}{\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
: For every function
$\,f : [\omega ]^n \to k$
, there is a function
$\mu : \omega \to \omega ^{+}$
, an infinite
$\mu $
-transitive set
$H \subseteq \omega $
, and a coloring
$\chi \in \mathcal {R}$
such that for every
$D \in [H]^n$
,
$\,f(D) = \chi (\mathcal {V}_n(\mu, D))$
.
One particular case of interest is whenever
$\mathcal {R}$
is a singleton
$\{\chi \}$
. The following notion will be very useful in our case analysis. Given some
$n, k \in \omega $
and a collection W of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-patterns, let
$$\begin{align*}\mathcal{R}^n_k(W) = \left\{\chi : \mathcal{V}_n \to k \mbox{ }|\mbox{ } {\operatorname{\mathrm{{\mathsf{RT}}}}}^n_k(W) \leq_{id} \{\chi\}\mbox{-}{\mathsf{ARITH}}\mbox{-}{\mathsf{SCA}}\mbox{-}{\mathsf{RT}}^n_k\right\}\kern-1.5pt. \end{align*}$$
In particular, if
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
is a true statement, then every constant function
$\chi : \mathcal {V}_n \to k$
belongs to
$\mathcal {R}^n_k(W)$
.
Lemma 3.3. Let V and W be collections of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-patterns such that
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \leq _{id} \mathcal {R}^n_k(V)\mbox {-}{\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
. Then
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V, W)$
admits strong cone avoidance for nonarithmetical cones.
Proof. Fix a set Z, a non-Z-arithmetical set C and a coloring
$\,f : [\omega ]^n \to k$
.
Suppose first that C is not Z-hyperarithmetical. By Solovay [Reference Solovay28], C is not computably encodable relative to Z. Since for every infinite set
$X \subseteq \omega $
, there is an infinite
${\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution
$Y \subseteq X$
to f, there is an
${\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution H to f such that
$C \not \leq _T Z \oplus H$
.
Suppose now that C is Z-hyperarithmetical. By Groszek and Slaman [Reference Groszek and Slaman12], there is a modulus
$\mu : \omega \to \omega $
relative to Z, that is, for every function g dominating
$\mu $
,
$C \leq _T Z \oplus g$
. Let
$\,f_1$
be defined for each
$D \in [\omega ]^n$
by
$\,f_1(D) = \langle f(D), \mathcal {V}_n(\mu, D) \rangle $
. By strong cone avoidance of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_{<\infty, 2^{n-1}}$
for nonarithmetical cones (see Cholak and Patey [Reference Cholak and Patey4, theorem 4.15]), there is an infinite set H such that
$C \not \leq _T Z \oplus H$
and
$|f_1[H]^n| \leq 2^{n-1}$
. In particular,
$Z \oplus H$
does not compute a function dominating
$\mu $
, so by Theorem 2.10, for every
$\mathcal {G} \in \mathcal {V}_n$
, there is some
$i < k$
and some
$D \in [H]^n$
such that
$\,f_1(D) = \langle i, \mathcal {G} \rangle $
. Since
$|\mathcal {V}_n| = 2^{n-1}$
, this i is unique. For each
$\mathcal {G} \in \mathcal {V}_n$
, let
$\chi (\mathcal {G})$
be such an i. In particular, for every
$D \in [H]^n$
,
$\,f(D) = \chi (\mathcal {V}_n(\mu, D))$
. By Cholak and Patey [Reference Cholak and Patey4, corollary 5.5], there is an infinite
$\mu $
-transitive subset
$H_1 \subseteq H$
such that
$C \not \leq _T Z \oplus H_1$
. Therefore,
$H_1$
is a
${\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution to f.
If
$\chi \in \mathcal {R}^n_k(V)$
, then since
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \leq _{id} \mathcal {R}^n_k(V)\mbox {-}{\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
,
$H_2$
is an
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V, W)$
-solution to f, and we are done. So suppose
$\chi \not \in \mathcal {R}^n_k(V)$
. Unfolding the definition,
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V) \not \leq _{id} \{\chi \}\mbox {-}{\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
, so there is a coloring
$\,f_\chi : [\omega ]^n \to k$
and some infinite
${\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution
$H_\chi $
to
$\,f_\chi $
with witnesses
$\mu _\chi : \omega \to \omega ^{+}$
and
$\chi : \mathcal {V}_n \to k$
, that meets some
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-pattern
$P_\chi \in V$
.
However,
$H_2\, f$
-avoids
$P_\chi $
since f is an instance of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V, W)$
. By Lemma 2.17,
$H_2 \oplus Z$
computes a function dominating
$\mu $
, hence
$C \leq _T Z \oplus H_2$
, contradiction. This completes the proof of Lemma 3.3.⊣
Lemma 3.4. Let V and W be collections of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-patterns such that
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \not \leq _{id} \mathcal {R}^n_k(V)\mbox {-}{\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
. For every function
$\mu : \omega \to \omega $
, there is an
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V, W)$
-instance such that every solution computes a function dominating
$\mu $
.
Proof. Since
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \not \leq _{id} \mathcal {R}^n_k(V)\mbox {-}{\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
, there is some coloring
$\,f_{\textit{fail}} : [\omega ]^n \to k$
and some infinite
${\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution H to f with some witness
$\mu _{\textit{fail}} : \omega \to \omega $
and
$\chi \in \mathcal {R}^n_k(V)$
that meets some
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-pattern
$P \in W$
. Define
$\,f : [\omega ]^n \to k$
by
$\,f(D) = \chi (\mathcal {V}_n(\mu, D))$
. Suppose
$\mu $
is not dominated by any computable function, otherwise we are done. By Cholak and Patey [Reference Cholak and Patey4, theorem 5.11], there is an infinite
$\mu $
-transitive set H which does not compute a function dominating
$\mu $
. Therefore, H is an
${\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution to f with witnesses
$\mu $
and
$\chi \in \mathcal {R}^n_k(V)$
. By definition of
$\mathcal {R}^n_k(V)$
,
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V) \leq _{id} \{\chi \}\mbox {-}{\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
and H is an
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V)$
-solution to f, so
$\,f : [H]^n \to k$
is an instance of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V, W)$
.
We claim that for every
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V, W)$
-solution
$G \subseteq H$
to f, G computes a function dominating
$\mu $
. In particular,
$G\, f$
-avoids P, so by Lemma 2.17, G computes a function dominating
$\mu $
. This completes the proof of Lemma 3.4.⊣
Theorem 3.5. Let V and W be two collections of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-patterns.
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V, W)$
admits strong cone avoidance for nonarithmetical cones if and only if
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \leq _{id} \mathcal {R}^n_k(V)\mbox {-}{\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
.
Proof.
$\Leftarrow $
: This is Lemma 3.3.
$\Rightarrow $
: We prove the contrapositive. Suppose
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \not \leq _{id} \mathcal {R}^n_k(V)\mbox {-}{\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
Let C be a nonarithmetical set with modulus
$\mu $
. By Lemma 3.4, there is a
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V, W)$
-instance such that every solution computes a function dominating
$\mu $
, hence computes C.⊣
In the case
$V = \emptyset $
, then
$\mathcal {R}^n_k(V)$
is the set of all functions
$\chi : \mathcal {V}_n \to k$
and therefore
$\mathcal {R}^n_k(V)\mbox {-}{\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
is
${\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
. We obtain Theorem 2.19, that is,
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(\emptyset, W)$
admits strong cone avoidance for nonarithmetical cones if and only if
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \leq _{id} {\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
. More interestingly, we consider the case where W is the set
$W_{{\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k}$
of patterns forbidding nonhomogeneous sets.
Corollary 3.6. Let V be a collection of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-patterns.
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V, W_{{\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k})$
admits strong cone avoidance for nonarithmetical cones if and only if
$\mathcal {R}^n_k(V)$
contains only constant functions.
Proof. By Theorem 3.5,
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V, W_{{\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k})$
admits strong cone avoidance for nonarithmetical cones if and only if
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k \leq _{id} \mathcal {R}^n_k(V)\mbox {-}{\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
. Case 1:
$\mathcal {R}^n_k(V)$
contains only constant functions. Then for any
$\,f : [\omega ]^n \to k$
, any
$\mathcal {R}^n_k(V)\mbox {-}{\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution to f is f-homogeneous, hence
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k \leq _{id} \mathcal {R}^n_k(V)\mbox {-}{\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
, so
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V, W_{{\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k})$
admits strong cone avoidance for nonarithmetical cones. Case 2:
$\mathcal {R}^n_k(V)$
contains a nonconstant function
$\chi : \mathcal {V}_n \to k$
. Let
$\mu : \omega \to \omega $
be a modulus of a nonarithmetical set C. Let
$\,f(D) = \chi (\mathcal {V}_n(\mu, D))$
. By Cholak and Patey [Reference Cholak and Patey4, corollary 5.5], there is an infinite
$\mu $
-transitive set H which does not compute a function dominating
$\mu $
. Therefore, H is an
$\mathcal {R}^n_k(V)\mbox {-}{\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution to f with witnesses
$\mu $
and
$\chi $
. We claim that H is not f-homogeneous. Indeed, by Theorem 2.10, for every
$\mathcal {G} \in \mathcal {V}_n$
, there is some
$D \in [H]^n$
such that
$\mathcal {G} = \mathcal {V}_n(\mu, D)$
. Since
$\chi $
is not constant on
$\mathcal {V}_n$
, H is not f-homogeneous. Thus
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k \not \leq _{id} \mathcal {R}^n_k(V)\mbox {-}{\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
and
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V, W_{{\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k})$
does not admit strong cone avoidance for nonarithmetical cones.⊣
3.2 Strongly avoiding noncomputable cones
The strong cone avoidance analysis is very similar to the one for nonarithmetical cones, mutatis mutandis. We start again by defining a restricted version of
${\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
.
Statement 3.7. Let
$\mathcal {S}$
be a set of functions of type
$\chi : \mathcal {L}_n \to k$
.
$\mathcal {S}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
: For every function
$\,f : [\omega ]^n \to k$
, there is a strongly increasing relative left-c.e. function
$\mu : \omega \to \omega ^{+}$
, an infinite strongly
$\mu $
-transitive set
$H \subseteq \omega $
, and a coloring
$\chi \in \mathcal {S}$
such that for every
$D \in [H]^n$
,
$\,f(D) = \chi (\mathcal {L}_n(\mu, D))$
.
Given a collection of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-patterns, we define a class
$\mathcal {S}^n_k(W)$
for
${\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
is a similar way as the class
$\mathcal {R}^n_k(W)$
for
${\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
, that is, given some
$n, k \in \omega $
and a collection W of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-patterns, let
$$\begin{align*}\mathcal{S}^n_k(W) = \left\{\chi : \mathcal{L}_n \to k \mbox{ }|\mbox{ } {\operatorname{\mathrm{{\mathsf{RT}}}}}^n_k(W) \leq_{id} \{\chi\}\mbox{-}{\mathsf{SCA}}\mbox{-}{\mathsf{RT}}^n_k\right\}\kern-1.5pt. \end{align*}$$
In particular, if
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
is a true statement, then every constant function
$\chi : \mathcal {L}_n \to k$
belongs to
$\mathcal {S}^n_k(W)$
.
Lemma 3.8. Let V and W be collections of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-patterns such that
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \leq _{id} \mathcal {S}^n_k(V)\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
. Then
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V, W)$
admits strong cone avoidance.
Proof. Fix two sets Z and C with
$C \not \leq _T Z$
and let
$\,f : [\omega ]^n \to k$
be an instance of
${\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
.
By Lerman [Reference Lerman16, theorem 4.18], there is a set
$Z_1 \geq _T Z$
such that C is
$\Delta ^0_2(Z_1)$
but
$C \not \leq _T Z_1$
. Since C is
$\Delta ^0_2(Z_1)$
, there is a left
$Z_1$
-c.e. modulus
$\mu : \omega \to \omega $
for C. By Lemma 2.24, we can assume that
$\mu $
is strongly increasing.
Let
$\,f : [\omega ]^n \to k$
be an instance of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V, W)$
. Let
$\,f_1 : [\omega ]^n \to k \times \mathcal {L}_n$
be defined for each
$D \in [\omega ]^n$
by
$\,f_1(D) = \langle f(D), \mathcal {L}_n(\mu, D) \rangle $
. By strong cone avoidance of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_{<\infty, C_n}$
(Cholak and Patey [Reference Cholak and Patey4, theorem 4.18]), there is an infinite set
$H \subseteq \omega $
such that
$C \not \leq _T Z_1 \oplus H$
and
$|f_1[H]^n| \leq C_n$
. In particular,
$Z_1 \oplus H$
does not compute a function dominating
$\mu $
, so by Theorem 2.27, for every
$\mathcal {G} \in \mathcal {L}_n$
, there is some
$i < k$
and some
$D \in [H]^n$
such that
$\,f_1(D) = \langle i, \mathcal {G} \rangle $
. Since
$|\mathcal {L}_n| = C_n$
(Cholak and Patey [Reference Cholak and Patey4, Lemma 3.16]), this i is unique. For each
$\mathcal {G}$
, let
$\chi (\mathcal {G})$
be such an i. Then for every
$D \in [H]^n$
,
$\,f(D) = \chi (\mathcal {L}_n(\mu, D))$
. By Cholak and Patey [Reference Cholak and Patey4, corollary 5.5], there is an infinite
$\mu $
-transitive subset
$H_1 \subseteq H$
such that
$C \not \leq _T Z \oplus H_1$
. By Lemma 2.26, there is an infinite strongly
$\mu $
-transitive subset
$H_2 \subseteq H_1$
such that
$C \not \leq _T Z \oplus H_2$
. Therefore,
$H_2$
is a
${\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution to f.
If
$\chi \in \mathcal {S}^n_k(V)$
, then since
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \leq _{id} \mathcal {S}^n_k(V)\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
,
$H_2$
is an
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V, W)$
-solution to f, and we are done. So suppose
$\chi \not \in \mathcal {S}^n_k(V)$
. Unfolding the definition,
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V) \not \leq _{id} \{\chi \}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
, so there is a coloring
$\,f_\chi : [\omega ]^n \to k$
and some infinite
${\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution
$H_\chi $
to
$\,f_\chi $
with witnesses
$\mu _\chi : \omega \to \omega ^{+}$
and
$\chi : \mathcal {L}_n \to k$
, that meets some
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-pattern
$P_\chi \in V$
.
However,
$H_2\, f$
-avoids
$P_\chi $
since f is an instance of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V, W)$
. By Lemma 2.30,
$H_2 \oplus Z$
computes a function dominating
$\mu $
, hence
$C \leq _T Z \oplus H_2$
, contradiction. This completes the proof of Lemma 3.8.⊣
Lemma 3.9. Let V and W be collections of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-patterns such that
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \not \leq _{id} \mathcal {S}^n_k(V)\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
. For every strongly increasing left-c.e. function
$\mu : \omega \to \omega $
, there is an
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V, W)$
-instance such that every solution computes a function dominating
$\mu $
.
Proof. Since
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \not \leq _{id} \mathcal {S}^n_k(V)\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
, there is some coloring
$\,f_{\textit{fail}} : [\omega ]^n \to k$
and some infinite
${\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution
$H_{\textit{fail}}$
to
$\,f_{\textit{fail}}$
with some witness
$\mu _{\textit{fail}} : \omega \to \omega $
and
$\chi \in \mathcal {S}^n_k(V)$
that meets some
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-pattern
$P \in W$
. Define
$\,f : [\omega ]^n \to k$
by
$\,f(D) = \chi (\mathcal {L}_n(\mu, D))$
. Suppose that
$\mu $
is not dominated by a computable function. By Cholak and Patey [Reference Cholak and Patey4, theorem 5.11] and Lemma 2.26, there is an infinite strongly
$\mu $
-transitive set H which does not compute a function dominating
$\mu $
. Therefore, H is a
${\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution to f with witnesses
$\mu $
and
$\chi \in \mathcal {S}^n_k(V)$
. By definition of
$\mathcal {S}^n_k(V)$
,
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V) \leq _{id} \{\chi \}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
and H is an
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V)$
-solution to f, so
$\,f : [H]^n \to k$
is an instance of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V, W)$
.
We claim that for every
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V, W)$
-solution
$G \subseteq H$
to f, G computes a function dominating
$\mu $
. In particular,
$G\, f$
-avoids P, so by Lemma 2.30, G computes a function dominating
$\mu $
. This completes the proof of Lemma 3.9.⊣
Theorem 3.10. Let V and W be two collections of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-patterns.
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V, W)$
admits strong cone avoidance if and only if
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \leq _{id} \mathcal {S}^n_k(V)\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
.
Proof.
$\Leftarrow $
: This is Lemma 3.8.
$\Rightarrow $
: We prove the contrapositive. Suppose
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \not \leq _{id} \mathcal {S}^n_k(V)\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
. Let
$\mu $
be a strongly increasing left-c.e. modulus of
$\emptyset '$
. By Lemma 3.9, there is a
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V, W)$
-instance such that every solution computes a function dominating
$\mu $
, hence computes
$\emptyset '$
.⊣
Corollary 3.11. Let V be a collection of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-patterns.
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V, W_{{\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k})$
admits strong cone avoidance if and only if
$\mathcal {S}^n_k(V)$
contains only constant functions.
Proof. By Theorem 3.10,
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V, W_{{\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k})$
admits strong cone avoidance if and only if
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k \leq _{id} \mathcal {S}^n_k(V)\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
. Case 1:
$\mathcal {S}^n_k(V)$
contains only constant functions. Then for any
$\,f : [\omega ]^n \to k$
, any
$\mathcal {S}^n_k(V)\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution to f is f-homogeneous, hence
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k \leq _{id} \mathcal {S}^n_k(V)\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
, so
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V, W_{{\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k})$
admits strong cone avoidance. Case 2:
$\mathcal {S}^n_k(V)$
contains a nonconstant function
$\chi : \mathcal {L}_n \to k$
. Let
$\mu : \omega \to \omega $
be a strongly increasing left-c.e modulus of a noncomputable set C. Let
$\,f(D) = \chi (\mathcal {L}_n(\mu, D))$
. By Cholak and Patey [Reference Cholak and Patey4, corollary 5.5] and Lemma 2.26, there is an infinite strongly
$\mu $
-transitive set H such that
$C \not \leq _T H$
. Therefore, H is an
$\mathcal {S}^n_k(V)\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution to f with witnesses
$\mu $
and
$\chi $
. We claim that H is not f-homogeneous. Since
$C \not \leq _T H$
, then in particular, H does not compute a function dominating
$\mu $
, so by Theorem 2.27, for every
$\mathcal {G} \in \mathcal {L}_n$
, there is some
$D \in [H]^n$
such that
$\mathcal {G} = \mathcal {L}_n(\mu, D)$
. Since
$\chi $
is not constant on
$\mathcal {L}_n$
, H is not f-homogeneous. Thus
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k \not \leq _{id} \mathcal {S}^n_k(V)\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
and
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V, W_{{\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k})$
does not admit strong cone avoidance.⊣
3.3 Avoiding noncomputable cones
Last, we complete our analysis of this extended class of promise Ramsey-like theorems with cone avoidance. The analysis follows the same scheme.
Statement 3.12. Let
$\mathcal {T}$
be a set of functions of type
$\chi : \mathcal {P}_n \to k$
.
$\mathcal {T}\mbox {-}{\mathsf {CA}}\mbox {-}{\mathsf {RT}}^n_k$
: For every function
$\,f : [\omega ]^n \to k$
, there is a strongly increasing relative left-c.e. function
$\mu : \omega \to \omega ^{+}$
, an infinite strongly
$\mu $
-transitive set
$H \subseteq \omega $
, and a coloring
$\chi \in \mathcal {T}$
such that for every
$D \in [H]^n$
,
$\,f(D) = \chi (\mathcal {P}_n(\mu, D))$
.
We now define
$\mathcal {T}^n_k(W)$
the same way we defined
$\mathcal {R}^n_k(W)$
and
$\mathcal {S}^n_k(W)$
for
${\mathsf {ARITH}}\mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
and
${\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
, respectively. Given some
$n, k \in \omega $
and a collection W of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-patterns, let
$$\begin{align*}\mathcal{T}^n_k(W) = \left\{\chi : \mathcal{P}_n \to k \mbox{ }|\mbox{ } {\operatorname{\mathrm{{\mathsf{RT}}}}}^n_k(W) \leq_{id} \{\chi\}\mbox{-}{\mathsf{CA}}\mbox{-}{\mathsf{RT}}^n_k\right\}\kern-1.5pt. \end{align*}$$
In particular, if
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
is a true statement, then every constant function
$\chi : \mathcal {P}_n \to k$
belongs to
$\mathcal {T}^n_k(W)$
.
Lemma 3.13. Let V and W be collections of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-patterns such that
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \leq _{id} \mathcal {T}^n_k(V)\mbox {-}{\mathsf {CA}}\mbox {-}{\mathsf {RT}}^n_k$
. Then
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V, W)$
admits cone avoidance.
Proof. Fix two sets Z and C with
$C \not \leq _T Z$
and let
$\,f : [\omega ]^n \to k$
be a Z-computable instance of
${\mathsf {CA}}\mbox {-}{\mathsf {RT}}^n_k$
.
By Lerman [Reference Lerman16, theorem 4.18], there is a set
$Z_1 \geq _T Z$
such that C is
$\Delta ^0_2(Z_1)$
but
$C \not \leq _T Z_1$
. Since C is
$\Delta ^0_2(Z_1)$
, there is a left
$Z_1$
-c.e. modulus
$\mu : \omega \to \omega $
for C. By Lemma 2.24, we can assume that
$\mu $
is strongly increasing.
Let
$\,f_1 : [\omega ]^n \to k \times \mathcal {P}_n$
be defined for each
$D \in [\omega ]^n$
by
$\,f_1(D) = \langle f(D), \mathcal {P}_n(\mu, D) \rangle $
. By cone avoidance of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_{<\infty, C_{n-1}}$
(Cholak and Patey [Reference Cholak and Patey4, corollary 4.19]), there is an infinite set
$H \subseteq \omega $
such that
$C \not \leq _T Z_1 \oplus H$
and
$|f_1[H]^n| \leq C_{n-1}$
. In particular,
$Z_1 \oplus H$
does not compute a function dominating
$\mu $
, so by Theorem 2.27, for every
$\mathcal {G} \in \mathcal {P}_n$
, there is some
$i < k$
and some
$D \in [H]^n$
such that
$\,f_1(D) = \langle i, \mathcal {G} \rangle $
. Since
$|\mathcal {P}_n| = C_{n-1}$
(Cholak and Patey [Reference Cholak and Patey4, Lemma 3.15 and 3.16]), this i is unique. For each
$\mathcal {G}$
, let
$\chi (\mathcal {G})$
be such an i. For every
$D \in [H]^n$
,
$\,f(D) = \chi (\mathcal {P}_n(\mu, D))$
. By Cholak and Patey [Reference Cholak and Patey4, corollary 5.5], there is an infinite
$\mu $
-transitive subset
$H_1 \subseteq H$
such that
$C \not \leq _T Z \oplus H_1$
. By Lemma 2.26, there is an infinite strongly
$\mu $
-transitive subset
$H_2 \subseteq H_1$
such that
$C \not \leq _T Z \oplus H_2$
. Therefore,
$H_2$
is a
${\mathsf {CA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution to f.
If
$\chi \in \mathcal {T}^n_k(V)$
, then since
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \leq _{id} \mathcal {T}^n_k(V)\mbox {-}{\mathsf {CA}}\mbox {-}{\mathsf {RT}}^n_k$
,
$H_2$
is an
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V, W)$
-solution to f, and we are done. So suppose
$\chi \not \in \mathcal {T}^n_k(V)$
. Unfolding the definition,
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V) \not \leq _{id} \{\chi \}\mbox {-}{\mathsf {CA}}\mbox {-}{\mathsf {RT}}^n_k$
, so there is a coloring
$\,f_\chi : [\omega ]^n \to k$
and some infinite
${\mathsf {CA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution
$H_\chi $
to
$\,f_\chi $
with witnesses
$\mu _\chi : \omega \to \omega ^{+}$
and
$\chi : \mathcal {P}_n \to k$
, that meets some
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-pattern
$P_\chi \in V$
.
However,
$H_2\, f$
-avoids
$P_\chi $
since f is an instance of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V, W)$
. By Lemma 2.46,
$H_2 \oplus Z$
computes a function dominating
$\mu $
, hence
$C \leq _T Z \oplus H_2$
, contradiction. This completes the proof of Lemma 3.13.⊣
Lemma 3.14. Let V and W be collections of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-patterns such that
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \not \leq _{id} \mathcal {T}^n_k(V)\mbox {-}{\mathsf {CA}}\mbox {-}{\mathsf {RT}}^n_k$
. For every strongly increasing left-c.e. function
$\mu : \omega \to \omega $
, there is a set Z which does not compute a function dominating
$\mu $
, and a Z-computable
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V, W)$
-instance such that every solution Z-computes a function dominating
$\mu $
.
Proof. Since
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \not \leq _{id} \mathcal {T}^n_k(V)\mbox {-}{\mathsf {CA}}\mbox {-}{\mathsf {RT}}^n_k$
, there is some coloring
$\,f_{\textit{fail}} : [\omega ]^n \to k$
and some infinite
${\mathsf {CA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution H to f with some witness
$\mu _{\textit{fail}} : \omega \to \omega ^{+}$
and
$\chi \in \mathcal {T}^n_k(V)$
that meets some
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-pattern
$P \in W$
. Define
$\,f : [\omega ]^n \to k$
by
$\,f(D) = \chi (\mathcal {P}_n(\mu, D))$
. Suppose that
$\mu $
is not dominated by a computable function. By Cholak and Patey [Reference Cholak and Patey4, theorem 5.11] and Lemma 2.26, there is an infinite strongly
$\mu $
-transitive set H which does not compute a function dominating
$\mu $
. Therefore, H is a
${\mathsf {CA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution to f with witnesses
$\mu $
and
$\chi \in \mathcal {T}^n_k(V)$
. By definition of
$\mathcal {T}^n_k(V)$
,
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V) \leq _{id} \{\chi \}\mbox {-}{\mathsf {CA}}\mbox {-}{\mathsf {RT}}^n_k$
and H is an
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V)$
-solution to f, so
$\,f : [H]^n \to k$
is an H-computable instance of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V, W)$
such that H does not compute a function dominating
$\mu $
.
We claim that for every
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V, W)$
-solution
$G \subseteq H$
to f,
$G \oplus H$
computes a function dominating
$\mu $
. In particular,
$G\, f$
-avoids P, so by Lemma 2.46,
$G \oplus H$
computes a function dominating
$\mu $
. This completes the proof of Lemma 3.14.⊣
Theorem 3.15. Let V and W be two collections of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-patterns.
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V, W)$
admits cone avoidance if and only if
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \leq _{id} \mathcal {T}^n_k(V)\mbox {-}{\mathsf {CA}}\mbox {-}{\mathsf {RT}}^n_k$
.
Proof.
$\Leftarrow $
: This is Lemma 3.13.
$\Rightarrow $
: We prove the contrapositive. Suppose
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \not \leq _{id} \mathcal {T}^n_k(V)\mbox {-}{\mathsf {CA}}\mbox {-}{\mathsf {RT}}^n_k$
. Let
$\mu $
be a strongly increasing left-c.e. modulus of
$\emptyset '$
. By Lemma 3.14, there is a set Z which does not compute a function dominating
$\mu $
and a Z-computable
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V, W)$
-instance such that every solution Z computes a function dominating
$\mu $
, hence computes
$\emptyset '$
. Therefore
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
does not admit cone avoidance.⊣
Corollary 3.16. Let V be a collection of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k$
-patterns.
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V, W_{{\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k})$
admits cone avoidance if and only if
$\mathcal {T}^n_k(V)$
contains only constant functions.
Proof. By Theorem 3.15,
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V, W_{{\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k})$
admits cone avoidance if and only if
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k \leq _{id} \mathcal {T}^n_k(V)\mbox {-}{\mathsf {CA}}\mbox {-}{\mathsf {RT}}^n_k$
. Case 1:
$\mathcal {T}^n_k(V)$
contains only constant functions. Then for any
$\,f : [\omega ]^n \to k$
, any
$\mathcal {T}^n_k(V)\mbox {-}{\mathsf {CA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution to f is f-homogeneous, hence
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k \leq _{id} \mathcal {T}^n_k(V)\mbox {-}{\mathsf {CA}}\mbox {-}{\mathsf {RT}}^n_k$
, so
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V, W_{{\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k})$
admits cone avoidance. Case 2:
$\mathcal {T}^n_k(V)$
contains a nonconstant function
$\chi : \mathcal {P}_n \to k$
. Let
$\mu : \omega \to \omega $
be a strongly increasing left-c.e modulus of a noncomputable set C. Let
$\,f(D) = \chi (\mathcal {P}_n(\mu, D))$
. By Cholak and Patey [Reference Cholak and Patey4, corollary 5.5] and Lemma 2.26, there is an infinite strongly
$\mu $
-transitive set H which does not compute C. Therefore, H is a
$\mathcal {T}^n_k(V)\mbox {-}{\mathsf {CA}}\mbox {-}{\mathsf {RT}}^n_k$
-solution to f with witnesses
$\mu $
and
$\chi $
. We claim that H is not f-homogeneous. Indeed, since
$C \not \leq _T H$
, then H does not compute a function dominating
$\mu $
, so by Theorem 2.40, for every
$\mathcal {G} \in \mathcal {P}_n$
, there is some
$D \in [H]^n$
such that
$\mathcal {G} = \mathcal {P}_n(\mu, D)$
. Since
$\chi $
is not constant on
$\mathcal {P}_n$
, H is not f-homogeneous. Thus
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k \not \leq _{id} \mathcal {T}^n_k(V)\mbox {-}{\mathsf {CA}}\mbox {-}{\mathsf {RT}}^n_k$
and
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(V, W_{{\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k})$
does not admit cone avoidance.⊣
4 Applications
In this section, we exemplify the use of this framework by reproving existing theorems in reverse mathematics without involving any forcing argument.
4.1 Ramsey’s theorem
Ramsey’s theorem for pairs is one of the most famous theorems studied in reverse mathematics as it is historically the first one which is not equivalent (and not even linearly ordered with) the five systems of axioms known as the Big Five [Reference Simpson27]. The first theorem that we reprove with our framework is the celebrated Seetapun theorem [Reference Seetapun and Slaman26, theorem 2.1], answering negatively the long-standing question whether
${\operatorname {\mathrm {{\mathsf {RT}}}}}^2_2$
is equivalent to the Arithmetical Comprehension Axiom (
$\operatorname {\mathrm {{\mathsf {ACA}}}}$
) over
$\operatorname {\mathrm {{\mathsf {RCA}}_0}}$
.
Theorem 4.1 (Seetapun and Slaman [Reference Seetapun and Slaman26])
For every
$k \geq 1$
,
${\operatorname {\mathrm {{\mathsf {RT}}}}}^2_k$
admits cone avoidance.
Proof. By Theorem 2.45,
${\mathsf {CA}}\mbox {-}{\mathsf {RT}}^2_k$
admits cone avoidance. As explained,
${\mathsf {CA}}\mbox {-}{\mathsf {RT}}^2_k$
is nothing but the statement
${\operatorname {\mathrm {{\mathsf {RT}}}}}^2_k$
. Indeed, since
$|\mathcal {P}_2| = 1$
, the function
$\chi : \mathcal {P}_2 \to k$
is constant, and
${\mathsf {CA}}\mbox {-}{\mathsf {RT}}^2_k$
asserts the existence of an infinite set H over which f belongs to the range of
$\chi $
. In particular H is f-homogeneous.⊣
Later, Jockusch and Dzhafarov [Reference Jockusch15, lemma 3.2] adapted the proof of Seetapun’s theorem to obtain strong cone avoidance of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^1_k$
.
Theorem 4.2 (Jockusch and Dzhafarov [Reference Jockusch15])
For every
$k \geq 1$
,
${\operatorname {\mathrm {{\mathsf {RT}}}}}^1_k$
admits strong cone avoidance.
Proof. By Theorem 2.29,
${\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^1_k$
admits strong cone avoidance. Here again,
${\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^1_k$
is nothing but the statement
${\operatorname {\mathrm {{\mathsf {RT}}}}}^1_k$
, since
$|\mathcal {L}_1| = 1$
.⊣
Wang [Reference Wang29, theorem 3.1] surprisingly proved that for every n, whenever
$\ell $
is sufficiently large, then
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_{<\infty, \ell }$
admits strong cone avoidance. Cholak and Patey [Reference Cholak and Patey4, theorem 4.18] improved his bound to Catalan’s sequence, and proved the tightness of the result. The following theorem was used all over the article, and we can actually get a reversal.
Theorem 4.3 (Cholak and Patey [Reference Cholak and Patey4])
For every
$n \geq 1$
,
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_{<\infty, C_n}$
admits strong cone avoidance.
Proof. By Theorem 2.29,
${\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
admits strong cone avoidance. In particular,
${\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
asserts the existence, for every coloring
$\,f : [\omega ]^n \to k$
, of an infinite set H and a function
$\chi : \mathcal {L}_n \to k$
such that
$\,f[H]^n \subseteq \chi (\mathcal {L}_n)$
. Since
$|\mathcal {L}_n| = C_n$
, it follows that
$|f[H]^n| \leq C_n$
and therefore that H is an
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_{<\infty, C_n}$
-solution to f.⊣
4.2 The
$\operatorname {\mathrm {{\mathsf {EM}}}}$
theorem and the Ascending Descending sequence
A tournament T is a directed graph such that any two vertices has exactly one arrow. We consider the predicate
$T(x, y)$
to be true if there is an arrow from x to y. A set H is T-transitive if for every
$x, y, z \in H$
such that
$T(x, y)$
and
$T(y, z)$
both hold, then
$T(x, z)$
holds.
Statement 4.4 (Erdős–Moser)
$\operatorname {\mathrm {{\mathsf {EM}}}}$
: Every infinite tournament admits an infinite transitive set.
A tournament T can be represented by a coloring
$\,f : [\omega ]^2 \to 2$
such that for every
$x < y$
,
$\,f(x, y) = 1$
if and only if
$T(x, y)$
holds. A set H is f-transitive if for every
$x < y < z \in H$
and
$i < 2$
, if
$\,f(x, y) = f(y, z)= i$
then
$\,f(x, z) = i$
. One can see the
$\operatorname {\mathrm {{\mathsf {EM}}}}$
theorem as the Ramsey-like statement “For every coloring
$\,f : [\omega ]^2 \to 2$
, there is an infinite f-transitive set H.”
The following
$\operatorname {\mathrm {{\mathsf {ADS}}}}$
principle was introduced and studied by Hirschfeldt and Shore [Reference Hirschfeldt and Shore14] in the context of reverse mathematics.
Statement 4.5 (Ascending Descending sequence)
$\operatorname {\mathrm {{\mathsf {ADS}}}}$
: Every infinite linear order has an infinite ascending or descending sequence.
As explained, a linear order
$(\omega, {\prec }_{\mathcal {L}})$
can be represented by a coloring
$\,f : [\omega ]^2 \to 2$
such that for every
$x < y \in \omega $
,
$\,f(x, y) = 1$
if and only if
$x {\prec }_{\mathcal {L}} y$
. In particular,
$\omega $
is f-transitive. The Ascending Descending sequence principle can be seen as the promise Ramsey-like statement “For every coloring
$\,f : [\omega ]^2 \to 2$
such that
$\omega $
is f-transitive, there is an infinite f-homogeneous set.”
The
$\operatorname {\mathrm {{\mathsf {EM}}}}$
principle was introduced by Bovykin and Weiermann [Reference Bovykin and Weiermann1] as a way to decompose the proof of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^2_2$
into two steps. Indeed, given a coloring
$\,f : [\omega ]^2 \to 2$
, by
$\operatorname {\mathrm {{\mathsf {EM}}}}$
, there is an infinite set X over which f is transitive, and by
$\operatorname {\mathrm {{\mathsf {ADS}}}}$
, there is an infinite f-homogeneous subset
$Y \subseteq X$
. The author [Reference Patey20] proved that
$\operatorname {\mathrm {{\mathsf {EM}}}}$
admits strong cone avoidance.
Theorem 4.6 (Patey [Reference Patey20])
$\operatorname {\mathrm {{\mathsf {EM}}}}$
admits strong cone avoidance.
Proof. By Theorem 2.32, it suffices to prove that
$\operatorname {\mathrm {{\mathsf {EM}}}} \leq _{id} {\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^2_2$
. However,
${\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^2_2$
is the statement
${\mathsf {LARGE}}_2$
saying that for every coloring
$\,f : [\omega ]^2 \to 2$
, there is some
$i < 2$
and an infinite set H such that for every
$x < y < z \in H$
,
$\,f(x, y) = f(y, z) = i$
if and only if
$\,f(x, z) = i$
. In particular H is f-transitive.⊣
The author [Reference Patey20] also deduced that
$\operatorname {\mathrm {{\mathsf {ADS}}}}$
does not admit strong cone avoidance. Indeed, if
$\operatorname {\mathrm {{\mathsf {ADS}}}}$
and
$\operatorname {\mathrm {{\mathsf {EM}}}}$
both admit strong cone avoidance, then
${\operatorname {\mathrm {{\mathsf {RT}}}}}^2_2$
does, which is known not to be the case. One can however reprove it directly from our criterion for promise Ramsey-like theorems.
Theorem 4.7 (Patey [Reference Patey20])
$\operatorname {\mathrm {{\mathsf {ADS}}}}$
does not admit strong cone avoidance.
Proof. Let
$V_{\operatorname {\mathrm {{\mathsf {ADS}}}}}$
be the set of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^2_2$
-patterns forbidding nontransitive colorings.
$\operatorname {\mathrm {{\mathsf {ADS}}}}$
is the promise Ramsey-like statement
${\operatorname {\mathrm {{\mathsf {RT}}}}}^2_2(V_{\operatorname {\mathrm {{\mathsf {ADS}}}}}, W_{{\operatorname {\mathrm {{\mathsf {RT}}}}}^2_2})$
. By Corollary 3.11,
$\operatorname {\mathrm {{\mathsf {ADS}}}}$
admits strong cone avoidance if and only if
$\mathcal {S}^2_2(V_{\operatorname {\mathrm {{\mathsf {ADS}}}}})$
contains only constant functions. Since
${\operatorname {\mathrm {{\mathsf {RT}}}}}^2_2(V_{\operatorname {\mathrm {{\mathsf {ADS}}}}}) \leq _{id} {\mathsf {LARGE}}_2$
and
${\mathsf {LARGE}}_2$
is the statement
${\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^2_2$
, then
$\mathcal {S}^2_2(V_{\operatorname {\mathrm {{\mathsf {ADS}}}}})$
contains all the functions
$\chi : \mathcal {L}_2 \to 2$
. Since
$|\mathcal {L}_2| = 2$
,
$\operatorname {\mathrm {{\mathsf {ADS}}}}$
does not admit strong cone avoidance.⊣
Dorais et al [Reference Dorais, Dzhafarov, Hirst, Mileti and Shafer8] studied combinatorial principles, including Ramsey’s theorem, under the Weihrauch reduction. They introduced for this some new consequences of Ramsey’s theorem for pairs, such as
$\operatorname {\mathrm {{\mathsf {SHER}}}}$
. Given a coloring
$\,f : [\omega ]^2 \to k$
, a set
$H \subseteq \omega $
is f-semi-hereditary if for all
$i < k$
except possibly one, whenever
$x < y < z \in H$
and
$\,f(x, z) = f(y, z) = i$
, then
$\,f(x, y) = i$
.
Statement 4.8 (Semi-hereditary)
$\operatorname {\mathrm {{\mathsf {SHER}}}}_k$
: Every coloring
$\,f : [\omega ]^2 \to k$
such that
$\omega $
is f-semi-hereditary has an infinite f-homogeneous set.
The restriction
$\operatorname {\mathrm {{\mathsf {SHER}}}}_2$
was studied by Dorais (unpublished), who showed that it follows from
$\operatorname {\mathrm {{\mathsf {ADS}}}}$
. Thanks to our general criterion for promise Ramsey-like principles, we can prove the following theorem.
Theorem 4.9. For every
$k \geq 2$
,
$\operatorname {\mathrm {{\mathsf {SHER}}}}_k$
does not admit strong cone avoidance.
Proof. Let
$V_{\operatorname {\mathrm {{\mathsf {SHER}}}}_k}$
be the set of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^2_k$
-patterns forbidding nonsemi-hereditary colorings.
$\operatorname {\mathrm {{\mathsf {SHER}}}}_k$
is the promise Ramsey-like statement
${\operatorname {\mathrm {{\mathsf {RT}}}}}^2_2(V_{\operatorname {\mathrm {{\mathsf {SHER}}}}_k}, W_{{\operatorname {\mathrm {{\mathsf {RT}}}}}^2_k})$
. By Corollary 3.11,
$\operatorname {\mathrm {{\mathsf {SHER}}}}_k$
admits strong cone avoidance if and only if
$\mathcal {S}^2_k(V_{\operatorname {\mathrm {{\mathsf {SHER}}}}_k})$
contains only constant functions.
We now prove that
$\operatorname {\mathrm {{\mathsf {SHER}}}}_k \leq _{id} {\mathsf {LARGE}}_k$
. Fix a coloring
$\,f : [\omega ]^2 \to k$
and let H be an infinite
${\mathsf {LARGE}}_k$
-solution to f. In particular, there are two colors
$i_s, i_\ell < k$
such that
$\,f[H]^2 \subseteq \{i_s, i_\ell \}$
and for every
$x < y < z \in H$
,
$\,f(x, y) = f(y, z) = i_s$
if and only if
$\,f(x, z) = i_s$
. Therefore, for all colors
$i < k$
except possibly
$i_\ell $
, whenever
$\,f(x, z) = f(y, z) = i$
, then
$\,f(x, y) = i$
.
Since
${\mathsf {LARGE}}_k$
is the statement
${\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^2_k$
, then
$\mathcal {S}^2_k(V_{\operatorname {\mathrm {{\mathsf {SHER}}}}_k})$
contains all the functions
$\chi : \mathcal {L}_2 \to k$
. Since
$|\mathcal {L}_2| = 2$
,
$\operatorname {\mathrm {{\mathsf {SHER}}}}_k$
does not admit strong cone avoidance.⊣
4.3 The free set theorem
We now provide an example of application to a statement which involves
$\omega $
-colorings of
$[\omega ]^n$
. The free set theorem was introduced by Friedman [Reference Friedman11] and then studied by Cholak et al [Reference Cholak, Giusto, Hirst and Jockusch2] in the framework of reverse mathematics. Given a coloring
$\,f : [\omega ]^n \to \omega $
, a set
$H \subseteq \omega $
is f-free if for every
$D \in [H]^n$
, whenever
$\,f(D) \in H$
then
$\,f(D) \in D$
. Equivalently, H is f-free if for every
$x \in H$
,
$x \not \in f[H \smallsetminus \{x\}]^n$
.
Statement 4.10 (Free set theorem)
$\operatorname {\mathrm {{\mathsf {FS}}}}^n$
: Every coloring
$\,f : [\omega ]^n \to \omega $
has an infinite f-free set.
Given a coloring
$\,f : [\omega ]^n \to \omega $
, for every
$D = \{x_0 < \dots < x_n \} \in [\omega ]^{n+1}$
, let
$g(D)$
be the function
$g_D : [n+1]^n \to 2$
defined for every
$E \in [n+1]^n$
by
$g_D(E) = 1$
if and only if
$\,f(\{x_i : i \in E\}) = x_j$
where j is the unique value in
$D \smallsetminus E$
. Since there are
$2^{n+1}$
functions of type
$[n+1]^n \to 2$
, one can see g as a function of type
$[\omega ]^{n+1} \to 2^{n+1}$
. Moreover, every g-homogeneous set H must be for color the 0-constant function of type
$[n+1]^n \to 2$
, and H is then f-free. We say that an infinite set H is g-functional if for every
$D_1 = \{x_0 < \dots < x_n\}, D_2 = \{y_0 < \dots < y_n \} \in [\omega ]^{n+1}$
and
$E \in [n+1]^n$
, if
$g(D_1)(E) = g(D_2)(E) = 1$
, then
$\{x_i : i \in E\} = \{y_i : i \in E\}$
. In particular,
$\omega $
is g-functional for the coloring
$g : [\omega ]^{n+1} \to 2^{n+1}$
defined above. We can therefore see
$\operatorname {\mathrm {{\mathsf {FS}}}}^n$
as the promise Ramsey-like statement “For every coloring
$g : [\omega ]^{n+1} \to 2^{n+1}$
such that
$\omega $
is g-functional, there is an infinite g-homogeneous set.” Wang [Reference Wang29, theorem 4.1] proved the following theorem.
Theorem 4.11 (Wang [Reference Wang29])
For every
$n \geq 1$
,
$\operatorname {\mathrm {{\mathsf {FS}}}}^n$
admits strong cone avoidance.
Proof. Let
$V_{\operatorname {\mathrm {{\mathsf {FS}}}}^n}$
be the set of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^{n+1}_{2^{n+1}}$
-patterns which ensures that
$\omega $
is g-functional. By Corollary 3.11,
$\operatorname {\mathrm {{\mathsf {FS}}}}^n$
admits strong cone avoidance if and only if
$\mathcal {S}^{n+1}_{2^{n+1}}(V_{\operatorname {\mathrm {{\mathsf {FS}}}}^n})$
contains only constant functions.
Let
$\chi : \mathcal {L}_{n+1} \to 2^{n+1}$
be a nonconstant function. In particular, there is some
$\mathcal {G} \in \mathcal {L}_{n+1}$
such that
$\chi (\mathcal {G}) : [n+1]^n \to 2$
is different from the 0-constant function of type
$[n+1]^n \to 2$
.
Let
$\mu : \omega \to \omega $
be a strongly increasing left-c.e. modulus of
$\emptyset '$
. Let
$\rho : \omega \to \omega $
be the left-c.e. function defined for every
$n, x \in \omega $
by
$\rho _{2n}(2x) = 2\mu _n(x)$
,
$\rho _{2n}(2x+1) = \rho _{2n}(2x)$
and
$\rho _{2n+1} = \rho _{2n}$
. Informally,
$\rho $
is obtained from
$\mu $
by considering the integers of
$\mu $
as even numbers for
$\rho $
, and interleaving odd numbers which do not change the value of
$\rho $
. We claim that
$\rho $
is strongly increasing. First of all for every n,
$\rho _{2n}$
is nondecreasing, and since
$\rho _{2n+1} = \rho _{2n}$
, neither is
$\rho _{2n+1}$
. We need to check that for every
$x < y \in \omega $
and
$s \in \omega $
, if
$\rho _{s+1}(x)> \rho _s(x)$
then
$\rho _{s+1}(y)> s$
. By construction of
$\rho $
, if
$\rho _{s+1}(x)> \rho _s(x)$
then s is of the form
$2s_1+1$
. Let
$x_1 = \lfloor x/2 \rfloor $
and
$y_1 = \lfloor y/2\rfloor $
. In particular
$\mu _{s_1+1}(x_1)> \mu _{s_1}(x_1)$
, and since
$\mu $
is strongly increasing,
$\mu _{s_1+1}(y_1)> s_1$
so
$\rho _{s+1}(y) = 2\mu _{s_1+1}(y_1)> 2s_1$
so
$\rho _{s+1}(y)> s$
. Thus
$\rho $
is a strongly increasing left-c.e. function. Moreover, every function dominating
$\rho $
computes
$\emptyset '$
.
Let
$\,f : [\omega ]^{n+1} \to 2^{n+1}$
be defined by
$\,f(D) = \chi (\mathcal {L}_{n+1}(\rho, D))$
. By Cholak and Patey [Reference Cholak and Patey4, corollary 5.5] and Lemma 2.26, there is an infinite strongly
$\rho $
-transitive set
$H_{even} \subseteq \{2n : n \in \omega \}$
which does not compute
$\emptyset '$
, hence does not compute a function dominating
$\rho $
. We claim that
$H = \{x, x+1 : x \in H_{even}\}$
is strongly
$\rho $
-transitive. Let
$w < x < y < z \in H$
be such that
$\rho _z(w)> x$
and
$\rho _z(x)> y$
. Let
$w_1, x_1, y_1$
and
$z_1$
be the largest even value smaller or equal to w, x, y and z, respectively. Then
$\rho _{z_1}(w_1) = \rho _z(w)> x \geq x_1$
and
$\rho _{z_1}(x_1) = \rho _z(x)> y \geq y_1$
. By strong
$\rho $
-transitivity of
$H_{even}$
,
$\rho _{z_1}(w_1)> y_1$
. In particular,
$\rho _z(w) = \rho _{z_1}(w_1)> y_1$
, and since
$\rho _z(w)$
is even,
$\rho _z(w)> y$
. Therefore, H is a
$\chi \mbox {-}{\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^{n+1}_{2^{n+1}}$
-solution to f with witness
$\rho $
.
We claim that H is not an
${\operatorname {\mathrm {{\mathsf {RT}}}}}^{n+1}_{2^{n+1}}(V_{\operatorname {\mathrm {{\mathsf {FS}}}}^n})$
-solution to f. Let
$\mathcal {G} \in \mathcal {L}_{n+1}$
be such that
$\chi (\mathcal {G})$
is not the 0-constant function of type
$[n+1]^n \to 2$
. In particular, there is some
$E \in [n+1]^n$
such that
$\chi (\mathcal {G})(E) = 1$
.
Since
$H_{even}$
does not compute
$\emptyset '$
, hence does not compute a function dominating
$\rho $
, by Theorem 2.27, there is some
$D_{even} = \{x_0 < \dots < x_n\} \in [H_{even}]^{n+1}$
such that
$\mathcal {G} = \mathcal {L}_{n+1}(\rho, D_{even})$
. Let t be the unique element of
$\{0, \dots, n+1\} \smallsetminus E$
and let
$D = \{x_i : i \in E\} \cup \{x_t+1\}$
. In particular,
$D \in [H]^{n+1}$
. By construction of
$\rho $
,
$\mathcal {L}_{n+1}(\rho, D_{even}) = \mathcal {L}_{n+1}(\rho, D) = \mathcal {G}$
, so
$\,f(D) = f(D_{even}) = \chi (\mathcal {G})$
. Then D and
$D_{even} \in [H]^{n+1}$
witness that H is not f-functional, and therefore that H is not an
${\operatorname {\mathrm {{\mathsf {RT}}}}}^{n+1}_{2^{n+1}}(V_{\operatorname {\mathrm {{\mathsf {FS}}}}^n})$
-solution to f.⊣
4.4 The canonical Ramsey theorem and the rainbow Ramsey theorem
We conclude this section by providing a more general translation scheme from principles involving
$\omega $
-colorings of
$[\omega ]^n$
into promise Ramsey-like statements.
As shown by Theorem 2.4, Ramsey’s theorem is the maximal true Ramsey-like theorem for finite colorings of
$[\omega ]^n$
. The following canonical Ramsey theorem can be seen as the maximal true Ramsey-like theorem for
$\omega $
-colorings from
$[\omega ]^n$
. Given a coloring
$\,f : [\omega ]^n \to \omega $
, a set H is f-canonical if there is a set
$U \subseteq \{0, \dots, n-1\}$
such that for every
$D_0 = \{x_0 < \dots < x_{n-1}\} \in [H]^n$
and
$D_1 = \{y_0 < \dots < y_{n-1}\} \in [H]^n$
,
$\,f(D_0) = f(D_1)$
if and only if for every
$i \in U$
,
$x_i = y_i$
.
Statement 4.12 (Canonical Ramsey theorem)
$\operatorname {\mathrm {{\mathsf {CRT}}}}^n$
: Every coloring
$\,f : [\omega ]^n \to \omega $
has an infinite f-canonical set.
The canonical Ramsey theorem was first studied by Mileti [Reference Mileti18] from a computability-theoretic viewpoint. He proved in particular that
$\operatorname {\mathrm {{\mathsf {CRT}}}}^2$
does not admit cone avoidance. We now explain how to express the canonical Ramsey theorem as a promise Ramsey-like statement.
Given a function
$\,f : [\omega ]^n \to \omega $
, for every
$D = \{x_0 < \dots < x_{2n-1}\} \in [\omega ]^{2n}$
, let
$g(D)$
be the function
$g_D : [2n]^n \times [2n]^n \to 2$
defined for every
$E_0, E_1 \in [2n]^n$
by
$g_D(E_0, E_1) = 1$
if and only if
$\,f(\{x_i : i \in E_0\}) = f(\{x_i : i \in E_1\})$
.
Lemma 4.13. An infinite set H is g-homogeneous if and only if it is f-canonical.
Proof.
$\Rightarrow $
: Suppose first that H is g-homogeneous, say for color
$c : [2n]^n \times [2n]^n \to 2$
.
Claim 1: There is a finite set
$U \subseteq \{0, \dots, n-1\}$
such that for every
$E_0 = \{a_0 < \dots < a_{n-1}\} \in [2n]^n$
and
$E_1 = \{b_0 < \dots < b_{n-1}\} \in [2n]^n$
,
$c(E_0, E_1) = 1$
if and only if for every
$i \in U$
,
$a_i = b_i$
. Fix
$E_0$
and
$E_1$
. By the classical canonical Ramsey theorem, there is an infinite subset
$H_1 \subseteq H$
which is f-canonical with some witness set
$U \subseteq \{0, \dots, n-1\}$
. Note that
$c(E_0, E_1) = 1$
if and only if for every
$F = \{z_0 < \dots < z_{2n-1}\} \in [H_1]^{2n}$
, letting
$D_0 = \{z_i : i \in E_0\}$
and
$D_1 = \{z_i : i \in E_1\}$
,
$\,f(D_0) = f(D_1)$
. Since
$H_1$
is f-canonical with witness U, then
$\,f(D_0) = f(D_1)$
if and only if for every
$i \in U$
, the ith element of
$D_0$
equals the ith element of
$D_1$
, if for every
$i \in U$
,
$a_i = b_i$
. This proves Claim 1. From now on, fix the set U.
Claim 2: H is f-canonical with witness U. Fix some
$D_0, D_1 \in [H]^n$
, and let
$F = \{z_0 < \dots < z_{2n-1}\} \in [H]^{2n}$
be some set such that
$D_0 \cup D_1 \subseteq F$
. Let
$E_0 = \{i < 2n : z_i \in D_0\}$
and
$E_1 = \{i < 2n : z_i \in D_1\}$
. By definition of g,
$\,f(D_0) = f(D_1)$
if and only if
$c(E_0, E_1) = 1$
. By Claim 1,
$c(E_0, E_1) = 1$
if and only if for every
$i \in U$
, the ith element of
$E_0$
equals the ith element of
$E_1$
. Therefore,
$\,f(D_0) = f(D_1)$
if and only if for every
$i \in U$
, the ith element of
$D_0$
equals the ith element of
$D_1$
. This proves Claim 2.
$\Leftarrow $
: Suppose now that H is f-canonical, with witness
$U \subseteq \{0, \dots, n-1\}$
. We claim that H is g-homogeneous. Fix some
$D = \{z_0 < \dots < z_{2n-1}\} \in [H]^{2n}$
and let
$c = f(D)$
, with
$c : [2n]^n \times [2n]^n \to 2$
. We claim that c is fully specified by U. Fix some
$E_0, E_1 \in [2n]^n$
and let
$D_0 = \{z_i : i \in E_0\}$
and
$D_1 = \{z_i : i \in E_1\}$
. Then
$c(E_0, E_1) = 1$
if and only if
$\,f(D_0) = f(D_1)$
, and by f-canonicity of H, this holds if and only if for every
$i \in U$
, the ith element of
$D_0$
equals the ith element of
$D_1$
, which again holds if and only if the ith element of
$E_0$
equals the ith element of
$E_1$
. This property depends only on
$E_0$
,
$E_1$
and U. Therefore c is unique.⊣
We say that a set H is g-comparing if g behaves as the coding of some function f, that is, for every
$F_{1,2} = \{x_0 < \dots < x_{2n-1}\} \in [H]^{2n}$
,
$F_{1,3} = \{y_0 < \dots < y_{2n-1}\} \in [H]^{2n}$
and
$F_{2,3} = \{z_0 < \dots < z_{2n-1}\} \in [H]^{2n}$
and
$E^1_{1,2}, E^1_{1,3}, E^2_{1,2}, E^2_{2,3}, E^3_{1,3}, E^3_{2,3}$
such that
$\{x_i : i \in E^1_{1,2} \} = \{ y_i : i \in E^1_{1,3} \}$
,
$\{x_i : i \in E^2_{1,2} \} = \{ z_i : i \in E^2_{2,3} \}$
and
$\{y_i : i \in E^3_{1,3}\} = \{z_i : i \in E^3_{2,3}\}$
, if
$g(F_{1,2})(E^1_{1,2},E^2_{1,2}) = g(F_{2,3})(E^2_{2,3}, E^3_{2,3}) = 1$
then
$g(F_{1,3})(E^1_{1,3}, E^3_{1,3}) = 1$
. Moreover
$g(F_{1,2})(E^1_{1,2},E^2_{1,2}) = 1$
and if
$g(F_{1,2})(E^1_{1,2},E^2_{1,2}) = 1$
then
$g(F_{1,2})(E^2_{1,2},E^1_{1,2}) = 1$
. Let
$V_{\operatorname {\mathrm {{\mathsf {CRT}}}}^n}$
be the set of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^{2n}_\ell $
-patterns (where
$\ell $
is the number of functions of type
$[2n]^n \times [2n]^n \to 2$
) forbidding the sets which are non g-comparing. Then
$\operatorname {\mathrm {{\mathsf {CRT}}}}^n$
can be seen as the promise Ramsey-like statement
${\operatorname {\mathrm {{\mathsf {RT}}}}}^{2n}_\ell (V_{\operatorname {\mathrm {{\mathsf {CRT}}}}^n}, W_{{\operatorname {\mathrm {{\mathsf {RT}}}}}^{2n}_\ell })$
.
A function
$\,f : [\omega ]^n \to \omega $
is k-bounded if for every
$c \in \omega $
,
$|f^{-1}(c)| \leq k$
, that is, each color appears at most k times. A set
$H \subseteq \omega $
is an f-rainbow if f is injective over
$[H]^n$
.
Statement 4.14 (Rainbow Ramsey theorem)
$\operatorname {\mathrm {{\mathsf {RRT}}}}^n_k$
: Every k-bounded coloring
$\,f : [\omega ]^n \to \omega $
has an infinite f-rainbow.
Cisma and Mileti [Reference Csima and Mileti7] first studied the rainbow Ramsey theorem in the context of reverse mathematics. Wang [Reference Wang29, theorem 4.2] proved that
$\operatorname {\mathrm {{\mathsf {RRT}}}}^n_2$
follows directly from
$\operatorname {\mathrm {{\mathsf {FS}}}}^n$
, thus that
$\operatorname {\mathrm {{\mathsf {RRT}}}}^n_2$
admits strong cone avoidance for every
$n \geq 1$
. Later, the author [Reference Patey22, theorem 4.6] proved that
$\operatorname {\mathrm {{\mathsf {FS}}}}^n$
follows from
$\operatorname {\mathrm {{\mathsf {RRT}}}}^{2n+1}_2$
. Given a k-bounded function
$\,f : [\omega ]^n \to \omega $
, we can define
$g : [\omega ]^{2n} \to [2n]^n \times [2n]^n \to 2$
as for the canonical Ramsey theorem. An infinite set H is g-homogeneous if and only if it is an f-rainbow. Then letting
$V_{\operatorname {\mathrm {{\mathsf {RRT}}}}^n_k}$
be the set of
${\operatorname {\mathrm {{\mathsf {RT}}}}}^{2n}_\ell $
-patterns which force the sets to be g-comparing and to code a k-bounded function, the rainbow Ramsey theorem can be seen as the promise Ramsey-like statement
${\operatorname {\mathrm {{\mathsf {RT}}}}}^{2n}_\ell (V_{\operatorname {\mathrm {{\mathsf {RRT}}}}^n_k}, W_{{\operatorname {\mathrm {{\mathsf {RT}}}}}^{2n}_\ell })$
.
5 Open questions
This article provides an extensive analysis of cone avoidance for Ramsey-like and promise Ramsey-like theorems. As a general study of a property over a class of problems, there are two main axis of improvements: broadening the result to a larger class of problems, and studying other properties over this class. We now detail both directions.
5.1 Structural Ramsey theory
We restricted our analysis to consequences of Ramsey’s theorem, thus to instances of the form
$\,f : [\omega ]^n \to k$
. Although this formalism encompasses already a larger class of problems, such as
$\omega $
-colorings, some statements studied in reverse mathematics do not fit into this framework, although they could arguably be considered as Ramsey-like. The most notable example is the tree theorem [Reference Chubb, Hirst and McNicholl5] (
$\operatorname {\mathrm {{\mathsf {TT}}}}^n_k$
), which asserts, for every k-coloring of the n-tuples of comparable nodes of the perfect tree
$2^{<\omega }$
, the existence of an infinite perfect subtree whose n-tuples of comparable nodes are monochromatic. The author and Dzhafarov [Reference Dzhafarov and Patey10] proved that
$\operatorname {\mathrm {{\mathsf {TT}}}}^1_k$
admits strong cone avoidance and
$\operatorname {\mathrm {{\mathsf {TT}}}}^2_k$
cone avoidance, contrary to
$\operatorname {\mathrm {{\mathsf {TT}}}}^3_k$
.
Ramsey’s theorem and the tree theorem belong to a broad field of research called structural Ramsey theory. Given two model-theoretic structures
$\mathcal {A}$
and
$\mathcal {F}$
, let
${\mathcal {A} \choose \mathcal {F}}$
denote the set of all the embeddings of
$\mathcal {F}$
into
$\mathcal {A}$
. Structural Ramsey theory studies, among others, the conditions under which, given a coloring
$\,f : {\mathcal {A} \choose \mathcal {F}} \to k$
, there exists a sub-copy
$\mathcal {B}$
of
$\mathcal {A}$
such that f is monochromatic over
${\mathcal {B} \choose \mathcal {F}}$
. In the case of Ramsey’s theorem for n-tuples,
$\mathcal {A}$
is
$\omega $
, and
$\mathcal {F}$
is a finite set of size n. One would like to extend the study of this article to other structures such as perfect trees.
Other weakness notions have been proven to be very useful in reverse mathematics. It would be interesting to extend this analysis to these notions. We detail some of the remaining questions.
5.2 PA avoidance
Among the five main subsystems of second-order arithmetics studied in reverse mathematics, weak König’s lemma (
$\operatorname {\mathrm {{\mathsf {WKL}}}}$
) captures compactness arguments. Weak König’s lemma asserts that every infinite binary tree admits an infinite path. The question whether
${\operatorname {\mathrm {{\mathsf {RT}}}}}^2_2$
implies
$\operatorname {\mathrm {{\mathsf {WKL}}}}$
was a long-standing open question, until Liu [Reference Liu17] answered it negatively using the notion of PA avoidance. A Turing degree
$\mathbf {d}$
is PA relative to X if every infinite X-computable binary tree has an infinite path bounded by
$\mathbf {d}$
.
Definition 5.1 (PA avoidance)
A problem
$\mathsf {P}$
admits PA avoidance if for every set Z of non-PA degree and every Z-computable
$\mathsf {P}$
-instance X, there is a
$\mathsf {P}$
-solution Y to X such that
$Z \oplus Y$
is of non-PA degree.
The notion of strong PA avoidance is defined accordingly. Liu [Reference Liu17] proved that
${\operatorname {\mathrm {{\mathsf {RT}}}}}^1_2$
admits strong PA avoidance and deduced that
${\operatorname {\mathrm {{\mathsf {RT}}}}}^2_2$
admits PA avoidance.
Question 5.2. What Ramsey-like statements admit PA and strong PA avoidance, respectively?
The cone avoidance analysis for Ramsey-like statements strongly relies on finding the exact bounds for which the thin set theorems admits cone avoidance. The author [Reference Patey20] proved that for every
$n \geq 1$
, there is some
$\ell \in \omega $
such that
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_{<\infty, \ell }$
admits strong PA avoidance.
5.3 Preservation of hyperimmunities
A very important and successful computability-theoretic notion to separate statements in reverse mathematics is simultaneous preservation of hyperimmunities. A function
$\,f : \omega \to \omega $
is X-hyperimmune if it is not dominated by any X-computable function.
Definition 5.3 (Preservation of hyperimmunities)
A problem
$\mathsf {P}$
admits preservation of k hyperimmunities if for every set Z, every k-tuple of Z-hyperimmune functions
$\,f_0, \dots, f_{k-1}$
and every Z-computable
$\mathsf {P}$
-instance X, there is a
$\mathsf {P}$
-solution Y such that all the functions
$\,f_0, \dots, f_{k-1}$
are
$Z \oplus Y$
-hyperimmune.
Again, the notion of strong preservation of k hyperimmunities is defined accordingly. The analysis of §2 actually shows that whenever
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W) \not \leq _{id} {\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
, then
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_k(W)$
does not admit strong preservation of one hyperimmunity. Actually, the proof of Cholak and Patey [Reference Cholak and Patey4] that
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_{<\infty, C_n}$
admits strong cone avoidance can be adapted to prove that
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_{<\infty, C_n}$
admits strong preservation of one hyperimmunity. By a similar analysis, we can prove that
${\mathsf {SCA}}\mbox {-}{\mathsf {RT}}^n_k$
admits strong preservation of 1 hyperimmunity, and thus that the Ramsey-like statements which admit strong preservation of one hyperimmunity and strong cone avoidance coincide. The situation becomes different when preserving two hyperimmunities. Indeed, the author [Reference Patey21, lemmas 25 and 27] proved that
${\operatorname {\mathrm {{\mathsf {RT}}}}}^1_2$
does not admit strong preservation of two hyperimmunities, while Dzhafarov and Jockusch [Reference Dzhafarov and Jockusch9] proved that
${\operatorname {\mathrm {{\mathsf {RT}}}}}^1_2$
can strongly avoid multiple cones simultaneously.
Question 5.4. What Ramsey-like statements admit preservation and strong preservation of k hyperimmunities, respectively?
The author [Reference Patey24, Theorem 8.4.1] proved that for every
$k \in \omega $
and
$n \geq 1$
, there is some
$\ell \in \omega $
such that
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_{<\infty, \ell }$
admits preservation of k hyperimmunities.
5.4 Jump cone avoidance
The question of the relation between stable Ramsey’s theorem for pairs and cohesiveness [Reference Patey23] motivated the study of jump computation and yielded the notion of jump cone avoidance which is similar to the notion of cone avoidance, but for jump computation.
Definition 5.5 (Jump cone avoidance)
A problem
$\mathsf {P}$
admits jump cone avoidance if for every set Z, every non-
$\Delta ^0_2(Z)$
set C, and every Z-computable
$\mathsf {P}$
-instance X, there is a
$\mathsf {P}$
-solution Y such that C is not
$\Delta ^0_2(Z \oplus Y)$
.
Once again, the notion of strong jump cone avoidance is defined accordingly by dropping the effectiveness restraint on the
$\mathsf {P}$
-instance. Recently, Monin and Patey [Reference Monin and Patey19, Theorem 4.1] proved that
${\operatorname {\mathrm {{\mathsf {RT}}}}}^1_2$
admits strong jump cone avoidance. It is however currently unknown whether for every
$n \geq 1$
, there is some
$\ell \in \omega $
such that
${\operatorname {\mathrm {{\mathsf {RT}}}}}^n_{<\infty, \ell }$
admits strong jump cone avoidance.
Question 5.6. What Ramsey-like statements admit jump cone and strong jump cone avoidance, respectively?
Acknowledgments
The author is thankful for the anonymous referee for this helpful comments and improvement suggestions. The author was partially supported by grant ANR ACTC #ANR-19-CE48-0012-01.
