Coloring the rationals in reverse mathematics

Abstract

Ramsey’s theorem for pairs asserts that every 2-coloring of the pairs of integers has an infinite monochromatic subset. In this paper, we study a strengthening of Ramsey’s theorem for pairs due to Erdős and Rado, which states that every 2-coloring of the pairs of rationals has either an infinite 0-homogeneous set or a 1-homogeneous set of order type η, where η is the order type of the rationals. This theorem is a natural candidate to lie strictly between the arithmetic comprehension axiom and Ramsey’s theorem for pairs. This Erdős–Rado theorem, like the tree theorem for pairs, belongs to a family of Ramsey-type statements whose logical strength remains a challenge.

Keywords

Reverse mathematics Ramsey computable reduction

1. Introduction

In this paper, we investigate the reverse mathematics of a well-known theorem due to Erdős and Rado about 2-colorings of pairs of rationals. This theorem is a natural strengthening of Ramsey’s theorem for pairs and two colors. We say that an order type α is Ramsey, and write $α \to {(α)}_{2}^{2}$ , if for every coloring $f : {[L]}^{2} \to 2$ , where L is a linear order of order type α, there is a homogeneous set H such that $(H, ⩽_{L})$ has order type α. Ramsey’s theorem for pairs and two colors asserts that ω is Ramsey. It turns out that ω and $ω^{*}$ are the only countable Ramsey order types. In particular, $η \to {(η)}_{2}^{2}$ does not hold, where η is the order type of the rationals. A standard counterexample is as follows. Fix a one-to-one map $i : Q \to N$ . Define $f : {[Q]}^{2} \to 2$ by letting $\begin{matrix} f (x, y) = \{\begin{matrix} 0 & if x <_{Q} y \land i (x) < i (y); \\ 1 & if x <_{Q} y \land i (x) > i (y) . \end{matrix} \end{matrix}$ A homogeneous set of order type η would give an embedding of $Q$ into ω (with color 0) or $ω^{*}$ (with color 1), which is impossible. Even though Ramsey’s theorem for rationals fails, Erdős and Rado [7, Theorem 4, p. 427] proved the following Ramsey-type theorem (see also Rosenstein [17, Theorem 11.7, p. 207]).

Theorem 1.1 (Erdős–Rado theorem).

The partition relation $η \to {(ℵ_{0}, η)}^{2}$ holds.

The relation $η \to {(ℵ_{0}, η)}^{2}$ asserts that for every coloring $f : {[L]}^{2} \to 2$ , where L is a linear order of order type η, there is either an infinite 0-homogeneous set or a 1-homogeneous set H such that $(H, ⩽_{Q})$ has order type η.

We study Theorem 1.1 within the framework of reverse mathematics (see Simpson [21]). Reverse mathematics is a vast mathematical program whose goal is to study the logical strength of ordinary theorems in terms of set existence axioms. It uses the framework of subsystems of second-order arithmetic, with the base theory ${RCA}_{0}$ (recursive comprehension axiom). ${RCA}_{0}$ is composed of $P^{-}$ , that is, the basic first-order Peano axioms for 0, 1, +, ×, <, together with $Δ_{1}^{0}$ -comprehension and $Σ_{1}^{0}$ -induction with number and set parameters. ${RCA}_{0}$ is usually thought of as capturing computable mathematics. It turns out that the large majority of countable mathematics can be proven in ${ACA}_{0}$ , where ${ACA}_{0}$ is ${RCA}_{0}$ together with arithmetic comprehension. See Hirschfeldt [5] for a gentle presentation of the reverse mathematics below ${ACA}_{0}$ .

We formalize Theorem 1.1 in ${RCA}_{0}$ as follows.

For every coloring $f : {[Q]}^{2} \to 2$ there exists either an infinite 0-homogeneous set or a 1-homogeneous set H such that $(H, ⩽_{Q})$ is dense.

Here

Q

is any fixed primitive recursive presentation of the rationals. We may safely assume that the domain of

Q

N

. Note that provably in

{RCA}_{0}

every two (countable) linear orders of order type η are isomorphic and any dense linear order obviously contains a linear order of order type η. Therefore

{ER}_{2}^{2}

is provably equivalent over

{RCA}_{0}

to the statement of Theorem 1.1.

In order to study ${ER}_{2}^{2}$ we also consider a version of the infinite pigeonhole principle over the rationals, namely the statement:

For every n and for every n-coloring $f : Q \to n$ there exists a dense homogeneous set.

The early study of reverse mathematics has led to the observation that most of the theorems happen to be equivalent to five main subsystems of second-order arithmetic that Montalbán [13] called the “Big Five”. However, Ramsey’s theory provides many statements escaping this observation. Perhaps the most well-known example is Ramsey’s theorem for pairs and two colors ( ${RT}_{2}^{2}$ ). The effective analysis of Ramsey’s theorem was started by Jockusch [10]. In the framework of reverse mathematics, Simpson (see [21]), building on Jockusch results, proved that whenever $n ⩾ 3$ and $k ⩾ 2$ , ${RT}_{k}^{n}$ is equivalent to ${ACA}_{0}$ over ${RCA}_{0}$ . The case of ${RT}_{2}^{2}$ had been a long-standing open problem until Seetapun [19] proved that ${RT}_{2}^{2}$ is strictly weaker than ${ACA}_{0}$ over ${RCA}_{0}$ . Cholak, Jockusch and Slaman [1] paved the way to the reverse mathematics analysis of Ramsey’s theorem for pairs. Since then, many consequences of Ramsey’s theorem for pairs have been studied, leading to a whole zoo of independent statements. However, no natural statement besides Ramsey’s theorem for pairs ( ${RT}^{2}$ ) is known to be strictly between ${ACA}_{0}$ and ${RT}_{2}^{2}$ over ${RCA}_{0}$ . The only known candidate is the tree theorem for pairs ( ${TT}_{2}^{2}$ ) studied in [2–4,15]. We show that ${ER}_{2}^{2}$ also lies between ${ACA}_{0}$ and ${RT}_{2}^{2}$ , and so represents another candidate, arguably more natural than ${TT}_{2}^{2}$ .

Although no relation is known between them, ${TT}_{2}^{2}$ and ${ER}_{2}^{2}$ share some essential combinatorial features and put the emphasis on a new family of Ramsey-type theorems, characterized by what we call a disjoint extension commitment. See Section 5 for a discussion on this notion. Some separations known for variants of ${TT}_{2}^{2}$ are essentially due to this common feature, which enables us to prove the same separations for variants of ${ER}_{2}^{2}$ . In particular, we prove that ${ER}_{2}^{2}$ does not computably reduce to Ramsey’s theorem for pairs with an arbitrary number of colors ( ${RT}^{2}$ ). However, we cannot simply adapt this “one-step separation” to a separation over ω-models, and in particular over ${RCA}_{0}$ , as in the case of ${TT}_{2}^{2}$ [15]. This is the first known example of such an inability. Indeed, a diagonalization against an ${RT}_{4}^{2}$ -instance is similar to a diagonalization against two ${RT}_{2}^{2}$ -instances. Therefore, diagonalizing against ${RT}^{2}$ has some common flavor with a separation over standard models.

Among the consequences of Ramsey’s theorem for pairs, Ramsey’s theorem for singletons ( ${RT}^{1}$ ), also known as the infinite pigeonhole principle, is of particular interest. ${RT}^{1}$ happens to be equivalent to the $Σ_{2}^{0}$ bounding scheme (see Hirst [9]). The $Σ_{2}^{0}$ bounding scheme ( $B Σ_{2}^{0}$ ) is formally defined as $\begin{matrix} (\forall x < a) \exists y φ (x, y, a) ⟹ \exists b (\forall x < a) (\exists y < b) φ (x, y, n), \end{matrix}$ where φ is any $Σ_{2}^{0}$ formula. One may think of $B Σ_{2}^{0}$ as asserting that the finite union of finite sets is finite (see for instance [8]). We show that ${ER}^{1}$ , the corresponding pigeonhole principle for rationals, is strictly stronger than $B Σ_{2}^{0}$ , and hence has the same reverse mathematics status as the tree theorem for singletons ( ${TT}^{1}$ ) [3].

For the purpose of separating ${ER}_{2}^{2}$ from ${RT}^{2}$ over computable reducibility, we also introduce the asymmetric version of ${ER}^{1}$ for two colors, namely $a - {ER}_{2}^{1}$ , stating that for every partition $A_{0} \cup A_{1} = Q$ of the rationals there exists either an infinite subset of $A_{0}$ or a dense subset of $A_{1}$ . Indeed, we show the existence of a $Δ_{2}^{0}$ -instance of $a - {ER}_{2}^{1}$ , and hence of a computable instance of ${ER}_{2}^{2}$ , which does not reduce to any computable instance of ${RT}^{2}$ .

1.1. Definitions and notation

String. A string is an ordered tuple of bits $b_{0}, \dots, b_{n - 1}$ , that is, such that $b_{i} < 2$ for every $i < n$ . The empty string is written $⟨ \cdot ⟩$ . A real is an infinite listing of bits $b_{0}, b_{1}, \dots$ . Given $s \in ω$ , $2^{s}$ is the set of strings of length s and $2^{< s}$ is the set of strings of length $< s$ . Similarly, $2^{< ω}$ is the set of finite strings and $2^{ω}$ is the set of reals. Given a string $σ \in 2^{< ω}$ , we denote by $| σ |$ its length. Given two strings $σ, τ \in 2^{< ω}$ , we write $σ^{⌢} τ$ for the concatenation of σ and τ, and we say that σ is a prefix of τ (written $σ ⪯ τ$ ) if there exists a string $ρ \in 2^{< ω}$ such that $σ^{⌢} ρ = τ$ . Given a real X, we write $σ ≺ X$ if $σ = X ↾ n$ for some $n \in ω$ , where $X ↾ n$ denotes the restriction of X to its first n elements.

Tree, path. A binary tree $T \subseteq 2^{< ω}$ is a set downward-closed under the prefix relation. A real P is a path though T if for every $σ ≺ P$ , $σ \in T$ .

Sets, partitions. Given two sets A and B, we denote by $A < B$ the formula $(\forall x \in A) (\forall y \in B) [x < y]$ and by $A \subseteq^{*} B$ the formula $(\forall^{\infty} x \in A) [x \in B]$ , meaning that A is included in B up to finitely many elements. Given a set X and some integer k, a k-partition of X is a k-uple of pairwise disjoint sets $A_{0}, \dots, A_{k - 1}$ such that $A_{0} \cup \dots \cup A_{k - 1} = X$ . A Mathias condition is a pair $(F, X)$ where F is a finite set, X is an infinite set and $F < X$ . A condition $(F_{1}, X_{1})$ extends $(F, X)$ (written $(F_{1}, X_{1}) ⩽ (F, X)$ ) if $F \subseteq F_{1}$ , $X_{1} \subseteq X$ and $F_{1} ∖ F \subset X$ . A set G satisfies a Mathias condition $(F, X)$ if $F \subset G$ and $G ∖ F \subseteq X$ .

2. The Erdős–Rado theorem in reverse mathematics

We start off the analysis of the Erdős–Rado theorem by proving that the statement ${ER}_{2}^{2}$ lies between ${ACA}_{0}$ and ${RT}_{2}^{2}$ . On the lower bound hand, ${ER}_{2}^{2}$ can be seen as an immediate strengthening of ${RT}_{2}^{2}$ . The upper bound is an effectivization of the original proof of ${ER}_{2}^{2}$ by Erdős and Rado in [7].

Lemma 2.1 ( ${RCA}_{0}$ ).

${ER}_{2}^{2} \to {RT}_{2}^{2}$ .

Proof.
An instance of ${RT}_{2}^{2}$ can be regarded as an instance of ${ER}_{2}^{2}$ . Moreover, provably in ${RCA}_{0}$ , a dense set is infinite. □

The rest of this section is devoted to show that ${ER}_{2}^{2}$ is provable in ${ACA}_{0}$ . For this purpose, we give the following definition.
Definition 2.2 ( ${RCA}_{0}$ ).

By interval we mean a set of the form $I = {(x, y)}_{Q}$ for $x, y \in Q$ . We say that $A \subseteq Q$ is somewhere dense if A is dense in some interval of $Q$ , i.e., there exists an interval I such that for all intervals $J \subseteq I$ we have that $A \cap J \neq \emptyset$ . We call A nowhere dense otherwise.

Notice that the above notion of nowhere dense is the usual topological notion with respect to the order topology of $Q$ . In general, the nowhere dense sets of a topological space form an ideal. This is crucial in the proof by Erdős and Rado. For this reason, we also use the terminology positive and small for somewhere dense and nowhere dense respectively. In ${RCA}_{0}$ we can show that nowhere dense subsets of $Q$ are small, meaning that:

If $A \subseteq Q$ is small and $B \subseteq A$ , then B is small;

If $A, B \subseteq Q$ are small, then $A \cup B$ is small.

With enough induction, it is possible to generalize $(2)$ to finitely many sets.

Lemma 2.3 ( ${RCA}_{0} + I Σ_{2}^{0}$ ).

If $A_{i}$ is a small subset of $Q$ for all $i < n$ , then $⋃_{i < n} A_{i}$ is small.

Proof.
Suppose that $A_{i}$ is small for every $i < n$ . Fix an interval I. We aim to show that $A^{n} = ⋃_{i < n} A_{i}$ is not dense in I. By $Σ_{2}^{0}$ -induction we prove that for all $i ⩽ n$ there exists an interval $J \subseteq I$ such that $A^{i} \cap J = \emptyset$ , where $A^{i} = ⋃_{j < i} A_{j}$ . For $i = n$ we have the desired conclusion. The case $i = 0$ is trivial. Suppose $i + 1 ⩽ n$ . By induction there exists an interval $J \subseteq I$ such that $A^{i} \cap J = \emptyset$ . By the assumption $A_{i}$ is small and so there exists an interval $K \subseteq J$ such that $A_{i} \cap K = \emptyset$ . It follows that $A^{i + 1} \cap K = (A^{i} \cup A_{i}) \cap K = \emptyset$ . □
Theorem 2.4.
${ER}_{2}^{2}$ is provable in ${ACA}_{0}$ .
Proof.
Let $f : {[Q]}^{2} \to 2$ be given. For any $x \in Q$ , let $Red (x) = {y \in Q ∖ {x} : f (x, y) = 0}$ . Define $Blue (x)$ accordingly. We say that $A \subseteq Q$ is red-admissible if there exists some $x \in A$ such that $A \cap Red (x)$ is positive. Case I.
Every positive subset of $Q$ is red-admissible. We aim to show that there exists an infinite 0-homogeneous set. We define by arithmetical recursion a sequence ${(x_{n})}_{n \in N}$ as follows. Suppose we have defined $x_{i}$ for all $i < n$ , and assume by arithmetical induction that $A_{n} = ⋂_{i < n} Red (x_{i})$ is positive, and hence red-admissible (where $⋂_{i < 0} Red (x_{i}) = Q$ ). Search for the ω-least $x_{n} \in A_{n}$ such that $A_{n} \cap Red (x_{n}) = ⋂_{i < n + 1} Red (x_{i})$ is positive. By definition, the set ${x_{n} : n \in N}$ is infinite and 0-homogeneous.
Case II.
There is a positive subset A of $Q$ which is not red-admissible. In this case, we show that there exists a dense 1-homogeneous set. Let I be a witness of A being positive. Fix an enumeration ${(I_{n})}_{n \in N}$ of all subintervals of I. Notice that by definition A intersects every $I_{n}$ .

We define by arithmetical recursion a sequence ${(x_{n})}_{n \in N}$ as follows. Let $x_{0} \in A \cap I_{0}$ . Suppose we have defined $x_{i} \in A \cap I_{i}$ for all $i < n$ . By Lemma 2.3, since every $A \cap Red (x_{i})$ with $i < n$ is small, it follows that $E = ⋃_{i < n} (A \cap Red (x_{i}))$ is small. Let $J \subseteq I_{n}$ be such that $E \cap J = \emptyset$ . We may safely assume that no $x_{i}$ with $i < n$ belongs to J. Since A is dense in I and $J \subseteq I$ , we can find $x_{n} \in A \cap J$ . In particular, $x_{n} \in ⋂_{i < n} Blue (x_{i})$ . Therefore ${x_{n} : n \in N}$ is dense and 1-homogeneous. □
Remark 2.5.
A similar proof shows that ${RT}_{2}^{2}$ is provable in ${ACA}_{0}$ . In fact, we can consider the ideal of finite sets of $N$ so that a positive set is just an infinite set and a red-admissible set is a set $A \subseteq N$ such that $A \cap Red (x)$ is infinite for some $x \in A$ .

3. Pigeonhole principle on $Q$

We next consider the statement ${ER}^{1}$ asserting that every finite coloring of rationals has a dense homogeneous set. The main result is that ${ER}^{1}$ is stronger than $B Σ_{2}^{0}$ over ${RCA}_{0}$ . We achieve this by adapting the model-theoretic proof of Corduan, Groszek, and Mileti [3] that separates ${TT}^{1}$ from $B Σ_{2}^{0}$ . Basically, in a model of ${RCA}_{0} + \neg I Σ_{2}^{0}$ , there are a real X and an X-recursive instance of ${ER}^{1}$ with no X-recursive solutions. Before going into the details of this proof, we establish the following simple reverse mathematics facts.

Lemma 3.1.
Over ${RCA}_{0}$ ,
${ER}_{2}^{2} \lor I Σ_{2}^{0} \to {ER}^{1}$ ;

${ER}^{1} \to {RT}^{1}$ .

Proof.
1) Let $f : Q \to n$ be a given coloring. First assume ${ER}_{2}^{2}$ , and let $g : {[Q]}^{2} \to 2$ be defined by $g (x, y) = 1$ if and only if $f (x) = f (y)$ . Provably in ${RCA}_{0}$ every one-to-one function from an infinite set is unbounded. Then by ${ER}_{2}^{2}$ there exists a dense 1-homogeneous set for g, which is homogeneous for f.

