1111/1111.2526.md

REVERSE MATHEMATICS AND A RAMSEY-TYPE KÖNIG'S LEMMA

STEPHEN FLOOD

ABSTRACT. In this paper, we propose a weak regularity principle which is similar to both weak König's lemma and Ramsey's theorem. We begin by studying the computational strength of this principle in the context of reverse mathematics. We then analyze different ways of generalizing this principle.

1. INTRODUCTION

Weak König's lemma states that for any infinite binary tree $T \subseteq 2^{<\mathbb{N}}$ , there is an infinite path $p$ through $T$ . When formalized in second order arithmetic, this theorem is denoted $\text{WKL}_0$ . There is a direct correspondence between a path $p$ through a binary tree, which is a function $p : \mathbb{N} \rightarrow {0, 1}$ , and the set ${x : p(x) = 1}$ . With this in mind, we occasionally identify paths through trees, colorings of singletons, and subsets of $\mathbb{N}$ .

Ramsey's theorem is a generalization of the pigeon-hole principle. Given $n \in \mathbb{N}$ , let $[\mathbb{N}]^n$ denote the collection of size $n$ subsets of $\mathbb{N}$ . The infinite version of Ramsey's theorem says that for every $n, k \in \mathbb{N}$ and every function (called a coloring) $f : [\mathbb{N}]^n \rightarrow {0, \dots, k-1}$ , there is an infinite set $H \subseteq \mathbb{N}$ which is given one color by $f$ . In the context of second order arithmetic, this principle is denoted $\text{RT}_k^n$ (with $n, k$ as above).

Weak König's lemma and Ramsey's theorem can be thought of as asserting the existence of different types of regularity. Viewed topologically, weak König's lemma is essentially the statement " $2^{\mathbb{N}}$ is compact." This carries over to reverse mathematics, where $\text{WKL}_0$ is equivalent to many theorems about compactness (see [13]). For its part, Ramsey's theorem says that no matter how badly behaved a coloring is, it always has a sizable homogeneous set. In the words of T.S. Motzkin, absolute disorder is impossible.

In this paper, we study the computational and reverse mathematical strength of a regularity principle which combines features of weak König's lemma and Ramsey's theorem. We will refer to the statement "for each infinite binary tree $T$ , there is an infinite set $H$ homogeneous for a path through $T$ " as a Ramsey-type König's lemma. In statement 2, we give a formal definition of our Ramsey-type König's

---

2010 Mathematics Subject Classification. Primary 03F35, Secondary 03B30.

Key words and phrases. Ramsey's theorem, weak König's lemma, reverse mathematics.

Partially supported by EMSW21-RTG 0353748, 0739007, and 0838506. This research will be part of the author's Ph.D. thesis written at Notre Dame under the direction of Peter Cholak. Special thanks to Damir Dzhararov for his suggestions and comments. Many thanks to Keita Yokoyama for his proof of theorem 18. This research was partly conducted while the author was visiting the Institute for Mathematical Sciences at the National University of Singapore in 2011.lemma, denoted $\text{RKL}$ , in terms of finite strings. It is the novelty of this principle, rather than the complexity of the proofs, that is the main innovation of this paper.

We begin by showing that $\text{RKL}$ is a nontrivial weakening of $\text{WKL}_0$ and of $\text{RT}_2^2$ . More formally, we show that $\text{SRT}_2^2$ implies $\text{RKL}$ , that $\text{WKL}_0$ implies $\text{RKL}$ , and that $\text{RKL}$ implies $\text{DNR}$ (unless specified, we always work over $\text{RCA}_0$ ). Applying results of [1] and [11], we conclude that $\text{RKL}$ is strictly weaker than $\text{WKL}_0$ and $\text{SRT}_2^2$ .

In the remaining sections, we state analogs of $\text{RKL}$ for trees generated by infinite sets of strings ( $\text{RKL}^{(1)}$ ) and for arithmetically-definable trees ( $\text{RKL}^{(<\omega)}$ ). We then study the strength of each principle, and obtain the surprising result that these stronger principles are more closely related to $\text{RT}_2^2$ than to $\text{WKL}_0$ .