Now assume $I Σ_{2}^{0}$ and define $A_{i} = f^{- 1} (i)$ for $i < n$ . As $Q = ⋃_{i < n} A_{i}$ is positive, by Lemma 2.3, there exists $i < n$ such that $A_{i}$ is positive. From $A_{i}$ we can compute a dense i-homogeneous set.

2) is trivial. □

As in [3], the proof of our separation result consists of a few lemmas. We start by first adapting [3, Lemma 3.4] (see Lemma 3.3 below). The combinatorial core of the proof is based on the following.
Lemma 3.2 ( ${RCA}_{0}$ ).

For each $e < n$ , let $Γ_{e}$ consist of $4 n$ pairwise disjoint intervals of $Q$ . Then there exist $2 n$ pairwise disjoint intervals $⟨ I_{e, i} : e < n, i < 2 ⟩$ such that $I_{e, i} \in Γ_{e}$ for all $e < n$ and $i < 2$ .

Proof.
Let $Γ_{e}$ , $e < n$ , be given. Consider the following recursive procedure. At each stage we define $Γ_{e, s}$ for $e < n$ and $Δ_{s}$ as follows. At stage 0, $Γ_{e, 0} = Γ_{e}$ and $Δ_{0} = ⟨ \cdot ⟩$ . At stage $s + 1$ , if $| Δ_{s} | = 2 n$ or $Γ^{s} = ⋃_{e < n} Γ_{e, s}$ is empty, we are done. Otherwise search for $I \in Γ^{s}$ minimal with respect to inclusion (such an interval exists by $I Σ_{1}$ ). Add I to $Δ_{s}$ , that is, $Δ_{s + 1} = Δ_{s}^{⌢} I$ . Let e be such that $I \in Γ_{e, s}$ . If $Δ_{s}$ already contains an interval in $Γ_{e}$ , let $Γ_{e, s + 1} = \emptyset$ , otherwise let $Γ_{e, s + 1} = Γ_{e, s} ∖ {I}$ . For all $j \neq e$ , let $Γ_{j, s + 1} = {J \in Γ_{j, s} : I \cap J = \emptyset}$ . Notice that by the choice of I as minimal, at most two intervals from each $Γ_{j, s}$ with $j \neq e$ have nonempty intersection with J.

By $I Σ_{1}$ (indeed $I Σ_{0}$ ) it is easy to show that, for all $s < 2 n + 1$ , $Δ_{s}$ consists of s disjoint intervals from $⋃_{e < n} Γ_{e}$ with at most two intervals from the same $Γ_{e}$ , that every interval in $Δ_{s}$ is disjoint from any interval in $Γ^{s}$ , and that if $Δ_{s}$ does not contain 2 intervals from $Γ_{e}$ , then $Γ_{e, s}$ contains at least $4 n - 2 s$ intervals. In particular, $Δ_{2 n}$ is as desired. □
Lemma 3.3 ( ${RCA}_{0}$ ).

For every real X there exists an X-recursive function $d : N \times Q \to 2$ such that for all n and $e < n$ , if $W_{e}^{X}$ is a dense subset of $Q$ , then there exist two disjoint intervals $I_{0}, I_{1}$ such that $W_{e}^{X} \cap I_{i}$ is infinite for all $i < 2$ and $d (n, x) = i$ for all $i < 2$ and for almost every $x \in I_{i}$ .

Proof sketch.
Our strategy to defeat n-many dense sets ${A_{e} : e < n}$ is to choose $2 n$ pairwise disjoint intervals $I_{e, 0}, I_{e, 1}$ for $e < n$ so that each $I_{e, i}$ has end-points in $A_{e}$ , and assign color i to the interval $I_{e, i}$ for all $e < n$ and $i < 2$ . As we want to diagonalize against n-many potential dense sets of the form $W_{e}^{X}$ for $e < n$ and we cannot decide uniformly in n which ones are dense, we act only when some $W_{e}^{X}$ outputs $4 n + 1$ points. We then specify a set $Γ_{e}$ of $4 n$ disjoint intervals with end-points in $W_{e}^{X}$ and from each $Γ_{e}$ currently defined we choose intervals $I_{e, 0}$ and $I_{e, 1}$ as in Lemma 3.2. Every time we act, our choice of $I_{e, 0}$ and $I_{e, 1}$ might change, but this happens at most n-many times. As the actual construction is essentially the one in the proof of [3, Lemma 3.4], we leave the details to the reader. □

The next lemma is the key part of the whole argument (see [3, Proposition 3.5]).
Lemma 3.4.
Let M be a model of ${RCA}_{0} + \neg I Σ_{2}^{0}$ . Then for some real $X \in M$ there is an X-recursive (in the sense of M) coloring f of $Q$ into M-finitely many colors such that no X-recursive dense set is homogeneous for f.
Proof.
Let $X \in M$ witness the failure of $I Σ_{2}^{0}$ . Then there exists an X-recursive function $h : N^{2} \to N$ such that for some number a, the range of the partial function $h (y) = {lim}_{s \to \infty} h (y, s)$ is unbounded on ${y : y < a}$ (see also [3, Lemma 3.6]). Define $f : Q \to 2^{a}$ by $\begin{matrix} f (x) = ⟨ d (h (y, x), x) : y < a ⟩, \end{matrix}$ where $d (n, x)$ is the function of Lemma 3.3. Let $W_{e}^{X}$ be a dense subset of $Q$ . We aim to show that $W_{e}^{X}$ is not homogeneous for f. Let $y < a$ such that $h (y) > e$ . Observe that for almost every $x \in Q$ the yth bit of $f (x)$ is $d (h (y), x)$ . As $e < h (y)$ , let $I_{0}$ and $I_{1}$ be two intervals as in Lemma 3.3. Now for sufficiently large $x_{0} \in W_{e}^{X} \cap I_{0}$ and $x_{1} \in W_{e}^{X} \cap I_{1}$ we have $d (h (y, x_{i}), x_{i}) = d (h (y), x_{i}) = i$ , and hence $f (x_{0}) \neq f (x_{1})$ . □