We show that $\text{RT}_2^2$ implies $\text{RKL}^{(1)}$ , and that $\text{RKL}^{(1)}$ implies $\text{SRT}_2^2$ . By the main results of [5] and [11], it follows that $\text{RKL}^{(1)}$ and $\text{WKL}_0$ are incomparable. We also show that $\text{RT}_2^2$ does not imply $\text{RKL}^{(<\omega)}$ and, by using a result of [11], we show that $\text{RKL}^{(<\omega)}$ does not imply $\text{WKL}_0$ . We leave open whether $\text{RKL}^{(<\omega)}$ implies $\text{RT}_2^2$ . We summarize our results in figure 1.

1.1. Working in second order arithmetic. We assume that the reader is familiar with the basic definitions and results of computability theory and reverse mathematics. For an introduction to reverse mathematics, see chapter I of [13]. For an introduction to computability theory, see part A of [14].

Some care is required to formalize $\text{RKL}$ in $\text{RCA}_0$ . Our goal here is to study the computational complexity of the homogeneous set $H$ , not of the path $p$ . While there are computable trees $T$ such that each path through $T$ is reasonably complicated, there are paths $p$ with relatively simple homogeneous sets $H$ . We begin with definitions that allow us to say that $H$ is homogeneous for some path through $T$ without explicit reference to a path $p$ .

Definition 1 ( $\text{RCA}_0$ ). $H$ is homogeneous for $\sigma \in 2^{<\mathbb{N}}$ with color $c \in {0, 1}$ if $\sigma(x) = c$ for each $x \in H$ s.t. $x < |\sigma|$ . $H$ is homogeneous for a path through $T$ if $\exists c \in {0, 1}$ s.t. $H$ is homogeneous for $\sigma$ with color $c$ for arbitrarily long $\sigma \in T$ .

Statement 2 ( $\text{RCA}_0$ ). $\text{RKL}$ asserts that “for each infinite binary tree $T$ , there is an infinite set $H$ which is homogeneous for a path through $T$ .”

Unless stated otherwise, all strings and trees we consider will be binary ( ${0, 1}$ -valued). Given $\tau, \sigma \in 2^{<\mathbb{N}}$ we write $\tau \preceq \sigma$ if $\tau$ is an initial segment of $\sigma$ . We write $\sigma \upharpoonright t$ (or $p \upharpoonright t$ ) to denote the initial segment of $\sigma \in 2^{<\mathbb{N}}$ (or $p \in 2^{\mathbb{N}}$ ) of length $t$ .

2. REVERSE MATHEMATICS OF $\text{RKL}$

Theorem 3 ( $\text{RCA}_0$ ). $\text{WKL}_0$ implies $\text{RKL}$ .

Proof. Given an infinite binary tree $T$ , let $p$ be an infinite path through $T$ . Note that $p : \mathbb{N} \rightarrow {0, 1}$ maps singletons into two colors. Applying $\text{RT}_2^1$ , which is provable in $\text{RCA}_0$ , yields a set $H$ which is homogeneous for $p$ . In particular, $p \upharpoonright t \in T$ and $H$ is homogeneous for $p \upharpoonright t$ for each $t \in \mathbb{N}$ . Thus $H$ satisfies definition 1, as desired. $\square$

Definition 4 ( $\text{RCA}_0$ ). A coloring $f : [\mathbb{N}]^2 \rightarrow {0, 1}$ is stable if for each $x$ , there is some $t > x$ s.t. $(\forall y > t)[f(x, y) = f(x, t)]$ . $\text{SRT}_2^2$ is the theorem “every stable coloring of pairs into two colors has an infinite homogeneous set.”

Theorem 5 ( $\text{RCA}_0$ ). $\text{SRT}_2^2$ implies $\text{RKL}$ .Proof. Given an infinite tree $T$ , we define a coloring $f : [\mathbb{N}]^2 \rightarrow {0, 1}$ as follows. For each $y$ , let $\sigma_y$ be the lexicographically least element of $T$ of length $y$ . For each $x < y$ , define $f(x, y) = \sigma_y(x)$ .

We now show that $f$ is a stable coloring. Fix $x$ , and let $T^{ext}$ denote the strings in $T$ that are extended by arbitrarily long strings in $T$ . For each $\tau \in T - T^{ext}$ of length $x + 1$ , there is a bound on the length of strings in $T$ extending $\tau$ , so there is a least such bound $s_\tau$ . Note that $s_\tau$ is $\Delta_1^0$ definable (with parameters) from $\tau$ . By $\Sigma_1^0$ induction, there is a uniform upper bound $t$ for ${s_\tau : \tau \in 2^{x+1} \wedge \tau \in T - T^{ext}}$ . By $\Pi_1^0$ induction, there is a lexicographically least element $\tau_{x+1} \in T^{ext}$ of length $x + 1$ . Then for each $y > t$ , $\sigma_y \upharpoonright (x + 1) = \tau_{x+1}$ hence $f(x, y) = \tau_{x+1}(x)$ . In general, for each $x$ , $(\exists t)(\forall y > t)[f(x, y) = \tau_{x+1}(x)]$ . In other words, $f$ is a stable coloring.

Suppose that $H$ is homogeneous for $f$ with color $c \in {0, 1}$ . We now show that $H$ is homogeneous for a path through $T$ . Fix $t \in \mathbb{N}$ . Because $H$ is an infinite set, there is an element $y \in H$ with $y \geq t$ . By the definition of $f$ , $(\forall x < y)[\sigma_y(x) = f(x, y)]$ . Because $H$ is homogeneous for $f$ with color $c$ and because $y \in H$ , $(\forall x < y)[x \in H \implies \sigma_y(x) = c]$ . Then $H$ is homogeneous for $\sigma_y \in T$ with color $c$ . Since $t$ is arbitrary and $|\sigma_y| \geq t$ , we have satisfied definition 1. $\square$

Corollary 6 (RCA₀). RKL does not imply SRT₂² or WKL₀.

Proof. By the main result of [11], SRT₂² does not imply WKL₀. Because SRT₂² implies RKL, RKL cannot imply WKL₀. Similarly, RKL cannot imply SRT₂² over RCA₀ because WKL₀ does not imply SRT₂² (by Theorem 3.3 of [12] and Theorem 10.5 of [1]). $\square$

We conclude our analysis of RKL by showing that it is not provable in RCA₀, and by showing that RKL is strong enough to imply DNR. When $T \subseteq 2^{<\mathbb{N}}$ is a tree, $[T] \subseteq 2^{\mathbb{N}}$ will be the set of infinite paths through $T$ . The following lemma follows from the proof of lemma 2 in [10].

Lemma 7 (Jockusch, [10]). There is an infinite computable tree $T$ such that for any $p \in [T]$ and for any $e \in \mathbb{N}$ , if $|W_e| \geq e + 3$ then $W_e$ is not homogeneous for $p$ . In fact, for each $e \in \mathbb{N}$ , there is a $t \in \mathbb{N}$ s.t. if $|W_e| \geq e + 3$ then $W_e$ is not homogeneous for any string in $T$ of length greater than $t$ .

A simple corollary is that RCA₀ $\not\vdash$ RKL, via an $\omega$ -model. Adapting the proof of Theorem 2.3 from [8], we can obtain a slightly stronger result. We say that a function $f$ is diagonally non-computable relative to $X$ if $f(e) \neq \Phi_e^X(e)$ for each $e$ s.t. $\Phi_e^X(e) \downarrow$ . The principle DNR asserts that for any set parameter $X$ , there is a function that is diagonally non-computable relative to $X$ .

Theorem 8 (RCA₀). RKL implies DNR.

Proof. We work relative to a set parameter $X$ . The proof of lemma 2 of [10] (lemma 7 above) works in RCA₀. Let $T$ be the tree defined in this proof. By RKL, there is a set $H$ homogeneous for a path through $T$ . Note that there is a $\Delta_1^0$ definable function $g : \mathbb{N} \rightarrow \mathbb{N}$ such that $W_{g(e)}$ is the least $e + 3$ elements of $H$ (in the $\mathbb{N}$ order).

We now show that $g$ is a fixed point free function. If $|W_e| < 2^{e+1}$ , then $|W_{g(e)}| \neq |W_e|$ . Suppose that $|W_e| \geq 2^{e+1}$ . By the above lemma, there is some $t$ s.t. $W_e$ is not homogeneous for any $\sigma \in T$ of length greater than $t$ . Because $W_{g(e)} \subset H$ and because $H$ is homogeneous for a path through $T$ , $W_{g(e)}$ is homogeneous for arbitrarily long $\sigma \in T$ . In particular $W_e \neq W_{g(e)}$ . In other words, $g$ is fixed pointfree, so can be used to give a $\Delta_1^0$ definition for a DNR function (formalize V.5.8 of [14] in $\text{RCA}_0$ ). $\square$