We can finally prove the analogue of [3, Corollary 3.8], which is the main result. Theorem 3.5.
Let P be a $Π_{1}^{1}$ sentence. Then ${RCA}_{0} + P ⊢ {ER}^{1}$ if and only if ${RCA}_{0} + P ⊢ I Σ_{2}^{0}$ . In particular, ${RCA}_{0} + B Σ_{2}^{0} ⊬ {ER}^{1}$ .
Proof.
The argument is the same as in the proof of [3, Theorem 3.7]. As ${RCA}_{0} + I Σ_{2}^{0} ⊢ {ER}^{1}$ , we just need to prove one implication. Suppose that ${RCA}_{0} + P ⊬ I Σ_{2}^{0}$ , and let M be a model of ${RCA}_{0} + P$ where $I Σ_{2}^{0}$ fails. By Lemma 3.4, for some real $X \in M$ , there exists an X-recursive instance of ${ER}^{1}$ with no X-recursive solutions. Let $M^{'}$ be the submodel of M with the same first-order part as M and second-order part consisting of the reals recursive in X (in the sense of M). Therefore ${ER}^{1}$ fails in $M^{'}$ . Since $M^{'}$ has same first-order part as M, $M^{'}$ satisfies the $Π_{1}^{1}$ sentence P. As the reals of $M^{'}$ are the ones recursive in a given real of M, M satisfies ${RCA}_{0}$ . Thus ${RCA}_{0} + P ⊬ {ER}^{1}$ . □

4. ${ER}_{2}^{2}$ does not computably reduce to ${RT}_{2}^{2}$

Many proofs of $Q \to P$ over ${RCA}_{0}$ make use only of one $Q$ -instance to solve a $P$ -instance. This is the notion of computable reducibility.

Definition 4.1 (Computable reducibility).

Fix two $Π_{2}^{1}$ statements $P$ and $Q$ . $P$ is computably reducible to $Q$ (written $P ⩽_{c} Q$ ) if every $P$ -instance $X_{0}$ computes a $Q$ -instance $X_{1}$ such that for every solution Y to $X_{1}$ , $Y \oplus X_{0}$ computes a solution to $X_{0}$ .

Proving that $P ⩽_{c} Q$ is not sufficient to deduce that ${RCA}_{0} ⊢ Q \to P$ . One needs to prove that this reducibility can be formalized within ${RCA}_{0}$ , and in particular that $Σ_{1}^{0}$ -induction is sufficient to prove its validity. The fine-grained nature of computable reducibility enables one to exhibit distinctions between statements which would not have been revealed in reverse mathematics. For example, ${RT}_{k}^{2}$ and ${RT}_{k + 1}^{2}$ are equivalent over ${RCA}_{0}$ whereas ${RT}_{k + 1}^{2} ≰_{c} {RT}_{k}^{2}$ [16].

This notion of reducibility can be also seen as an intermediary step to tackle difficult separations [6]. Proving that $P ≰_{c} Q$ is simpler than separating $Q$ from $P$ over ω-models. Lerman, Solomon and Towsner [12] introduced a framework to separate Ramsey-type statements over ω-models, in which they transform a one-step diagonalization, that is, computable non-reducibility, into a separation in the sense of reverse mathematics. In this section, we prove that the Erdős–Rado theorem for pairs does not reduce to Ramsey’s theorem for pairs in one step.

Theorem 4.2.
${ER}_{2}^{2} ≰_{c} {RT}^{2}$ .

Interestingly, this diagonalization does not seem to be easily generalizable to a separation over ω-models. A reason is that the fairness property ensured by the ${ER}_{2}^{2}$ -instance does not seem to be preserved by weak König’s lemma. This is hitherto the first example of a computable non-reducibility of a principle $P$ to ${RT}^{2}$ which is not generalizable to a proof that ${RT}_{2}^{2}$ does not imply $P$ over ${RCA}_{0}$ .

The remainder of this section is devoted to a proof of Theorem 4.2. The notion of fairness presented below may have some ad-hoc flavor. It has been obtained by applying the main ideas of the framework of Lerman, Solomon and Towsner [12,14]. Thanks to an analysis of the combinatorics of Ramsey’s theorem for pairs and the Erdős–Rado theorem for pairs, we prove our computable non-reducibility result by constructing an instance of ${ER}_{2}^{2}$ ensuring the density of the diagonalizing conditions in the forcing notion of ${RT}_{2}^{2}$ . Then we abstract the diagonalization to any $Σ_{1}^{0}$ formula, to get rid of the specificities of the forcing notion of ${RT}_{2}^{2}$ in the notion of fairness preservation. See [15] for a detailed example of the various steps of this framework, leading to a separation of ${RT}_{2}^{2}$ from the tree theorem for pairs over ${RCA}_{0}$ .
Definition 4.3 (Simple partition).

A simple partition ${int}_{Q} (S)$ is a finite sequence of open intervals $(- \infty, x_{0}), (x_{0}, x_{1}), \dots, (x_{n - 1}, + \infty)$ for some set of rationals $S = {x_{0} <_{Q} \dots <_{Q} x_{n - 1}}$ . We set ${int}_{Q} (\emptyset) = {Q}$ . A simple partition $I_{0}, \dots, I_{n - 1}$ refines another simple partition $J_{0}, \dots, J_{m - 1}$ if for every $i < n$ , there is some $j < m$ such that $I_{i} \subseteq J_{j}$ . Given two simple partitions $I_{0}, \dots, I_{n - 1}$ and $J_{0}, \dots, J_{m - 1}$ , the product $\vec{I} \otimes \vec{J}$ is the simple partition $\begin{matrix} {I \cap J : I \in \vec{I} \land J \in \vec{J}} . \end{matrix}$

One can easily see that ${int}_{Q} (S)$ refines ${int}_{Q} (T)$ if $T \subseteq S$ and that ${int}_{Q} (S \cup T) = {int}_{Q} (S) \otimes {int}_{Q} (T)$ . Note that every simple partition has a finite description, since the set S and each rational has a finite description. Also note that a simple partition is not a true partition of $Q$ since the endpoints do not belong to any interval. However, we have $S \cup ⋃ {int}_{Q} (S) = Q$ .

Definition 4.4 (Matrix).

An m-by-n matrix M is a rectangular array of rationals $x_{i, j} \in Q$ such that $x_{i, j} <_{Q} x_{i, k}$ for each $i < m$ and $j < k < n$ . The ith row $M (i)$ of the matrix M is the n-tuple of rationals $x_{i, 0} < \dots < x_{i, n - 1}$ . The simple partition ${int}_{Q} (M)$ is defined by $⨂_{i < m} {int}_{Q} (M (i))$ . In particular, $⨂_{i < m} {int}_{Q} (M (i))$ refines the simple partition ${int}_{Q} (M (i))$ for each $i < m$ .

It is important to notice that an m-by-n matrix is formally a 3-tuple $⟨ m, n, M ⟩$ and not only the matrix itself M. This distinction becomes important when dealing with the degenerate cases. An m-by-0 matrix M and a 0-by-n matrix N are both empty. However, they have different sizes. In particular, we shall define the notion of M-type for a matrix, and this definition will depend on the number of columns of the matrix M, which is 0 for M, and n for N. Notice also that, for a degenerate matrix M, the simple partition ${int}_{Q} (M)$ is the singleton ${Q}$ .

Given a simple partition $\vec{I}$ , we want to classify the k-tuples of rationals according to which interval of $\vec{I}$ they belong to. This leads to the notion of $(\vec{I}, k)$ -type.

Definition 4.5 (Type).

Given a simple partition $I_{0}, \dots, I_{n - 1}$ and some $k \in ω$ , an $(\vec{I}, k)$ -type is a tuple $T_{0}, \dots, T_{k - 1}$ such that $T_{i} \in \vec{I}$ for each $i < k$ . Given an m-by-n matrix M, an M-type is an $({int}_{Q} (M), n)$ -type.

We now state two simple combinatorial lemmas which will be useful later. The first trivial lemma simply states that each m-tuple of rationals (different from the endpoints of a simple partition) belongs to a type.

Lemma 4.6.
For every simple partition $I_{0}, \dots, I_{n - 1}$ and every k-tuple of rationals $x_{0}, \dots, x_{k - 1} \in ⋃_{i < n} I_{i}$ , there is an $(\vec{I}, k)$ -type $T_{0}, \dots, T_{k - 1}$ such that $x_{j} \in T_{j}$ for each $j < k$ .
Proof.
Fix k rationals $x_{0}, \dots, x_{k - 1}$ . For each $i < k$ , there is some interval $T_{i} \in \vec{I}$ such that $x_{i} \in T_{i}$ since $x_{i} \in ⋃_{j < n} I_{j}$ . The sequence $T_{0}, \dots, T_{k - 1}$ is the desired $(\vec{I}, k)$ -type. □

The next lemma is a consequence of the pigeonhole principle.
Lemma 4.7.
For every m-by-n matrix M and every M-type $T_{0}, \dots, T_{n - 1}$ , there is an m-tuple of intervals $J_{0}, \dots, J_{m - 1}$ with $J_{i} \in {int}_{Q} (M (i))$ such that $\begin{matrix} (⋃_{j < n} T_{j}) \cap (⋃_{i < m} J_{i}) = \emptyset . \end{matrix}$
Proof.
Let $T_{0}, \dots, T_{n - 1}$ be an M-type. For every $i < m$ and $j < n$ , there is some $J \in {int}_{Q} (M (i))$ such that $T_{j} \subseteq J$ . Since $| {int}_{Q} (M (i)) | = n + 1$ , there is an interval $J_{i} \in {int}_{Q} (M (i))$ such that $(⋃_{j < n} T_{j}) \cap J_{i} = \emptyset$ . □
Definition 4.8 (Formula, valuation).

Given an m-by-n matrix M, an M-formula is a formula $φ (\vec{U}, \vec{V})$ with distinguished (finite coded) set variables $U_{j}$ for each $j < n$ and $V_{i, I}$ for each $i < m$ and $I \in {int}_{Q} (M (i))$ . An M-valuation $(\vec{R}, \vec{S})$ is a tuple of finite sets $R_{j} \subseteq Q$ for each $j < n$ and $S_{i, I} \subseteq I$ for each $i < m$ and $I \in {int}_{Q} (M (i))$ . The M-valuation $(\vec{R}, \vec{S})$ is of type $\vec{T}$ for some M-type $T_{0}, \dots, T_{n - 1}$ if moreover $R_{j} \subseteq T_{j}$ for each $j < n$ . The M-valuation $(\vec{R}, \vec{S})$ satisfies φ if $φ (\vec{R}, \vec{S})$ holds.

Given some valuation $(\vec{R}, \vec{S})$ and some integer s, we write $(\vec{R}, \vec{S}) > s$ to say that for every $x \in (⋃ \vec{R}) \cup (⋃ \vec{S})$ , $x > s$ . Following the terminology of [12], we define the notion of essentiality for a formula (an abstract requirement), which corresponds to the idea that there is room for diagonalization since the formula is satisfied by valuations which are arbitrarily far.

Definition 4.9 (Essential formula).

Given an m-by-n matrix M, an M-formula φ is essential if for every $s \in ω$ , there are an M-type $\vec{T}$ and an M-valuation $(\vec{R}, \vec{S}) > s$ of type $\vec{T}$ such that $φ (\vec{R}, \vec{S})$ holds.

The notion of fairness is defined accordingly. If some formula is essential, that is, leaves enough room for diagonalization, then there is an actual valuation which will diagonalize against the ${ER}_{2}^{2}$ -instance.

Definition 4.10 (Fairness).

Fix two sets $A_{0}, A_{1} \subseteq Q$ . Given an m-by-n matrix M, an M-valuation $(\vec{R}, \vec{S})$ diagonalizes against $A_{0}$ , $A_{1}$ if $⋃ \vec{R} \subseteq A_{1}$ and for every $i < m$ , there is some $I \in {int}_{Q} (M (i))$ such that $S_{i, I} \subseteq A_{0}$ . A set X is fair for $A_{0}$ , $A_{1}$ if for every $m, n \in ω$ , every m-by-n matrix M and every $Σ_{1}^{0, X}$ essential M-formula, there is an M-valuation $(\vec{R}, \vec{S})$ diagonalizing against $A_{0}$ , $A_{1}$ such that $φ (\vec{R}, \vec{S})$ holds.

Of course, if $Y ⩽_{T} X$ , then every $Σ_{1}^{0, Y}$ formula is $Σ_{1}^{0, X}$ . As an immediate consequence, if X is fair for some $A_{0}$ , $A_{1}$ and $Y ⩽_{T} X$ , then Y is fair for $A_{0}$ , $A_{1}$ .

Now that we have introduced the necessary terminology, we create a non-effective instance of $a - {ER}_{2}^{1}$ which will serve as a bootstrap for fairness preservation. Remember that $erps$ asserts that for every partition $A_{0} \cup A_{1} = Q$ of the rationals there exists either an infinite subset of $A_{0}$ or a dense subset of $A_{1}$ .

Lemma 4.11.
For every set C, there exists a $Δ_{2}^{0, C}$ partition $A_{0} \cup A_{1} = Q$ such that C is fair for $A_{0}$ , $A_{1}$ .
Proof.
The proof is a no-injury priority construction. Let $M_{0}, M_{1}, \dots$ be an enumeration of all m-by-n matrices and $φ_{0}, φ_{1}, \dots$ be an effective enumeration of all $Σ_{1}^{0, C}$ $M_{k}$ -formulas for every $m, n \in ω$ . We want to satisfy the following requirements for each pair of integers e, k.
$R_{e, k}$ : If the $M_{k}$ -formula $φ_{e}$ is essential, then $φ_{e} (\vec{R}, \vec{S})$ holds for some $M_{k}$ -valuation $(\vec{R}, \vec{S})$ diagonalizing against $A_{0}$ , $A_{1}$ .

The requirements are ordered via the standard pairing function $⟨ \cdot, \cdot ⟩$ . The sets $A_{0}$ and $A_{1}$ are constructed by a $C^{'}$ -computable list of finite approximations $A_{i, 0} \subseteq A_{i, 1} \subseteq \dots$ such that all elements added to $A_{i, s + 1}$ from $A_{i, s}$ are strictly greater than the maximum of $A_{i, s}$ (in the $N$ order) for each $i < 2$ . We then let $A_{i} = ⋃_{s} A_{i, s}$ which will be a $Δ_{2}^{0, C}$ set. At stage 0, set $A_{0, 0} = A_{1, 0} = \emptyset$ . Suppose that at stage s, we have defined two disjoint finite sets $A_{0, s}$ and $A_{1, s}$ such that
$A_{0, s} \cup A_{1, s} = {[0, b]}_{N}$ for some integer $b ⩾ s$ ;

$R_{e^{'}, k^{'}}$ is satisfied for every $⟨ e^{'}, k^{'} ⟩ < s$ .
Let $R_{e, k}$ be the requirement such that $⟨ e, k ⟩ = s$ . Decide $C^{'}$ -computably whether there are some $M_{k}$ -type $\vec{T}$ and some $M_{k}$ -valuation $V = (\vec{R}, \vec{S}) > b$ of type $\vec{T}$ such that $φ_{e} (V)$ holds. If so, C-effectively fetch $\vec{T} = T_{0}, \dots, T_{n - 1}$ and such a $(\vec{R}, \vec{S}) > b$ . Let d be an upper bound (in the $N$ order) on the rationals in $(\vec{R}, \vec{S})$ . By Lemma 4.7, for each $i < m$ , there is some $J_{i} \in {int}_{Q} (M (i))$ such that $\begin{matrix} (⋃_{j < n} T_{j}) \cap (⋃_{i < m} J_{i}) = \emptyset . \end{matrix}$ Set $A_{0, s + 1} = A_{0, s} \cup ⋃_{i < m} J_{i} \cap {(b, d]}_{N}$ and $A_{1, s + 1} = {[0, d]}_{N} ∖ A_{0, s + 1}$ . This way, $A_{0, s + 1} \cup A_{1, s + 1} = {[0, d]}_{N}$ . By the previous equation, $⋃_{j < n} T_{j} \cap {(b, d]}_{N} \subseteq {[0, d]}_{N} ∖ A_{0, s + 1}$ and the requirement $R_{e, k}$ is satisfied. If no such $M_{k}$ -valuation is found, the requirement $R_{e, k}$ is vacuously satisfied. Set $A_{0, s + 1} = A_{0, s} \cup {b + 1}$ and $A_{1, s + 1} = A_{1, s}$ . This way, $A_{0, s + 1} \cup A_{1, s + 1} = {[0, b + 1]}_{N}$ . In any case, go to the next stage. This finishes the construction. □
Lemma 4.12.
If X is fair for some sets $A_{0}, A_{1} \subseteq Q$ , then X computes neither an infinite subset of $A_{0}$ , nor a dense subset of $A_{1}$ .
Proof.
Since fairness is downward-closed under Turing reducibility, it suffices to prove that if X is infinite and fair for $A_{0}$ , $A_{1}$ , then it intersects both $A_{0}$ and $A_{1}$ .

We first prove that X intersects $A_{1}$ . Let M be the 0-by-1 matrix and $φ (U)$ be the $Σ_{1}^{0, X}$ M-formula which holds if $U \cap X \neq \emptyset$ . The only M-type is $Q$ and since X is infinite, φ is essential. By fairness of X, there is an M-valuation R diagonalizing against $A_{0}$ , $A_{1}$ such that $φ (R)$ holds. By definition of diagonalization, $R \subseteq A_{1}$ . Since $R \cap X \neq \emptyset$ , this shows that $X \cap A_{1} \neq \emptyset$ .

We now prove that X intersects $A_{0}$ . Let M be the 1-by-0 matrix and $φ (V)$ be the $Σ_{1}^{0, X}$ M-formula which holds if $V \cap X \neq \emptyset$ . The M-formula φ is essential since X is infinite. By fairness of X, there is an M-valuation S diagonalizing against $A_{0}$ , $A_{1}$ such that $φ (S)$ holds. By definition of diagonalization, $S \subseteq A_{0}$ . Since $S \cap X \neq \emptyset$ , this shows that $X \cap A_{0} \neq \emptyset$ . □

Note that we did not use the fact that X is dense to make sure it intersects $A_{0}$ . Density will be useful in the proof of Theorem 4.14.
Definition 4.13.
A Scott set is a set $S \subseteq 2^{ω}$ such that
$(\forall X \in S) (\forall Y ⩽_{T} X) [Y \in S]$ ;

$(\forall X, Y \in S) [X \oplus Y \in S]$ ;

Every infinite, binary tree in $S$ has an infinite path in $S$ .

Theorem 4.14.
Let $A_{0}, A_{1} \subseteq Q$ and $S$ be a Scott set whose members are all fair for $A_{0}$ , $A_{1}$ . For every set $C \in S$ , every C-computable coloring $f : {[ω]}^{2} \to k$ , there is an infinite f-homogeneous set H such that $H \oplus C$ computes neither an infinite subset of $A_{0}$ , nor a dense subset of $A_{1}$ .
Proof.
The proof is by induction over the number of colors k. The case $k = 1$ is ensured by Lemma 4.12. Fix a set $C \in S$ and let $f : {[ω]}^{2} \to k$ be a C-computable coloring. If f has an infinite f-thin set $H \in S$ , that is, an infinite set over which f avoids at least one color, then $H \oplus C$ computes a coloring $g : {[ω]}^{2} \to k - 1$ such that every infinite g-homogeneous set computes relative to $H \oplus C$ an infinite f-homogeneous set. Since $H \oplus C \in S$ , by induction hypothesis, there is an infinite g-homogeneous set $H_{1}$ such that $H_{1} \oplus H \oplus C$ computes neither an infinite subset of $A_{0}$ , nor a dense subset of $A_{1}$ . So suppose that f has no infinite f-thin set in $S$ .

We construct k infinite sets $G_{0}, \dots, G_{k - 1}$ . We need therefore to satisfy the following requirements for each $p \in ω$ . $\begin{matrix} N_{p} : (\exists q_{0} > p) [q_{0} \in G_{0}] \land \dots \land (\exists q_{k - 1} > p) [q_{k - 1} \in G_{k - 1}] . \end{matrix}$ Furthermore, we want to ensure that one of the G’s computes neither an infinite subset of $A_{0}$ , nor a dense subset of $A_{1}$ . To do this, we will satisfy the following requirements for every k-tuple of integers $e_{0}, \dots, e_{k - 1}$ . $\begin{matrix} Q_{\vec{e}} : R_{e_{0}}^{G_{0}} \lor \dots \lor R_{e_{k - 1}}^{G_{k - 1}}, \end{matrix}$ where $R_{e}^{H}$ holds if $W_{e}^{H \oplus C}$ is neither an infinite subset of $A_{0}$ , nor a dense subset of $A_{1}$ .

We construct our sets $G_{0}, \dots, G_{k - 1}$ by forcing. Our conditions are variants of Mathias conditions $(F_{0}, \dots, F_{k - 1}, X)$ such that each X is an infinite set in $S$ , each $F_{i}$ is a finite set with $max (F_{i}) < min (X)$ , and the following property holds:
$(\forall i < k) (\forall x \in X) [F_{i} \cup {x} is f -homogeneous with color i]$ .
A condition $d = (E_{0}, \dots, E_{k - 1}, Y)$ extends $c = (F_{0}, \dots, F_{k - 1}, X)$ if $(E_{i}, Y)$ Mathias extends $(F_{i}, X)$ for every $i < k$ . We now prove the progress lemma, stating that we can force the G’s to be infinite. This is where we use the fact that there is no infinite f-thin set in $S$ . Lemma 4.15.
For every condition $c = (F_{0}, \dots, F_{k - 1}, X)$ , every $i < k$ and every $p \in ω$ there is some extension $d = (E_{0}, \dots, E_{k - 1}, Y)$ such that $E_{i} \cap {(p, + \infty)}_{N} \neq \emptyset$ .
Proof.
Fix c, i and p. If for every $x \in X \cap {(p, + \infty)}_{N}$ and almost every $y \in X$ , $f (x, y) \neq i$ , then X computes an infinite f-thin set, contradicting our hypothesis. Therefore, there is some $x \in X \cap {(p, + \infty)}_{N}$ such that $f (x, y) = i$ for infinitely many $y \in X$ . Let Y be the collection of such y’s. The condition $(F_{0}, \dots, F_{i - 1}, F \cup {x}, F_{i + 1}, \dots, F_{k}, Y)$ is the desired extension. □

We now prove the core lemma stating that we can satisfy each $Q$ -requirement. A condition c forces a requirement $Q$ if $Q$ holds for every set G satisfying c. Lemma 4.16.
For every condition $c = (F_{0}, \dots, F_{k - 1}, X)$ and every k-tuple of indices $\vec{e}$ , there is an extension $d = (E_{0}, \dots, E_{k - 1}, Y)$ forcing $Q_{\vec{e}}$ .
Proof.
We can assume that $W_{e_{i}}^{F_{i} \oplus C}$ has already outputted at least k elements and is either included in $A_{0}$ or in $A_{1}$ for each $i < k$ . Indeed, if c has no extension satisfying this condition, then c forces $W_{e_{i}}^{G_{i} \oplus C}$ to be finite or not to be a valid solution for some $i < k$ and therefore forces $Q_{\vec{e}}$ . For each $i < k$ , we associate the label $ℓ_{i} < 2$ and the number $p_{i}$ such that $W_{e_{i}}^{F_{i} \oplus C}$ is the $(p_{i} + 1) th$ set of this form included in $A_{ℓ_{i}}$ .

Let n be the number of sets $W_{e_{i}}^{F_{i} \oplus C}$ which are included in $A_{0}$ , and let M be the $(k - n)$ -by-n matrix such that the jth row is composed of the n first elements already outputted by the set $W_{e_{i}}^{F_{i} \oplus C}$ where $p_{i} = j$ and $ℓ_{i} = 1$ . In other words, $M (j)$ are the n first elements outputted by the jth set $W_{e_{i}}^{F_{i} \oplus C}$ included in $A_{1}$ .

Let $φ (\vec{U}, \vec{V})$ be the $Σ_{1}^{0, X \oplus C}$ formula which holds if there is a finite set $Z \subseteq X$ such that for every k-partition $Z_{0} \cup \dots \cup Z_{k - 1} = Z$ , there are some $i < k$ and some set $E \subseteq Z_{i}$ which is f-homogeneous with color i and such that either $ℓ_{i} = 0$ and $W_{e_{i}}^{(F_{i} \cup E) \oplus C} \cap U_{p_{i}} \neq \emptyset$ , or $ℓ_{i} = 1$ and $W_{e_{i}}^{(F_{i} \cup E) \oplus C} \cap V_{p_{i}, I} \neq \emptyset$ for each $I \in {int}_{Q} (M (p_{i}))$ . We have two cases.

In the first case, $φ (\vec{U}, \vec{V})$ is essential. Since $X \oplus C$ is fair for $A_{0}$ , $A_{1}$ , there is an M-valuation $(\vec{R}, \vec{S})$ diagonalizing against $A_{0}$ , $A_{1}$ such that $φ (\vec{R}, \vec{S})$ holds. By compactness and definition of diagonalization against $A_{0}$ , $A_{1}$ , there is a finite subset $D \subset X$ such that for every k-partition $D_{0} \cup \dots \cup D_{k - 1} = D$ , there are some $i < k$ and some finite set $E \subseteq D_{i}$ which is f-homogeneous with color i and such that either $ℓ_{i} = 0$ and $W_{e_{i}}^{(F_{i} \cup E) \oplus C} \cap A_{1} \neq \emptyset$ , or $ℓ_{i} = 1$ and $W_{e_{i}}^{(F_{i} \cup E) \oplus C} \cap A_{0} \neq \emptyset$ .

Each $y \in X ∖ D$ induces a k-partition $D_{0} \cup \dots \cup D_{k - 1}$ of D by setting $D_{i} = {x \in D : f (x, y) = i}$ . Since there are finitely many possible k-partitions of D, there are a k-partition $D_{0} \cup \dots \cup D_{k - 1} = D$ and an infinite X-computable set $Y \subseteq X$ such that $\begin{matrix} (\forall i < k) (\forall x \in D_{i}) (\forall y \in Y) [f (x, y) = i] . \end{matrix}$ We furthermore assume that $min (Y)$ is larger than the use of the computations. Let $i < k$ and $E \subseteq D_{i}$ be the f-homogeneous set with color i such that either $ℓ_{i} = 0$ and $W_{e_{i}}^{(F_{i} \cup E) \oplus C} \cap A_{1} \neq \emptyset$ , or $ℓ_{i} = 1$ and $W_{e_{i}}^{(F_{i} \cup E) \oplus C} \cap A_{0} \neq \emptyset$ . The condition $(F_{0}, \dots, F_{i - 1}, F_{i} \cup E, F_{i + 1}, \dots, F_{k - 1}, Y)$ is an extension of c forcing $Q_{\vec{e}}$ by the ith side.

In the second case, there is some threshold $s \in ω$ such that for every M-type $\vec{T}$ , there is no M-valuation $(\vec{R}, \vec{S}) > s$ of type $\vec{T}$ such that $φ (\vec{R}, \vec{S})$ holds. By compactness, it follows that for every M-type $\vec{T}$ , the $Π_{1}^{0, X \oplus C}$ class $C_{\vec{T}}$ of all k-partitions $Z_{0} \cup \dots \cup Z_{k - 1} = X$ such that for every $i < k$ and every finite set $E \subseteq Z_{i}$ which is f-homogeneous with color i, either $ℓ_{i} = 0$ and $W_{e_{i}}^{(F_{i} \cup E) \oplus C} \cap T_{p_{i}} \cap {(s, + \infty)}_{N} = \emptyset$ , or $ℓ_{i} = 1$ and $W_{e_{i}}^{(F_{i} \cup E) \oplus C} \cap I \cap {(s, + \infty)}_{N} = \emptyset$ for some $I \in {int}_{Q} (M (p_{i}))$ is non-empty. Since $S$ is a Scott set, for each M-type $\vec{T}$ , there is a k-partition ${\vec{Z}}^{\vec{T}} \in C_{\vec{T}}$ such that $⨁_{\vec{T}} {\vec{Z}}^{\vec{T}} \oplus X \oplus C \in S$ .

If there are some M-type $\vec{T}$ and some $i < k$ such that $ℓ_{i} = 1$ and $Z_{i}^{\vec{T}}$ is infinite, then the condition $(F_{0}, \dots, F_{k - 1}, Z_{i}^{\vec{T}})$ extends X and forces $W_{e_{i}}^{G_{i} \oplus C}$ not to be dense. So suppose that it is not the case. Let $Y \in S$ be an infinite subset of X such that for each M-type $\vec{T}$ , there is some $i < k$ such that $Y \subseteq Z_{i}^{\vec{T}}$ . Note that by the previous assumption, $ℓ_{i} = 0$ for every such i. We claim that the condition $(F_{0}, \dots, F_{k - 1}, Y)$ forces $W_{e_{i}}^{G_{i} \oplus C}$ to be finite for some $i < k$ such that $ℓ_{i} = 0$ . Suppose for the sake of contradiction that there are some rationals $x_{0}, \dots, x_{n - 1} > s$ such that $x_{p_{i}} \in W_{e_{i}}^{G_{i} \oplus C}$ for each $i < k$ where $ℓ_{i} = 0$ . Since $x_{0}, \dots, x_{n - 1} > s$ , $x_{0}, \dots, x_{n - 1} \in ⋃ {int}_{Q} (M)$ . Therefore, by Lemma 4.6, let $\vec{T}$ be the unique M-type such that $x_{j} \in T_{j}$ for each $j < n$ . By assumption, there is some $i < k$ such that $Y \subseteq Z_{i}^{\vec{T}}$ and $ℓ_{i} = 0$ . By definition of $Z_{i}^{\vec{T}}$ , $W_{e_{i}}^{G_{i} \oplus C} \cap T_{p_{i}} \cap {(s, + \infty)}_{N} = \emptyset$ , contradicting $x_{p_{i}} \in W_{e_{i}}^{G_{i} \oplus C}$ . □

Using Lemma 4.15 and Lemma 4.16, define an infinite descending sequence of conditions $c_{0} = (\emptyset, \dots, \emptyset, ω) ⩾ c_{1} ⩾ \dots$ such that for each $s \in ω$
$| F_{i, s} | ⩾ s$ for each $i < k$ ,

$c_{s + 1}$ forces $Q_{\vec{e}}$ if $s = ⟨ e_{0}, \dots, e_{k - 1} ⟩$ ,
where $c_{s} = (F_{0, s}, \dots, F_{k - 1, s}, X_{s})$ . Let $G_{i} = ⋃_{s} F_{i, s}$ for each $i < k$ . The G’s are all infinite by (i) and $G_{i}$ does not compute an $a - {ER}_{2}^{1}$ -solution to the A’s for some $i < k$ by (ii). This finishes the proof of Theorem 4.14. □

We are now ready to prove the main theorem. Proof of Theorem 4.2.
By the low basis theorem [11], there is a low set P of PA degree. By Scott [18], every PA degree bounds a Scott set. Let $S$ be a Scott set such that $X ⩽_{T} P$ for every $X \in S$ . By Lemma 4.11, there is a $Δ_{2}^{0, P}$ (hence $Δ_{2}^{0}$ ) partition $A_{0} \cup A_{1} = Q$ such that P is fair for $A_{0}$ , $A_{1}$ . In particular, every set $X \in S$ is fair for $A_{0}$ , $A_{1}$ since fairness is downward-closed under the Turing reducibility.

By Schoenfield’s limit lemma [20], there is a computable function $h : {[Q]}^{2} \to 2$ such that for each $x \in Q$ , ${lim}_{s} h (x, s)$ exists and $x \in A_{{lim}_{s} h (x, s)}$ . Note that for every infinite set D 0-homogeneous for h, $D \subseteq A_{0}$ , and for every dense set D 1-homogeneous for h, $D \subseteq A_{1}$ .

Fix a computable ${RT}^{2}$ -instance $f : {[ω]}^{2} \to k$ . In particular, $f \in S$ . By Theorem 4.14, there is an infinite f-homogeneous set H such that H computes neither an infinite subset of $A_{0}$ , nor a dense subset of $A_{1}$ . Therefore, H computes no ${ER}_{2}^{2}$ -solution to h. □

5. Discussion and questions

This Erdős–Rado theorem shares an essential feature with another strengthening of Ramsey’s theorem for pairs already studied in reverse mathematics: the tree theorem for pairs [2–4,15].

Definition 5.1 (Tree theorem).

We denote by ${[2^{< N}]}^{n}$ the collection of linearly ordered subsets of $2^{< N}$ of size n. A set $S \subseteq 2^{< N}$ is order isomorphic to $2^{< N}$ (written $S ≅ 2^{< N}$ ) if there is a bijection $g : 2^{< N} \to S$ such that for all $σ, τ \in 2^{< N}$ , $σ ⪯ τ$ if and only if $g (σ) ⪯ g (τ)$ . Given a coloring $f : {[2^{< N}]}^{n} \to k$ , a tree S is f-homogeneous if $S ≅ 2^{< N}$ and $f ↾ {[S]}^{n}$ is monochromatic. ${TT}_{k}^{n}$ is the statement “Every coloring $f : {[2^{< N}]}^{n} \to k$ has an f-homogeneous tree.”

Both ${TT}_{2}^{2}$ and ${ER}_{2}^{2}$ lie between the arithmetic comprehension axiom and ${RT}_{2}^{2}$ , but more than that, they share a disjoint extension commitment. Let us try to explain this informal notion with a case analysis.

Suppose we want to construct a computable ${RT}_{2}^{1}$ -instance $f : N \to 2$ which diagonalizes against two opponents $W_{0}^{f}$ and $W_{1}^{f}$ . After some finite amount of time, each opponent $W_{i}^{f}$ will have outputted a finite approximation of a solution to f, that is, a finite f-homogeneous set $F_{i}$ . The two opponents share a common strategy. $W_{0}^{f}$ tries to build an infinite f-homogeneous set $H_{0}$ for color 0, and $W_{1}^{f}$ tries to build an infinite f-homogeneous set $H_{1}$ for color 1. It is therefore difficult to defeat both opponents at the same time, since if from now on we set $f (x) = 1$ , $W_{1}^{f}$ will succeed in extending $F_{1}$ to an infinite f-homogeneous set, and if we always set $f (x) = 0$ , $W_{0}^{f}$ will succeed with its dual strategy.

Consider now the same situation, where we want to construct a computable ${TT}_{2}^{1}$ -instance $f : 2^{< N} \to 2$ . After some time, the opponent $W_{0}^{f}$ will have outputted a finite tree $S_{0} ≅ 2^{< b}$ which is f-homogeneous for color 0, and the opponent $W_{1}^{f}$ will have done the same with a finite tree $S_{1} ≅ 2^{< b}$ f-homogeneous for color 1. The main difference with the ${RT}_{2}^{1}$ case is that each opponent will commit to extend each leaf of his finite tree $S_{i}$ into an infinite tree isomorphic to $2^{< N}$ . In particular, for each tree $S_{i}$ , the sets $X_{σ}$ of nodes extending the leaf $σ \in S_{i}$ are pairwise disjoint. Therefore, each opponent commits to extend its partial solution to disjoint sets. Moreover, by asking b to be large enough, each opponent will commit to extend enough pairwise disjoint sets so that we can choose two of them for each opponent and operate the diagonalization without any conflict.

This combinatorial property works in the same way for ${ER}^{1}$ -instances. Indeed, in this case, each opponent will commit to extend its partial solution to pairwise disjoint intervals due to the density requirement of an ${ER}^{1}$ -solution. Since the combinatorial arguments of the Erdős–Rado theorem and the tree theorem for pairs are very similar, one may wonder whether they are equivalent in reverse mathematics.

Question 5.2.

How do ${ER}_{2}^{2}$ and ${TT}_{2}^{2}$ compare over ${RCA}_{0}$ ?

The failure of Seetapun’s argument for ${ER}_{2}^{2}$ comes from this disjoint extension commitment feature. In particular, it is hard to find a forcing notion for ${ER}_{2}^{2}$ whose conditions are extendible.

Question 5.3.

Does ${ER}_{2}^{2}$ imply ${ACA}_{0}$ over ${RCA}_{0}$ ?

${ER}^{1}$ and ${TT}^{1}$ have the same state of the art due to their common combinatorial flavor. However, when looking at their statements for pairs, ${ER}_{2}^{2}$ and ${TT}_{2}^{2}$ have a fundamental difference: ${ER}_{2}^{2}$ has only a half disjoint extension commitment feature. This weaker property prevents one from separating ${RT}_{2}^{2}$ from ${ER}_{2}^{2}$ over ${RCA}_{0}$ by adapting the argument of ${TT}_{2}^{2}$ in [15].

Question 5.4.

Does ${RT}_{2}^{2}$ imply ${ER}_{2}^{2}$ over ${RCA}_{0}$ ?

We have seen in Section 3 that the separation of $B Σ_{2}^{0}$ from ${ER}^{1}$ is directly adaptable from the separation of $B Σ_{2}^{0}$ from ${TT}^{1}$ from Corduan, Groszek, and Mileti [3], since the combinatorial core of this separation comes from this shared disjoint extension commitment. It is natural to conjecture that the status of ${ER}^{1}$ with respect to $I Σ_{2}^{0}$ will be the same as ${TT}^{1}$ .

Question 5.5.

Does ${ER}^{1}$ imply $I Σ_{2}^{0}$ over ${RCA}_{0}$ ?

It is worth mentioning that ${RCA}_{0} + I Σ_{2}^{0}$ proves a strengthening of both ${TT}^{1}$ and ${ER}^{1}$ , namely the statement “For every n and every $f : 2^{< N} \to n$ there exists a strong copy S of the full binary tree such that f is constant on S”, where by strong copy we mean an isomorphic copy of $2^{< N}$ with respect to order and minima. It is easy to see that a strong copy computes a dense subset of $2^{< N}$ , when $2^{< N}$ is equipped with the standard dense linear ordering on binary strings, i.e., the only linear order such that ${τ : τ ⪰ σ^{⌢} 0} <_{Q} σ <_{Q} {τ : τ ⪰ σ^{⌢} 1}$ for all $σ \in 2^{< N}$ . It is likely that if we can separate ${TT}^{1}$ or ${ER}^{1}$ from $I Σ_{2}^{0}$ , then we can already separate this stronger statement by essentially the same proof.

Footnotes

Acknowledgements

Emanuele Frittaion’s research is supported by the Japan Society for the Promotion of Science. Ludovic Patey is funded by the John Templeton Foundation (‘Structure and Randomness in the Theory of Computation’ project). The opinions expressed in this publication are those of the author(s) and do not necessarily reflect the views of the John Templeton Foundation.

References

P.A.

Cholak,

C.G.

Jockusch and

T.A.

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

Chubb,

J.L.

Hirst and

T.H.

McNicholl, Reverse mathematics, computability, and partitions of trees, The Journal of Symbolic Logic 74(01) (2009), 201–215. doi:10.2178/jsl/1231082309.

Corduan,

M.J.

Groszek and

J.R.

Mileti, Reverse mathematics and Ramsey’s property for trees, The Journal of Symbolic Logic 75(03) (2010), 945–954. doi:10.2178/jsl/1278682209.

D.D.

Dzhafarov,

J.L.

Hirst and

T.J.

Lakins, Ramsey’s theorem for trees: The polarized tree theorem and notions of stability, Archive for Mathematical Logic 49(3) (2010), 399–415. doi:10.1007/s00153-010-0179-6.

D.R.

Hirschfeldt, Slicing the Truth, Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore, Vol. 28, 2014.

D.D.

Dzhafarov, Strong reductions between combinatorial principles, Journal of Symbolic Logic, to appear.

Erdős and

Rado, Combinatorial theorems on classifications of subsets of a given set, Proceedings of the London Mathematical Society 3(1) (1952), 417–439. doi:10.1112/plms/s3-2.1.417.

Frittaion and

Marcone, Linear extensions of partial orders and reverse mathematics, MLQ Math. Log. Q. 58(6) (2012). doi:10.1002/malq.201200025.

J.L.

Hirst, Combinatorics in subsystems of second order arithmetic, PhD thesis, Pennsylvania State University, August 1987.

10.

C.G.

Jockusch, Ramsey’s theorem and recursion theory, Journal of Symbolic Logic 37(2) (1972), 268–280. doi:10.2307/2272972.

11.

C.G.

Jockusch and

R.I.

Soare,

Π_{1}^{0}

classes and degrees of theories, Transactions of the American Mathematical Society 173 (1972), 33–56.

12.

Lerman,

Solomon and

Towsner, Separating principles below Ramsey’s theorem for pairs, Journal of Mathematical Logic 13(02) (2013), 1350007. doi:10.1142/S0219061313500074.

13.

Montalbán, Open questions in reverse mathematics, Bulletin of Symbolic Logic 17(03) (2011), 431–454. doi:10.2178/bsl/1309952320.

14.

Patey, Iterative forcing and hyperimmunity in reverse mathematics, in: Evolving Computability,

Beckmann,

Mitrana and

Soskova, eds, Lecture Notes in Computer Science, Vol. 9136, Springer International Publishing, 2015, pp. 291–301. doi:10.1007/978-3-319-20028-6_30.

15.

Patey, The strength of the tree theorem for pairs in reverse mathematics. Journal of Symbolic Logic, to appear.

16.

Patey, The weakness of being cohesive, thin or free in reverse mathematics, Israel Journal of Mathematics, to appear. Available at: http://arxiv.org/abs/1502.03709.

17.

J.G.

Rosenstein, Linear Orderings, Pure and Applied Mathematics, Vol. 98, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1982.

18.

Scott, Algebras of sets binumerable in complete extensions of arithmetic, in: Proc. Sympos. Pure Math, Vol. 5, 1962, pp. 117–121.

19.

Seetapun and

T.A.

Slaman, On the strength of Ramsey’s theorem, Notre Dame Journal of Formal Logic 36(4) (1995), 570–582. doi:10.1305/ndjfl/1040136917.

20.

J.R.

Shoenfield, On degrees of unsolvability, Annals of Mathematics 69(03) (1959), 644–653. doi:10.2307/1970028.

21.

S.G.

Simpson, Subsystems of Second Order Arithmetic, Cambridge University Press, 2009.

Coloring the rationals in reverse mathematics

Abstract

Keywords

1. Introduction

Theorem 1.1 (Erdős–Rado theorem).

1.1. Definitions and notation

2. The Erdős–Rado theorem in reverse mathematics

Lemma 2.1 ( RCA 0 ).

Proof. An instance of RT 2 2 can be regarded as an instance of ER 2 2 . Moreover, provably in RCA 0 , a dense set is infinite. □ The rest of this section is devoted to show that ER 2 2 is provable in ACA 0 . For this purpose, we give the following definition. Definition 2.2 ( RCA 0 ).

Lemma 2.3 ( RCA 0 + I Σ 2 0 ).

Definition 4.1 (Computable reducibility).

Definition 4.4 (Matrix).

Definition 4.5 (Type).

Definition 4.9 (Essential formula).

Definition 4.10 (Fairness).

Definition 5.1 (Tree theorem).

Footnotes

Acknowledgements

References

Lemma 2.1 ( ${RCA}_{0}$ ).

Lemma 2.3 ( ${RCA}_{0} + I Σ_{2}^{0}$ ).