Question 9. Does DNR imply RKL?

A number of principles are known to be stronger than DNR, such as ASRAM and ASRT $_2^2$ from [7]. Proving that one of these principles does not imply RKL would separate DNR from RKL.

3. TREES GENERATED BY SETS OF STRINGS

Definition 10. Given an infinite set of strings $\Sigma$ , let $T_\Sigma$ denote the downward closure of $\Sigma$ . More formally $T_\Sigma = {\tau : (\exists \sigma \in \Sigma)[\tau \preceq \sigma]}$ .

Statement 11 ( $\text{RCA}_0$ ). RKL $^{(1)}$ asserts that “for each infinite set of strings $\Sigma$ , there is a set $H$ which is homogeneous for a path through $T_\Sigma$ .”

Note that if $\Sigma$ is an infinite computable set of strings, $T_\Sigma$ is an infinite c.e. tree. In [6], Downey and Jockusch note that each infinite $\Pi_1^{0,\theta'}$ -class can be generated by a c.e. tree. We extend this slightly, to further motivate our definition of RKL $^{(1)}$ .

Proposition 12. If $T$ is an infinite $\Pi_2^0$ tree, then there is an infinite computable set of strings $\Sigma$ s.t. $[T] = [T_\Sigma]$ . Furthermore, $\Sigma$ can be taken to contain exactly one string of each length.

Proof. It suffices to consider $\Sigma_1^0$ trees. To see this, suppose that $T$ is $\Pi_2^0$ . Then there is a formula $\phi$ which is $\Delta_1^0$ s.t. $\tau \in T \leftrightarrow (\forall y)(\exists z)\phi(\tau, y, z)$ . Using the $\Delta_1^0$ formula $\psi(\tau, \hat{z}) =_{\text{def}} (\forall x, y \leq |\tau|)(\exists z < \hat{z})\phi(\tau \upharpoonright x, y, z)$ , we can define a $\Sigma_1^0$ tree $S$ by $\tau \in S \leftrightarrow (\exists \hat{z})\psi(\tau, \hat{z})$ . Then $[S] = {f : (\forall w)(\exists \hat{z})\psi(f \upharpoonright w, \hat{z})} = {f : (\forall x)(\forall y)(\exists z)\phi(f \upharpoonright x, y, z)} = [T]$ , so we may work with $S$ instead.

Given a $\Sigma_1^0$ tree $T$ , fix a computable enumeration ${T_s}$ of $T$ . If necessary, we computably modify the enumeration to ensure that no $\tau$ enters $T_s$ until $s \geq |\tau|$ and that exactly one string enters $T$ at each stage. We computably enumerate the elements of $\Sigma$ in increasing order. At stage $s > 0$ , find $\tau \in T_s - T_{s-1}$ , take one $\sigma \succeq \tau$ with $|\sigma| = s$ (the specific choice is not important), and put $\sigma$ into $\Sigma$ . It is not difficult to show that $T \subseteq T_\Sigma$ and that $T_\Sigma^{\text{ext}} \subseteq T^{\text{ext}}$ . It follows that $[T] = [T_\Sigma]$ . $\square$

We now examine the strength of RKL $^{(1)}$ .

Theorem 13 ( $\text{RCA}_0$ ). RT $_2^2$ implies RKL $^{(1)}$ .

Proof. Fix an infinite set of strings $\Sigma$ . For each $y$ , let $l \geq y$ be the length of the shortest string in $\Sigma$ of length at least $y$ . Let $\sigma_y$ be the lexicographically least string in $\Sigma$ of length $l$ . We now define a coloring $f : [\mathbb{N}]^2 \rightarrow {0, 1}$ as before. For each $x < y \in \mathbb{N}$ , set $f(x, y) = \sigma_y(x)$ . Note that $f$ is $\Delta_1^0$ -definable.

By RT $_2^2$ , there is an infinite set $H$ homogeneous for $f$ with color $c \in {0, 1}$ . We claim that $H$ is homogeneous for a path through $T_\Sigma$ .

Fix $t \in \mathbb{N}$ . Because $H$ is infinite, there is some $y \in H$ with $y \geq t$ . By definition of $f$ , $(\forall x < y)[f(x, y) = \sigma_y(x)]$ . Because $H$ is homogeneous for $f$ with color $c$ and because $y \in H$ , $(\forall x < y)[x \in H \implies \sigma_y(x) = c]$ . In other words, $H$ is homogeneous for $\sigma_y \upharpoonright y$ with color $c$ . Because $\sigma_y \upharpoonright y \in T_\Sigma$ and because $y \geq t$ with $t$ arbitrary, $H$ is homogeneous for a path through $T_\Sigma$ (in the sense of definition 1). $\square$Remark 14. The coloring defined in the proof of theorem 13 is not (necessarily) stable because it is defined in terms of $\Sigma$ , and not in terms of $T$ . For example, suppose that $\sigma(0) = 0$ for even length strings $\sigma \in \Sigma$ , and that $\sigma(0) = 1$ for odd length strings. Then $\lim_y f(0, y)$ does not exist.

There is a natural correspondence between computable colorings $f : [\mathbb{N}] \rightarrow {0, 1}$ and computable sets $\Sigma \subset 2^{<\mathbb{N}}$ that contain exactly one string of each length. Given $f$ , simply define $\Sigma = {\sigma_y : \sigma_y \in 2^y \wedge (\forall x < y)[\sigma_y(x) = f(x, y)]}$ . Using the induced tree $T_\Sigma$ , it is not difficult to show that $\text{RKL}^{(1)}$ implies $\text{SRT}_2^2$ over $\text{RCA}_0 + \text{B}\Sigma_2^0$ . Yokoyama was able to eliminate the use of $\text{B}\Sigma_2^0$ by introducing the following principle.

Statement 15 ( $\text{RCA}_0$ ). $P_2^2$ asserts that “for any $\Pi_2^0$ -definable subsets $A_0, A_1$ of $\mathbb{N}$ s.t. $A_0 \cup A_1 = \mathbb{N}$ , there exists an infinite set $H \in S(\mathcal{M})$ s.t. $H \subseteq A_0$ or $H \subseteq A_1$ .”

The principle $P_2^2$ is particularly useful because it implies the better understood principle $D_2^2$ . This is a special instance of the principle $D_2^n$ , which we will return to in the next section.

Statement 16 ( $\text{RCA}_0$ ). For each $n \in \omega$ , $D_2^n$ asserts that “for each $\Delta_n^0$ -definable subset $A$ of $\mathbb{N}$ , there exists an infinite set $H \in S(\mathcal{M})$ s.t. $H \subseteq A$ or $H \subseteq \overline{A}$ .”

Theorem 17 (Cholak, Chong, Jockush, Lempp, Slaman, Yang [1, 4]). Over $\text{RCA}_0$ , $D_2^2$ is equivalent to $\text{SRT}_2^2$ .

Theorem 18 (Yokoyama [15]). $\text{RKL}^{(1)}$ implies $P_2^2$ , and hence $\text{SRT}_2^2$ , over $\text{RCA}_0$ .

Proof. Let $\mathcal{M} = (\mathbb{N}, S(\mathcal{M})) \models \text{RCA}_0 + \text{RKL}^{(1)}$ and suppose that $A_0, A_1$ are $\Pi_2^0$ -definable subsets of $\mathbb{N}$ s.t. $A_0 \cup A_1 = \mathbb{N}$ . We will define a $\Delta_1^0$ function $f : [\mathbb{N}]^2 \rightarrow {0, 1}$ s.t. if $f(x, y) = i$ for infinitely many $y$ , then $x \in A_i$ .

Fix two $\Sigma_0^0$ formulas $\theta_i(x, m, n)$ s.t. $x \in A_i \iff (\forall m)(\exists n)\theta_i(x, m, n)$ . Using these formulas, we define a helper function:

Clearly, $h$ is a $\Delta_1^0$ function.

We must verify in $\text{RCA}_0$ that $h$ is total. Fix $x \in \mathbb{N}$ arbitrary. Then $x \in \mathbb{N} = A_0 \cup A_1$ , so $x \in A_0$ or $x \in A_1$ . So $(\forall m)(\exists n)\theta_0(x, m, n)$ or $(\forall m)(\exists n)\theta_1(x, m, n)$ . Let $y \in \mathbb{N}$ be arbitrary. Suppose $x \in A_i$ . Then $(\forall m)(\exists n)\theta_i(x, m, n)$ , so clearly $(\forall m < y)(\exists n)\theta_i(x, m, n)$ . By $\text{B}\Sigma_1^0$ , there is a $z_i$ s.t. $(\forall m < y)(\exists n < z_i)\theta_i(x, m, n)$ . Thus, $h$ will find a least $z$ s.t. the desired condition holds.

Define $f(x, y) = 0$ if $(\forall m < y)(\exists n < h(x, y))[\theta_0(x, m, n)]$ , and $f(x, y) = 1$ otherwise. Clearly, $f$ is total since $h$ is total, and $f$ is $\Delta_1^0$ since $h$ is total and $\Delta_1^0$ . If $f(x, y) = i$ for infinitely many $y$ , then our defn of $h(x, y)$ confirms that $x \in A_i$ .

Using $f$ , let $\Sigma = {\sigma_y : \sigma_y \in 2^y \wedge (\forall x < y)[\sigma_y(x) = f(x, y)]}$ and define $T_\Sigma$ as before. Take $H$ homogeneous for a path through $T_\Sigma$ with some color $c \in {0, 1}$ .

Let $x \in H$ be arbitrary. By definition of “homogeneous for a path through $T_\Sigma$ with color $c$ ,” there are infinitely many $y$ s.t. $f(x, y) = \sigma_y(x) = c$ . By our choice of $f$ , this means that $x \in A_c$ . In other words, $H \subseteq A_c$ is the desired infinite set. $\square$

Question 19 (Yokoyama [15]). Does $D_2^2$ imply $P_2^2$ ? Does $P_2^2$ imply $\text{RKL}^{(1)}$ ?

Corollary 20. *$\text{RKL}^{(1)}$ is incomparable with $\text{WKL}_0$ over $\text{RCA}_0$*Proof. Because $\text{WKL}_0$ does not imply $\text{SRT}_2^2$ (Theorem 3.3 of [12] and Theorem 10.5 of [1]), $\text{WKL}_0$ does not imply $\text{RKL}^{(1)}$ . By the main result of [11], $\text{RT}_2^2$ does not imply $\text{WKL}_0$ , so $\text{RKL}^{(1)}$ cannot imply $\text{WKL}_0$ . $\square$

Remark 21. Using the above arguments, we can rephrase $\text{RT}_2^2$ as the statement “for each $\Sigma$ which contains exactly one string of each length, there is an infinite $H$ which is homogeneous (with fixed color $c$ ) for each $\sigma \in \Sigma$ s.t. $|\sigma| \in H$ .”

Question 22. Does $\text{RKL}^{(1)}$ imply $\text{COH}$ , $\text{CAC}$ , $\text{ADS}$ or $\text{RT}_2^2$ ? One implication holds if and only if all implications hold. Does $\text{SRT}_2^2$ imply $\text{RKL}^{(1)}$ ?

4. ARITHMETICALLY-DEFINABLE TREES

Statement 23 ( $\text{RCA}_0$ ). $\text{RKL}^{(<\omega)}$ is the axiom scheme which, for each arithmetic formula $\phi$ , asserts that “if $\phi$ defines a tree $T$ containing arbitrarily long strings, there is an infinite set $H$ which is homogeneous for a path through $T$ .”

Theorem 24. Over $\text{RCA}_0$ , we have the following strict implications: $\text{ACA}_0 \implies \text{RKL}^{(<\omega)} \implies \text{RKL}^{(1)} \implies \text{RKL}$ .

The implications are immediate. We have already seen that the third implication is strict. We now show that the first two implications are also strict. We first use the following result from [11] to separate $\text{RKL}^{(<\omega)}$ from $\text{ACA}_0$ .

Theorem 25 (Liu, [11]). For every $C \not\supset \emptyset$ and every coloring $p : \mathbb{N} \rightarrow {0, 1}$ , there exists an infinite set $H$ homogeneous for $p$ such that $H \oplus C \not\supset \emptyset$ .

Corollary 26. There is an $\omega$ -model of $\text{RKL}^{(<\omega)}$ where $\text{WKL}_0$ fails.

Proof. To build an $\omega$ -model $\mathcal{M} = (\omega, S(\mathcal{M}))$ of $\text{RKL}^{(<\omega)}$ , we begin with $S(\mathcal{M}) = \text{REC}$ and add sets to $S(\mathcal{M})$ .

The general strategy for creating a model of $\text{RKL}^{(<\omega)}$ uses a list of the infinite trees which are arithmetically-definable from any set $X \in S(\mathcal{M})$ . For each $i \in \mathbb{N}$ , we must ensure that there is some finite stage $s$ where we select a path $p$ through the $i^{\text{th}}$ tree $T$ , where we select an infinite set $H_s$ homogeneous for $p$ , and where we add $H_s$ to $S(\mathcal{M})$ and close downward under $\leq_T$ . To ensure that $\mathcal{M} \not\models \text{WKL}0$ , we use Theorem 25 to select $H_s$ s.t. $H_s \oplus \bigoplus{j \leq s-1} H_j \not\supset \emptyset$ .

It is possible that adding the set $H_s$ to $S(\mathcal{M})$ causes new sets to become arithmetically-definable with parameters from $S(\mathcal{M})$ . Therefore, each time we add $H_s$ to $S(\mathcal{M})$ , we create a new list containing the trees arithmetically-definable from $\bigoplus_{i \leq s} H_i$ . We dovetail the lists, eventually running the general strategy for each tree in each list. In the limit, we obtain $\mathcal{M} \models \text{RKL}^{(<\omega)} \vdash \neg \text{WKL}_0$ . $\square$

Corollary 27 ( $\text{RCA}_0$ ). $\text{RKL}^{(<\omega)}$ does not imply $\text{WKL}_0$ .

We separate $\text{RKL}^{(<\omega)}$ from $\text{RKL}^{(1)}$ with an $\omega$ -model by the following observation.

Lemma 28. For each $n$ , no model of $\text{RKL}^{(<\omega)}$ is bounded by $\emptyset^n$ .

Proof. By the proof of lemma 7 relativized to $X = \emptyset^n$ , we obtain an $\emptyset^n$ -computable infinite tree $T$ s.t. no infinite set $W_e^{\emptyset^n}$ is homogeneous for a path through $T$ . Since each $\emptyset^n$ -computable set is $W_e^{\emptyset^n}$ for some $e$ , it follows that no infinite $\emptyset^n$ -computable set is homogeneous for a path through $T$ . $\square$Proposition 29. $RT_2^2$ does not imply $RKL^{(<\omega)}$ over $RCA_0$ . Consequently, $RKL^{(1)}$ does not imply $RKL^{(<\omega)}$ over $RCA_0$ .

Proof. By the previous lemma, there is no model of $RKL^{(<\omega)}$ which is bounded by $\emptyset^2$ . By Theorem 3.1 of [1], there is an $\omega$ -model of $RT_2^2$ consisting of only $low_2$ sets. This model is bounded by $\emptyset^2$ so is not a model of $RKL^{(<\omega)}$ . $\square$

Question 30. Does $RKL^{(<\omega)}$ imply $COH$ over $RCA_0$ ? Equivalently, does $RKL^{(<\omega)}$ imply $RT_2^2$ over $RCA_0$ ?

4.1. Subsets, co-subsets, and trees. There is a close relationship between finding subsets/cosubsets of a fixed set, and finding sets that are homogeneous for a path through a fixed tree.

Statement 31 ( $RCA_0$ ). We define $D_2^{\leq\omega}$ to be the axiom scheme which asserts $D_2^n$ for each $n \in \omega$ .

Proposition 32 ( $RCA_0$ ). $RKL^{(<\omega)}$ implies $D_2^{\leq\omega}$ .

Proof. Let $\mathcal{M} = (\mathbb{N}, S(\mathcal{M})) \models RCA_0 + RKL^{(<\omega)}$ and suppose that $A$ is a $\Delta_n^0$ -definable subset of $\mathbb{N}$ . We give a $\Pi_n^0$ definition for a tree $T$ as follows. Given $\tau \in 2^{<\mathbb{N}}$ , we say that $\tau \in T$ if and only if $(\forall x < |\tau|)[\tau(x) = 1 \text{ if and only if } x \in A]$ .

By $RKL^{(<\omega)}$ , there is a set $H \in S(\mathcal{M})$ which is homogeneous for arbitrarily long strings in $T$ with color $c \in {0, 1}$ . Note that the only strings in $T$ are initial segments of $\chi_A$ , so $H$ is homogeneous for $\chi_A$ with color $c$ . Then $H \subseteq A$ if $c = 1$ , and $H \subseteq \bar{A}$ if $c = 0$ , as desired. $\square$

Remark 33. For $\omega$ -models, the reverse implication also holds.

Question 34. Does $D_2^{\leq\omega}$ imply $RKL^{(<\omega)}$ over $RCA_0$ ?

By results of [1], $SRT_2^2$ implies $B\Sigma_2^0$ .

Question 35. Are there first order consequences of $RKL^{(<\omega)}$ beyond $B\Sigma_2^0$ ?

Chong, Slaman, and Yang have recently announced a proof that $D_2^2$ does not imply $COH$ over $RCA_0$ [3].

Question 36. Does $D_2^n$ imply $COH$ for any $n \in \omega$ ?

Theorem 2.1 of [9] gives another way to state this question for $\omega$ -models.

Question 37. Is there any arithmetically-definable $f : \mathbb{N} \rightarrow {0, 1}$ such that any set $H$ homogeneous for $f$ satisfies $H' \gg \emptyset'$ ?

REFERENCES

1. 1. Peter A. Cholak, Carl G. Jockusch, Jr., and Theodore A. Slaman, On the strength of Ramsey's theorem for pairs, J. Symbolic Logic 66 (2001), no. 1, 1–55.
2. 2. ———, Corrigendum to: "On the strength of Ramsey's theorem for pairs", J. Symbolic Logic 74 (2009), no. 4, 1438–1439.
3. 3. C. T. Chong, personal communication, 2012.
4. 4. C. T. Chong, Steffen Lempp, and Yue Yang, On the role of the collection principle for $\Sigma_2^0$ -formulas in second-order reverse mathematics, Proc. Amer. Math. Soc. 138 (2010), no. 3, 1093–1100.
5. 5. Rod Downey, Denis R. Hirschfeldt, Steffen Lempp, and Reed Solomon, A $\Delta_2^0$ set with no infinite low subset in either it or its complement, J. Symbolic Logic 66 (2001), no. 3, 1371–1381.```

graph TD ACA0[ACA0] --> RT2[RT22] ACA0 --> RKL1[RT22] ACA0 --> RKL11["RKL(<ω)"] ACA0 --> WKL0[WKL0] RT2 --> RKL11["RKL(1)"] RKL11 --> SRT2[SRT22] SRT2 --> RKL[RKL] RKL --> DNR[DNR] DNR --> RCA0[RCA0] RKL111["RKL(<ω)"] --> COH[COH] COH --> RCA0

FIGURE 1. A summary of the principles considered.

1. 6. Rod Downey and Carl G. Jockusch, Jr., *Effective presentability of Boolean algebras of Cantor-Bendixson rank 1*, J. Symbolic Logic **64** (1999), no. 1, 45–52.
2. 7. Damir D. Dzhafarov, *Stable Ramsey’s theorem and measure*, Notre Dame J. Form. Log. **52** (2011), no. 1, 95–112.
3. 8. Denis R. Hirschfeldt, Carl G. Jockusch, Jr., Bjørn Kjos-Hanssen, Steffen Lempp, and Theodore A. Slaman, *The strength of some combinatorial principles related to Ramsey’s theorem for pairs*, Computational prospects of infinity. Part II. Presented talks, Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap., vol. 15, World Sci. Publ., Hackensack, NJ, 2008, pp. 143–161.
4. 9. Carl Jockusch and Frank Stephan, *A cohesive set which is not high*, Math. Logic Quart. **39** (1993), no. 4, 515–530.
5. 10. Carl G. Jockusch, Jr.,  $\Pi_1^0$  classes and Boolean combinations of recursively enumerable sets, J. Symbolic Logic **39** (1974), 95–96.
6. 11. Jiayi Liu, *RT<sub>2</sub><sup>2</sup> does not imply WKL*, J. Symbolic Logic, to appear.
7. 12. David Seetapun and Theodore A. Slaman, *On the strength of Ramsey’s theorem*, Notre Dame J. Formal Logic **36** (1995), no. 4, 570–582, Special Issue: Models of arithmetic.
8. 13. Stephen G. Simpson, *Subsystems of second order arithmetic*, second ed., Perspectives in Logic, Cambridge University Press, Cambridge, 2009.
9. 14. Robert I. Soare, *Recursively enumerable sets and degrees*, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1987.
10. 15. Keita Yokoyama, personal communication, 2011.

DEPARTMENT OF MATHEMATICS, UNIVERSITY OF NOTRE DAME, 255 HURLEY HALL, NOTRE DAME, IN 46556

*E-mail address:* sflood@nd.edu