On the first-order parts of problems in the Weihrauch degrees

Abstract

We introduce the notion of the first-order part of a problem in the Weihrauch degrees. Informally, the first-order part of a problem $P$ is the strongest problem with codomaixn ω that is Weihrauch reducible to $P$ . We show that the first-order part is always well-defined, examine some of the basic properties of this notion, and characterize the first-order parts of several well-known problems from the literature.

1. Introduction

This paper continues the investigation of the interface between reverse mathematics and computable analysis. The connection was first suggested by Gherardi and Marcone [14], and later independently by Dorais, Dzhafarov, Hirst, Mileti, and Shafer [8]. In the past few years, this area has blossomed into a rich and productive area of research, with by now many papers dedicated to it.

Reverse mathematics uses a combined computability-theoretic and proof-theoretic point of view to analyze the logical strength of theorems that can be formalized in second-order arithmetic. Much of this focuses on second-order strength, meaning more specifically, on which set-existence axioms are necessary and sufficient to prove a given such theorem. But there has also been a great deal of work on first-order strength, meaning on which number-theoretic results are derivable from a particular theorem. The strongest such result is commonly referred to as the first-order part of the theorem. It is an impressive fact that theorems entirely about sets of natural numbers (and by extension, mathematical objects that can be represented by sets of numbers) can have nontrivial and often surprising first-order parts.

Computable analysis, on the other hand, is concerned with computational problems rather than theorems, and on how these relate to one another under various reducibilities, the most important of which is Weihrauch reducibility. As we review in detail below, there is a well-known correspondence between such problems and a common type of theorem analyzed in reverse mathematics, and this connection has been strengthened by some of the recent investigations mentioned above.

We refer the reader to Simpson [22], Hirschfeldt [16], and Dzhafarov and Mummert [12] for background in reverse mathematics. We include some basic definitions from computable analysis below, and refer the reader to Brattka and Pauly [4] and Brattka, Gherardi, and Pauly [2] for more complete introductions.

In this paper, we introduce the notion of the first-order part of a problem. By analogy with the reverse mathematics setting, this is informally meant to capture the strongest “number-theoretic” problem that is Weihrauch reducible to that problem. We will explore the connections between our definition and the first-order parts of theorems in reverse mathematics. We will then classify, as case studies, the first-order parts of several major problems from the literature. We note that, since the circulation of a preprint of this paper, there have been several papers continuing the investigation of the first-order parts of problems, including by Soldà and Valenti [26], Goh, Pauly, and Valenti [21], and Cipriani, Marcone, and Valenti [7].

We begin, in this section, by laying down some background for the rest of the paper. Our computability-theoretic notation and terminology is largely standard, following, e.g., Soare [25] or Downey and Hirschfeldt [9]. We highlight some small departures from this below.

We embed ω in $ω^{ω}$ by identifying $x \in ω$ with $f \in ω^{ω}$ such that $f (0) = x$ and $f (y) = 0$ for all $y > 0$ . Throughout, set will mean subset of ω unless otherwise noted. We identify sets with their characteristic functions, so that all sets are elements of $2^{ω} \subseteq ω^{ω}$ . For $f, g \in ω^{ω}$ , we write $⟨ f, g ⟩$ for the (Turing) join of f and g. If $f \in ω^{ω}$ and $σ \in ω^{< ω}$ , then $⟨ f, σ ⟩$ refers to the string τ of length $2 | σ |$ such that $τ (2 x) = f (x)$ and $τ (2 x + 1) = σ (x)$ for all $x < | σ |$ . We define $⟨ σ, f ⟩$ analogously. Joins of more than two objects are handled as usual, with the understanding that the number of objects involved is uniformly computable from the join itself.

We also write $⟨ y_{0}, \dots, y_{k - 1} ⟩$ for the string $σ \in ω^{k}$ with $σ (x) = y_{x}$ for all $x < k$ . For $b \in {0, 1}$ , we write $b^{k}$ for the string $σ \in ω^{k}$ with $σ (x) = b$ for all $x < k$ , and $b^{ω}$ for the sequence $f \in ω^{ω}$ with $f (x) = b$ for all x. For $σ, τ \in ω^{< ω}$ , we write $σ τ$ or $σ^{⌢} τ$ for the concatenation of σ by τ, and similarly for the concatenation of finite strings by infinite sequences.

We regard all Turing functionals Φ as partial continuous maps $ω^{ω} \to ω^{ω}$ , and write $Φ (f) = g$ if $Φ^{f} (x) ↓ = g (x)$ for all $x \in ω$ . In this paper, we also write $Φ (f) (x)$ in place of $Φ^{f} (x)$ and $Φ (f, g)$ in place of $Φ (⟨ f, g ⟩)$ , etc. We follow the convention that if $Φ (f) (x) ↓$ for some $f \in ω^{ω}$ and some $x \in ω$ then $Φ (f) (y) ↓$ for all $y ⩽ x$ . For $σ \in ω^{< ω}$ , we write $Φ (σ) (x) ↓ = y$ if $Φ (f) (x) ↓ = y$ for all $f \in ω^{ω}$ extending σ in at most $| σ |$ many steps. In particular, if $Φ (f) (x) ↓$ then $Φ (f ↾ k) (x) ↓$ for some $k \in ω$ .

We use uppercase Greek letters for arbitrary Turing functionals, Φ, Δ, Γ, etc., and let $Φ_{0}, Φ_{1}, \dots$ denote a fixed computable listing of all Turing functionals.

Definition 1.1.

A problem is a partial multifunction $P : \subseteq ω^{ω} ⇉ ω^{ω}$ . Each $f \in dom (P)$ is an instance of $P$ , or simply a $P$ -instance, and each $g \in P (f)$ is a solution to f in $P$ , or simply a $P$ -solution to f. We let $P$ denote the class of all problems.

A problem $Q$ is Weihrauch reducible to a problem $P$ , written $Q ⩽_{W} P$ , if there exist Turing functionals Φ and Ψ such that for all $f \in dom (Q)$ we have $Φ (f) \in dom (P)$ , and for every $\hat{g} \in P (Φ (f))$ we have $Ψ (f, \hat{g}) \in Q (f)$ . In this case, we also say $Q$ is Weihrauch reducible to $P$ via Φ and Ψ.

A problem $Q$ is strongly Weihrauch reducible to a problem $P$ , written $Q ⩽_{sW} P$ , if there exist Turing functionals Φ and Ψ such that for all $f \in dom (Q)$ we have $Φ (f) \in dom (P)$ , and for every $\hat{g} \in P (Φ (f))$ we have $Ψ (\hat{g}) \in Q (f)$ . In this case, we say $Q$ is strongly Weihrauch reducible to $P$ via Φ and Ψ.

The equivalence classes under $⩽_{W}$ form the Weihrauch degrees.

There is a natural correspondence between problems and theorems of the form $(\forall X) [φ (X) \to (\exists Y) ψ (X, Y)]$ for $X, Y \in ω^{ω}$ . Any problem gives rise to a theorem of this form by letting φ define the instances, and ψ the solutions. Conversely, any theorem of this form gives rise to the problem whose instances are the X satisfying $φ (X)$ , and the solutions to a given X are the Y satisfying $ψ (X, Y)$ . (See [12, Chapter 4] for a more detailed discussion.) When φ and ψ are arithmetical properties, the theorems of this form are $Π_{2}^{1}$ statements of second-order arithmetic, which constitute the bulk of theorems studied in reverse mathematics. The specific problems we consider in examples in the sequel will all correspond to $Π_{2}^{1}$ theorems in this fashion, and we will move back and forth between the problem and theorem perspectives.

For completeness, we include definitions of some of the principal operations on the Weihrauch degrees.
Definition 1.2.
Fix $P, Q \in P$ .
$P ⊔ Q$ (the join of $P$ and $Q$ ) is the problem with domain $dom (P) ⊔ dom (Q)$ and $(P ⊔ Q) (⟨ 0, f ⟩) = {0} \times P (f)$ and $(P ⊔ Q) (⟨ 1, g ⟩) = {1} \times Q (g)$ for all $f \in dom (P)$ and $g \in dom (Q)$ .

$P ⊓ Q$ (the meet of $P$ and $Q$ ) is the problem with domain $dom (P) \times dom (Q)$ and $(P ⊓ Q) (⟨ f, g ⟩) = ({0} \times P (f)) \cup ({1} \times Q (g))$ for all $f \in dom (P)$ and $g \in dom (Q)$ .

$P \times Q$ (the parallel product of $P$ and $Q$ ) is the problem with domain $dom (P) \times dom (Q)$ and $(P \times Q) (⟨ f, g ⟩) = P (f) \times Q (g)$ for all $f \in dom (P)$ and $g \in dom (Q)$ .

$P * Q$ (the compositional product of $P$ and $Q$ ) is the problem whose instances are all pairs $⟨ g, Δ ⟩$ such that $g \in dom (Q)$ and Δ is a Turing functional with $Δ (g, \hat{g}) \in dom (P)$ for all $\hat{g} \in Q (g)$ , with the solutions to any such $⟨ g, Δ ⟩$ being all $⟨ \hat{f}, \hat{g} ⟩$ such that $\hat{g} \in Q (g)$ and $\hat{f} \in P (Δ (g, \hat{g}))$ .

$P^{}$ (the finite parallelization* of $P$ ) is the problem whose instances are all $⟨ k, ⟨ f_{0}, \dots, f_{k - 1} ⟩ ⟩$ where $k ⩾ 1$ and $f_{0}, \dots, f_{k - 1}$ are $P$ -instances, with $P^{} (⟨ k, ⟨ f_{0}, \dots, f_{k - 1} ⟩ ⟩) = P (f_{0}) \times \dots \times P (f_{k - 1})$ .

$P^{'}$ (the jump* of $P$ ) is the problem whose instances are all pairs $⟨ f, i ⟩$ such that $f \in ω^{ω}$ and i is a $Δ_{2}^{0, f}$ index for a $P$ -instance g of $P$ , with a solution to any such $⟨ f, i ⟩$ being all the $P$ -solutions to g. We write $P^{(0)} = P$ , and for $n \in ω$ , $P^{(n + 1)} = {(P^{(n)})}^{'}$ .

The Weihrauch degrees form a lattice with ⊔ and ⊓ as join and meet, respectively. We refer the reader to Brattka and Pauly [4] for a comprehensive overview of the algebraic structure of the Weihrauch degrees under these (and many other) operations.

We will formally define the first-order part of a problem in the next section. For now, we make explicit the idea of a first-order, or “number-theoretic”, problem.
Definition 1.3.
$P \in P$ is a first-order problem if $P (f) \subseteq ω$ for all $f \in dom (P)$ . We let $F$ denote the class of all first-order problems.

$F$ is a large class of problems with many important and ubiquitous members, e.g., $LPO$ , $C_{2}$ , ${lim}_{N}$ , etc., which are commonly encountered in the literature on Weihrauch degrees. There are also many problems which, while not first-order themselves, are Weihrauch equivalent to first-order problems. The first-order part of a problem, which we define in the next section, will turn out to be the $⩽_{W}$ -largest member of $F$ that can be Weihrauch reduced to it.

One aspect of our interest is in how the first-order part of a problem in the present setting compares with its first-order part as a theorem of second-order arithmetic (in cases where both perspectives make sense). In reverse mathematics, first-order parts are often measured against induction and bounding schemes, which are themselves stratified by the arithmetical hierarchy. The commonly used base theory in reverse mathematics, ${RCA}_{0}$ , includes induction for $Σ_{1}^{0}$ formulas, $I Σ_{1}^{0}$ , and above this lies the Kirby–Paris hierarchy of successively stronger schemes: $B Σ_{2}^{0} < I Σ_{2}^{0} < B Σ_{3}^{0} < I Σ_{3}^{0} < \dots$ . (See [12, Sections 6.1–6.3] for definitions and further details.) There is a natural correspondence between these schemes and certain basic problems from computable analysis. We recall their definitions. Here and below, we identify each $k \in ω$ with the set ${i \in ω : i < k}$ for notational convenience.
Definition 1.4.
Fix $k \in ω \cup {ω}$ . The choice problem on k, $C_{k}$ , is the problem whose instances are all enumerations of proper subsets of k, with the solutions being all $i \in k$ that are not enumerated.

For convenience, we will usually think of the instances of $C_{k}$ , more explicitly, as functions $v : ω \to k + 1$ such that: $k ⊈ ran (v)$ ; if $v (s) \neq v (t)$ for some $s < t$ then $v (t) \neq k$ ; and if $v (s) = v (t)$ for some $s < t$ then $v (s) = v (u) = v (t)$ for all $s < u < t$ . In this way, ${i < k : (\exists t ⩽ s) [v (t) = i]}$ indicates the set of i enumerated at or before stage s. It is customary to write $C_{N}$ in place of $C_{ω}$ .

As noted by Brattka, Gherardi, and Pauly [1, Section 9.3], ${(C_{N})}^{(n - 1)}$ corresponds to induction for $Σ_{n}^{0}$ formulas, $I Σ_{n}^{0}$ , while ${(C_{2}^{})}^{(n - 1)}$ corresponds to bounding for $Σ_{n}^{0}$ formulas, $B Σ_{n}^{0}$ . As we will see, this correspondence extends to first-order parts in many, but not all, examples. Notice that for any $k \in ω \cup {ω}$ , $C_{k}$ belongs to $F$ , as does any combinations of $C_{k}$ under finite parallelizations and any number of jumps. (For finite parallelizations, we use a standard coding of finite sequences of unbounded length by numbers.)

In the context of classical reverse mathematics, we think of mathematical principles as “trivial” if they are provable in the base theory, typically ${RCA}_{0}$ . The analogous notion for problems under Weihrauch reducibility is that of being uniformly computable true. Let $Id : ω^{ω} \to ω^{ω}$ be the identity problem, i.e., $Id (f) = {f}$ for all $f \in ω^{ω}$ .
Definition 1.5.
Fix $P \in P$ .
$P$ is computably true* if $P ⩽_{c} Id$ , i.e., if every $P$ -instance f has an f-computable solution.

$P$ is uniformly computably true if $P ⩽_{W} Id$ , i.e., if there exists a Turing functional Γ such that $Γ (f) \in P (f)$ for every $f \in dom (P)$ .

In Section 3, we will explore problems whose first-order parts are trivial, and identify an even stronger property than being uniformly computably true that arguably aligns more closely with the reverse mathematics notion of triviality.

We end this section with one simple yet at first glance somewhat surprising application of isolating the class $F$ , which is otherwise unrelated to our discussion. This is that $F$ can be used to characterize computably true problems. Theorem 1.6.
A problem $P \in P$ is computably true if and only if there exists a $Q \in F$ such that $P ⩽_{W} Q$ .
Proof.
If $P ⩽_{W} Q$ for some $Q \in F$ then it is clear that $P$ is computably true. In the opposite direction, fix a computably true $P$ . Let $Q$ be the problem with the same instances as $P$ , with the solutions to an instance f being all $e \in ω$ such that $Φ_{e} (f) \in P (f)$ . Then $Q \in F$ and $P ⩽_{W} Q$ . □

2. Defining the first-order part

Restating the motivation from the preceding section, we would like the first-order part of a problem to correspond to the strongest first-order problem that Weihrauch reduces to it. The definition we now give does not resemble this, but we will prove that it captures the same idea.

Definition 2.1.
For $P \in P$ , the first-order part of $P$ , denoted by $^{1} P$ , is the following first-order problem:
the $^{1} P$ -instances are all triples $⟨ f, Φ, Ψ ⟩$ , where $f \in ω^{ω}$ and Φ and Ψ are Turing functionals such that $Φ (f) \in dom (P)$ and $Ψ (f, g) (0) ↓$ for all $g \in P (Φ (f))$ ;

the $^{1} P$ -solutions to any such $⟨ f, Φ, Ψ ⟩$ are all y such that $Ψ (f, g) (0) ↓ = y$ for some $g \in P (Φ (f))$ .

We proceed to our main theorem.
Theorem 2.2.
Fix $P \in P$ .
For every $Q \in F$ , if $Q ⩽_{W} P$ then $Q ⩽_{sW}^{1} P$ .

$^{1} P \equiv_{W} {max}_{⩽_{W}} {Q \in F : Q ⩽_{W} P}$ .

Proof.
For part (1), suppose $Q ⩽_{W} P$ for some $Q \in F$ , say via Φ and Ψ. We show that $Q ⩽_{sW}^{1} P$ . Map a given instance f of $Q$ to $⟨ f, Φ, Ψ ⟩$ . By assumption, $Φ (f)$ is an instance of $P$ and if g is any $P$ -solution to $Φ (f)$ then $Ψ (f, g)$ is a $Q$ -solution to f. As $Q$ is first-order, this solution is simply $Ψ (f, g) (0)$ . In particular, the latter converges, so $⟨ f, Φ, Ψ ⟩$ is an instance of $^{1} P$ . Now if y is any $^{1} P$ -solution to $⟨ f, Φ, Ψ ⟩$ then by definition $y = Ψ (f, g) (0)$ for some $P$ -solution g to $Φ (f)$ , so y is also a $Q$ -solution to f.

In light of part (1), to prove part (2) it suffices to show that $^{1} P ⩽_{W} P$ . To see this, we map a given $^{1} P$ -instance $⟨ f, Φ, Ψ ⟩$ to the $P$ -instance $Φ (f)$ . Then, we can map each $P$ -solution g to $Φ (f)$ to the output of the calculation $Ψ (f, g) (0)$ . By definition, the latter is a $^{1} P$ -solution to $⟨ f, Φ, Ψ ⟩$ . □

The following are immediate consequences of Definition 2.1 and the theorem.
Corollary 2.3.
If $P, Q \in P$ and $Q ⩽_{W} P$ then $^{1} Q ⩽_{sW}^{1} P$ . In particular, if $Q \equiv_{W} P$ then $^{1} Q \equiv_{sW}^{1} P$ .
Corollary 2.4.
If $P \in P$ and $P \equiv_{W} Q$ for some $Q \in F$ then $^{1} P \equiv_{W} P$ .

The behavior of the first-order part under the standard operations on the Weihrauch degrees was studied in detail by Soldà and Valenti [26]. In particular, they established the following basic bounds.
Proposition 2.5 (Soldà and Valenti [26], Propositions 4.1 and 4.4).

Fix $P, Q \in P$ .

$^{1} (P ⊔ Q) \equiv_{W}^{1} P ⊔^{1} Q$ .

$^{1} (P ⊓ Q) \equiv_{W}^{1} P ⊓^{1} Q$ .

$^{1} P \times^{1} Q ⩽_{W}^{1} (P \times Q)$ .

$^{1} P *^{1} Q ⩽_{W}^{1} (P * Q) ⩽_{W}^{1} P * Q$ .

$^{1} (P^{'}) ⩽_{sW} {(^{1} P)}^{'}$ .

No additional relations hold in general.

Let us now pass to one specific example. Recall that for $k ⩾ 1$ , ${RT}_{k}^{1}$ denotes the problem whose instances are all functions $c : ω \to k$ (called k-colorings or just colorings), with the solutions to any such c being all its infinite monochromatic sets, i.e., infinite sets $H \subseteq ω$ on which c is constant. (This is Ramsey’s theorem for k-colorings of singletons. We will discuss Ramsey’s theorem in more generality in Section 4.) There is a variant of this problem denoted ${BWT}_{k}$ , introduced by Brattka, Gherardi, and Marcone [1]. This has the same instances as those of ${RT}_{k}^{1}$ , but the solutions to any $c : ω \to k$ are all $i < k$ such that $c (x) = i$ for infinitely many x. Now, even though ${BWT}_{k}$ is first-order and ${RT}_{k}^{1}$ is not, it is easy to see that ${RT}_{k}^{1} \equiv_{W} {BWT}_{k}$ . (See, e.g., [5], Proposition 3.4, for a proof.) Hence, by Corollaries 2.3 and 2.4 we have that $^{1} {RT}_{k}^{1} \equiv_{sW}^{1} {BWT}_{k}$ and $^{1} {RT}_{k}^{1} \equiv_{W} {RT}_{k}^{1}$ .

We can characterize the first-order part of ${RT}_{k}^{1}$ in terms of more basic problems and operations from computable analysis. (This is our first example of such a characterization, but we will see others in the next two sections.) The following well-known result is due to Brattka, Gherardi, and Marcone [1]. For completeness, we include a proof here, which is also a bit more direct.

Proposition 2.6 (Brattka, Gherardi, and Marcone [1], Corollary 11.11).

For all $k ⩾ 1$ , ${BWT}_{k} \equiv_{sW} C_{k}^{'}$ .

Proof.
First, fix an instance of $C_{k}^{'}$ . Regard this as an $f \in ω^{ω}$ and a $Δ_{2}^{0, f}$ index for an $f^{'}$ -computable instance v of $C_{k}$ . The nonempty set $S = {i < k : (\forall s) [v (s) \neq i]}$ is then uniformly $Π_{2}^{0}$ in f. Let R be an f-computable predicate so that $i \in S$ if and only if $(\forall u) (\exists v) R (i, u, v)$ . Define an f-computable coloring $c : ω \to k$ as follows. Given $x \in ω$ , search for the least y such that $(\exists i < k) (\forall u < x) (\exists v < y) R (i, u, v)$ , and let $c (x)$ be the least witness i for this y. Now suppose $i < k$ is a ${BWT}_{k}$ -solution to c. Then in particular there are infinitely many x such that $(\forall u < x) (\exists v) R (i, u, v)$ and so $i \in S$ . It follows that i is a $C_{k}$ -solution to v, as wanted.

Conversely, fix an instance c of ${BWT}_{k}$ . Define $v : ω \to k + 1$ as follows: let $v (0) = k$ , and for all $s > 0$ , let $v (s) = i$ for the least $i < k$ such that $(\forall x > s) [c (x) \neq i]$ and $v (t) \neq i$ for any $t < s$ , or $v (s - 1)$ if no such i exists. Then v is a uniformly $c^{'}$ -computable instance of $C_{k}$ , so we can regard c together with a $Δ_{2}^{0, c}$ index for v as an instance of $C_{k}^{'}$ . Any $C_{k}$ -solution i to v is a ${BWT}_{k}$ -solution to c. □
Corollary 2.7.
For all $k ⩾ 1$ , $^{1} {RT}_{k}^{1} \equiv_{sW}^{1} {BWT}_{k} \equiv_{sW} C_{k}^{'}$ .

For $k ⩾ 2$ , one takeaway here is that while ${RT}_{k}^{1}$ has trivial first-order part as a $Π_{2}^{1}$ statement of second-order arithmetic, its first-order part in the present setting is non-trivial. Of course, ${RT}_{k}^{1}$ is itself trivial as a $Π_{2}^{1}$ statement, and nontrivial as a problem, so this is not so surprising. In the next two sections, we will see some more interesting examples of this phenomenon.

A further insight we can obtain from ${RT}_{k}^{1}$ is that, in general, it is false that $^{1} P ⩽_{sW} P$ , even for $P \in F$ . (Thus, Corollary 2.4 cannot be improved to $\equiv_{sW}$ , even if $P \equiv_{sW} Q$ there.)
Proposition 2.8.
For all $k ⩾ 2$ , $^{1} {BWT}_{k} ≰_{sW} {BWT}_{k}$ and $^{1} {BWT}_{k} ≰_{sW} {RT}_{k}^{1}$ .
Proof.
Fix $k ⩾ 2$ . To show that $^{1} {BWT}_{k} ≰_{sW} {BWT}_{k}$ , let Φ be the identity functional on $ω^{ω}$ . Let Ψ be a functional such that $Ψ (f, i) (0)$ is the least $x \in ω$ such that $f (x) = i$ , for all $f \in ω^{ω}$ and $i \in ω$ . So if c is an instance of ${BWT}_{k}$ and i is a solution to c then $Ψ (c, i) (0) ↓$ . It follows that $⟨ c, Φ, Ψ ⟩$ is an instance of $^{1} {BWT}_{k}$ for every such c. Now, suppose towards a contradiction that $^{1} {BWT}_{k} ⩽_{sW} {BWT}_{k}$ , say via $\hat{Φ}$ and $\hat{Ψ}$ . For each $x \in ω$ , let $c_{x} = 0^{x} 1^{ω}$ , viewed as a coloring $ω \to k$ . Then for each $x ⩽ k$ , we have by assumption that $\hat{Φ} (c_{x}, Φ, Ψ)$ is a ${BWT}_{k}$ -instance. There must then exist $x_{0} < x_{1} ⩽ k$ and $i < k$ such that $\hat{Φ} (c_{x_{0}}, Φ, Ψ)$ and $\hat{Φ} (c_{x_{1}}, Φ, Ψ)$ each have i as a ${BWT}_{k}$ -solution. Hence, $\hat{Ψ} (i)$ must be a $^{1} {BWT}_{k}$ -solution to both $⟨ c_{x_{0}}, Φ, Ψ ⟩$ and $⟨ c_{x_{1}}, Φ, Ψ ⟩$ . But since each of $c_{x_{0}}$ and $c_{x_{1}}$ has a unique ${BWT}_{k}$ -solution of 1, it follows that $⟨ c_{x_{0}}, Φ, Ψ ⟩$ and $⟨ c_{x_{1}}, Φ, Ψ ⟩$ have unique $^{1} {BWT}_{k}$ -solutions $x_{0}$ and $x_{1}$ , respectively, and $x_{0} \neq x_{1}$ . A similar (but simpler) argument shows that $^{1} {BWT}_{k} ≰_{sW} {RT}_{k}^{1}$ . □

Note that we do need both parts above because for $k ⩾ 2$ , ${BWT}_{k}$ and ${RT}_{k}^{1}$ are incomparable under strong Weihrauch reducibility. We are not aware of any explicit proof of this in the literature, but it is straightforward and routine. Trivially, $^{1} {BWT}_{1} \equiv_{sW} {BWT}_{1} \equiv_{sW} {RT}_{1}^{1}$ .
3. Uniform computable solvability and undiagonalizability

In this section, we explore a bit more the notion of being uniformly computable true (i.e., trivial under Weihrauch reducibility) and how it interacts with the first-order part of a problem. To begin, we connect this notion with the following one, which was introduced by Hirschfeldt and Jockusch [17] in an unrelated context.

Definition 3.1 (Hirschfeldt and Jockusch [17], Definition 4.11).

A problem $P$ is undiagonalizable if for every $P$ -instance f, the set of $σ \in ω^{< ω}$ that can be extended to a $P$ -solution $g \in ω^{ω}$ to f is uniformly $Δ_{1}^{0}$ in f (i.e., there is a Turing functional Γ such that $Γ (f) (σ) ↓ = i \in {0, 1}$ for all $P$ -instances f and all $σ \in ω^{< ω}$ , with $i = 1$ if and only if σ is an initial segment of $P$ -solution to f.)

Notice that any problem can be made undiagonalizable without changing the Turing degrees of its solutions, simply by replacing each solution by all finite modifications of it. In particular, there are many examples of such problems that are not themselves uniformly computably true, even non-uniformly so. This makes the next result striking.

Proposition 3.2.
Let $P \in P$ be undiagonalizable. Then $^{1} P$ is uniformly computably true.
Proof.
Fix a functional Γ witnessing that $P$ is undiagonalizable. Given any instance $⟨ f, Φ, Ψ ⟩$ of $^{1} P$ , search for the first $σ \in ω^{< ω}$ such that $Γ (Φ (f)) (σ) ↓ = 1$ and $Ψ (f, σ) (0) ↓$ . (The search must succeed since any sufficiently long initial segment of any $P$ -solution to $Φ (f)$ can serve as σ.) The value of $Ψ (f, σ) (0) ↓$ is then a $^{1} P$ -solution to $⟨ f, Φ, Ψ ⟩$ . □

As we will see, being undigonalizable somewhat better captures the idea of having trivial first-order part than simply having the first-order part be uniformly computably true.

The converse of Proposition 3.2 is false. In fact, being uniformly computably true does not even imply being Weihrauch reducible to an undiagonalizable problem. To see this, consider the thin set principle for 3-colorings of singletons, ${TS}_{3}^{1}$ . Its instances are all colorings $c : ω \to 3$ , and the solutions to any such c are all its infinite thin sets, i.e., infinite sets $T \subseteq ω$ such that $| c (T) | ⩽ 2$ . Hirschfeldt and Jockusch [17, p. 39] point out that ${TS}_{3}^{1}$ has what they call diagonalization opportunities (see [17, Definition 4.12]) and they show that no problem that has diagonalization opportunities is Weihrauch reducible to any undiagonalizable problem ([17, Theorem 4.13]). But $^{1} {TS}_{3}^{1}$ is uniformly computably true. Indeed, given an instance $⟨ f, Φ, Ψ ⟩$ of $^{1} {TS}_{3}^{1}$ with $Φ (f) = c : ω \to 3$ , we can search for $σ \in 2^{< ω}$ such that $c ↾ {x < | σ | : σ (x) = 1}$ is constant and $Ψ (f, σ) (0) ↓$ . Any monochromatic set for c is also thin for c, and any finite c-homogeneous set is extendible to an infinite c-thin one. Thus, the search must succeed and $Ψ (f, σ) (0)$ must be a $^{1} {TS}_{3}^{1}$ -solution to $⟨ f, Φ, Ψ ⟩$ .

We have the following immediate consequence of Proposition 3.2 and Corollary 2.4.
Corollary 3.3.
If $P \in P$ is undiagonalizable but not uniformly computably true then no $Q \in F$ satisfies $Q \equiv_{W} P$ .

This has an interesting application in that we can use it to see that in Theorem 1.6, we cannot in general replace $⩽_{W}$ by $\equiv_{W}$ . Indeed, consider any undiagonalizable problem that is computably true but not uniformly computably true. (For example, this can be the problem $^{FE} {RT}_{2}^{1}$ , introduced by Dzhafarov, Goh, Hirschfeldt, Patey, and Pauly [10], Definition 1.7. This is just ${RT}_{2}^{1}$ , but with solutions replaced by all infinite sets that are homogeneous modulo finitely many errors.) By Theorem 1.6, there is a $Q \in F$ such that $P ⩽_{W} Q$ , but by the preceding corollary, no such $Q$ satisfies $P \equiv_{W} Q$ .

Let us next look at some better-known examples of undiagonalizable problems. We recall some definitions.
Definition 3.4.

A set $X \subseteq ω$ is cohesive for a family $⟨ A_{i} : i \in ω ⟩$ of subsets of ω if for all i, either $X \cap A_{i}$ or $X \cap {\overline{A}}_{i}$ is finite.

A family of sets $⟨ B_{i} : i \in ω ⟩$ is a subfamily of a family of sets $⟨ A_{i} : i \in ω ⟩$ if $(\forall i) (\exists j) [B_{i} = A_{j}]$ . We write $⟨ B_{i} : i \in ω ⟩ \subseteq ⟨ A_{i} : i \in ω ⟩$ .

A family of sets $⟨ A_{i} : i \in ω ⟩$ has the finite intersection property if $⋂_{i \in F} A_{i} \neq \emptyset$ for every nonempty finite set F.

We emphasize that all families of sets considered above are indexed by ω, and that the definition of ⊆ for subfamilies need not preserve order or multiplicity of members.

The following problems come from the reverse mathematics literature, but have also been studied to a lesser extend in the context of Weihrauch reducibility.
Definition 3.5.

$COH$ is the problem whose instances are all families of sets $⟨ A_{i} : i \in ω ⟩$ , with the solutions being all the infinite cohesive sets for this family.

$FIP$ is the problem whose instances are all families of sets $⟨ A_{i} : i \in ω ⟩$ , not all empty, with the solutions being all the ⊆-maximal subfamilies of $⟨ A_{i} : i \in ω ⟩$ that have the finite intersection property.

$Π_{1}^{0} G$ is the principle whose instances are all $f \in ω^{ω}$ and all $Π_{1}^{0, f}$ -definable families $⟨ U_{i} : i \in ω ⟩$ of dense subsets of $2^{< ω}$ , with the solutions being all sets $G \subseteq ω$ that meet every $U_{i}$ (i.e., $(\forall i) (\exists k) [G ↾ k \in U_{i}]$ ).

(See, e.g., [12], Section 8.4.2 for a broader discussion of $COH$ , and Section 9.10.3 for a broader discussion of $FIP$ and $Π_{1}^{0} G$ .) $COH$ and $Π_{1}^{0} G$ are undiagonalizable because every finite binary string can be continued to a solution of a given instance. Dzhafarov and Mummert [11, Proposition 4.2] showed that, as $Π_{2}^{1}$ principles, $FIP$ is implied by $Π_{1}^{0} G$ over ${RCA}_{0}$ , and their proof actually shows that $FIP ⩽_{W} Π_{1}^{0} G$ as problems. $FIP$ is not itself undiagonalizable, but it turns out to be undiagonalizable up to Weihrauch equivalence. Indeed, $FIP$ clearly satisfies the weaker property in the hypothesis of the following result.
Proposition 3.6.
Let $P$ be a problem such that the set of $σ \in ω^{< ω}$ that can be extended to a $P$ -solution $g \in ω^{ω}$ to a $P$ -instance f is uniformly $Σ_{1}^{0}$ in f. Then there is an undiagonalizable problem $Q$ such that $P \equiv_{W} Q$ .
Proof.
Fix $P$ , and let $W_{e}$ be such that for every $P$ -instance f, $W_{e}^{f}$ is the set of all the initial segments of the $P$ -solutions to f. Let $Q$ be the problem with the same instances as $P$ , but with the solutions to a $Q$ -instance f being all sequences of the form $⟨ s_{0}, σ_{0} ⟩ ⟨ s_{1}, σ_{1} ⟩ \dots \in ω^{ω}$ such that $s_{0} ⩽ s_{1} ⩽ \dots$ , $σ_{0} ≺ σ_{1} ≺ \dots$ , $σ_{k} \in W_{e}^{f} [s_{k}]$ for every k, and $⋃_{k \in ω} σ_{k}$ is a $P$ -solution to f. It is easy to see that $Q$ is undiagonalizable and that $P \equiv_{W} Q$ . □

It follows that $FIP$ is Weihrauch equivalent to an undiagonalizable problem. By Proposition 3.2, we can now conclude the following.
Corollary 3.7.
Each of $^{1} COH$ , $^{1} FIP$ , and $^{1} Π_{1}^{0} G$ is uniformly computably true.

The corollary nicely meshes with what is known about the first-order parts of $COH$ , $FIP$ , and $Π_{1}^{0} G$ as $Π_{2}^{1}$ statements of second-order arithmetic. Each of these principles is $Π_{1}^{1}$ -conservative over ${RCA}_{0}$ . For $COH$ , this fact is due to Cholak, Jockusch, and Slaman [6, Theorem 9.1]. For $Π_{1}^{0} G$ , it is due for Hirschfeldt, Shore, and Slaman [18, Theorem 3.13 and the comment on p. 5824]. The latter also implies this fact for $FIP$ . Thus, in these cases, the first-order strengths agree between the classical reverse mathematics and Weihrauch analysis settings: they are trivial.

We wrap up this section by looking at how being uniformly computably true and being undiagonalizable behave under the standard operations on Weihrauch degrees. Proposition 3.8.
Fix $P, Q \in P$ with $^{1} Q$ uniformly computably true.
$^{1} (P ⊔ Q) ⩽_{W}^{1} P$ .

$^{1} (P ⊓ Q) ⩽_{W}^{1} P$ .

$^{1} P \times^{1} Q ⩽_{W}^{1} P$ .

$^{1} P ^{1} Q ⩽_{W}^{1} P$ .

$^{1} Q ^{1} P \equiv_{W}^{1} (Q * P) \equiv_{W}^{1} P$ .
If $Q$ is undiagonalizable, then additionally $^{1} (P \times Q) ⩽_{W}^{1} P$ .
Proof.
The first four parts are straightforward, using Proposition 2.5 in the case of parts (1) and (2). Also by Proposition 2.5, we have that $^{1} Q ^{1} P ⩽_{W}^{1} (Q P) ⩽_{W}^{1} Q * P$ . Since $^{1} Q$ is uniformly computably true, $^{1} Q * P ⩽_{W} P$ . Now (5) follows because $^{1} Q ^{1} P$ and $^{1} (Q P)$ are first-order.

Now suppose $Q$ is undiagonalizable. We reduce $^{1} (P \times Q)$ to $P$ , which suffices. First, fix an instance $⟨ f, Φ, Ψ ⟩$ of $^{1} (P \times Q)$ , so that $Φ (f)$ is an instance $⟨ f_{0}, f_{1} ⟩$ of $P \times Q$ . We map this to the $P$ -instance $f_{0}$ . Given any $P$ -solution g to $f_{0}$ , we search for an initial segment $σ \in ω^{< ω}$ of a $Q$ -solution to $f_{1}$ such that $Ψ (f, ⟨ g, σ ⟩) (0) ↓$ . Note that this search is uniformly computable in f since $Q$ is undiagonalizable, and it must succeed since any sufficiently long initial segment of any $Q$ -solution to $f_{1}$ would work. The value of $Ψ (f, ⟨ g, σ ⟩) (0)$ is then a $^{1} (P \times Q)$ -solution to $⟨ f, Φ, Ψ ⟩$ . □

4. Additional case studies

We have already classified the first-order parts of several problems whose first-order parts as theorems of second-order arithmetic were previously known. In this section, we look at several more examples. We begin with weak König’s lemma, $WKL$ . As a theorem, $WKL$ is famously $Π_{1}^{1}$ -conservative over ${RCA}_{0}$ . (This is Harrington’s theorem; see [16, Section 7.2] or [12, Section 7.7].) Unlike $COH$ , $FIP$ , and $Π_{1}^{0} G$ from Section 3, $WKL$ is not undiagonalizable, so it does not follow that its first-order part as a problem is also trivial, and indeed this turns out not to be the case. In the following theorem, we recall that weak weak König’s lemma, $WWKL$ , is $WKL$ with instances restricted to trees $T \subseteq 2^{< ω}$ so that $[T] \subseteq 2^{ω}$ has positive Lebesgue measure.

Theorem 4.1.

For all $n \in ω$ , we have $\begin{matrix} ^{1} ({WWKL}^{(n)}) \equiv_{sW}^{1} ({WKL}^{(n)}) \equiv_{sW} {(C_{2}^{*})}^{(n)} . \end{matrix}$

Proof.

Fix n. We first show that ${(C_{2}^{*})}^{(n)} ⩽_{sW}^{1} ({WWKL}^{(n)})$ . By Theorem 2.2, since ${(C_{2}^{*})}^{(n)} \in F$ , we can just show that ${(C_{2}^{*})}^{(n)} ⩽_{sW} {WWKL}^{(n)}$ . And since the jump operator is monotone on $⩽_{sW}$ , it suffices to show that $C_{2}^{*} ⩽_{sW} WWKL$ . To this end, let $⟨ v_{0}, \dots, v_{k - 1} ⟩$ be any instance of $C_{2}^{*}$ . Define T to be the set of all $σ \in 2^{< ω}$ such that for all $e < | σ |$ , $\begin{matrix} σ (e) = \{\begin{array}{ll} 0 & if e < k, \\ 1 & if e = k, \\ 1 - v_{e - k - 1} (| σ |) & if k < e ⩽ 2 k and v_{e - k - 1} (| σ |) < 2 . \end{array} \end{matrix}$ Note that if $σ \in T$ and $v_{e - k - 1} (| τ |) \neq v_{e - k - 1} (| σ |)$ for some $k < e ⩽ 2 k$ and some $τ ⪯ σ$ then necessarily $v_{e - k - 1} (| τ |) = 2$ , so trivially $τ \in T$ . Hence, T is a tree. Furthermore, by construction, the elements of $[T]$ are precisely the sequences of the form $0^{k} 1 x_{0} \dots x_{k - 1} g$ , where $⟨ x_{0}, \dots, x_{k - 1} ⟩$ is a $C_{2}^{*}$ -solution to $⟨ v_{0}, \dots, v_{k - 1} ⟩$ and $g \in 2^{ω}$ is arbitrary. It follows that the measure of $[T]$ is at least $2^{- 2 k - 1}$ and so T is an instance of $WWKL$ . Now if p is any $WWKL$ -solution to T then k can be computably recovered as the least e such that $p (e) = 1$ , and then $⟨ p (k + e + 1) : e < k ⟩$ is a $C_{2}^{*}$ -solution to $⟨ v_{0}, \dots, v_{k - 1} ⟩$ .

That $^{1} ({WWKL}^{(n)}) ⩽_{sW}^{1} ({WKL}^{(n)})$ is clear. It therefore remains only to show that $^{1} ({WKL}^{(n)}) ⩽_{sW} {(C_{2}^{*})}^{(n)}$ . By Proposition 2.5, $^{1} ({WKL}^{(n)}) ⩽_{sW} {(^{1} WKL)}^{(n)}$ , so by the monotonicity of the jump operator on $⩽_{sW}$ , it suffices to show that $^{1} WKL ⩽_{sW} C_{2}^{*}$ . We will work with the problem ${DNR}_{2}$ instead of $WKL$ , whose instances are all $g \in ω^{ω}$ , with the solutions to any such g being all ${0, 1}$ -valued functions that are diagonally noncomputable relative to g (hereafter abbreviated ${DNC}^{g}$ ). By results of Brattka, Hendtlass, and Kreuzer [3, Corollary 5.3], $WKL \equiv_{sW} {DNR}_{2}$

Consider an instance of $^{1} {DNR}_{2}$ . Since the instances of ${DNR}_{2}$ range over all elements of $ω^{ω}$ , we may regard this simply as a pair $⟨ g, Ψ ⟩$ where $g \in ω^{ω}$ and $Ψ (g, p) (0) ↓$ for every ${0, 1}$ -valued ${DNC}^{g}$ function p. Here, Ψ is given by an index, i. Let $T \subseteq 2^{< ω}$ be the standard g-computable tree whose paths are precisely the ${0, 1}$ -valued ${DNC}^{g}$ functions.

By compactness, there is a k such that $Ψ (g, σ) (0) ↓$ for every $σ \in T$ of length k. We have to encode i, k, and $g ↾ k$ into the solutions of an instance of $C_{2}^{*}$ . For each $e < k$ , define $w_{e} : ω \to 3$ by $\begin{matrix} w_{e} (s) = \{\begin{array}{ll} 2 & if Φ_{e} (g) (e) [s] ↑, \\ min {Φ_{e} (g) (e) [s], 1} & otherwise, \end{array} \end{matrix}$ for all s. Thus, each $w_{e}$ is an instance of $C_{2}$ , and $1 - {lim}_{s} w_{e} (s) \neq Φ_{e} (g) (e)$ if the latter converges.

Now consider the sequence $\begin{matrix} {1^{i}}^{⌢} 0^{⌢} {⟨ 1 - g (e) : e < k ⟩}^{⌢} ⟨ w_{e} : e < k ⟩, \end{matrix}$ where we regard each of 0, 1, and $1 - g (e)$ as a constant function $ω \to 3$ . So we have an instance $\vec{v} = ⟨ v_{j} : j < i + 1 + 2 k ⟩$ of $C_{2}^{*}$ . Since k and each $w_{e}$ can be uniformly computed from our $^{1} {DNR}_{2}$ -instance $⟨ g, i ⟩$ , it follows that we can uniformly compute $\vec{v}$ from this data. This is then our desired instance of $C_{2}^{*}$ .

Finally, let $⟨ x_{j} : j < i + 1 + 2 k ⟩$ be any solution to this instance. Since $x_{j} \neq {lim}_{s} v_{j} (s)$ , we can computably recover i as the least j such that $x_{j} = 1$ . Using i and the length of the solution, we can next also recover k and $g ↾ k$ . Finally, as remarked above, for $i + 1 + k ⩽ j < i + 1 + 2 k$ we must have $x_{j} \neq Φ_{j - i - 1 - k} (g) (j - i - 1 - k)$ . In other words, the string $σ \in 2^{k}$ defined by $σ (e) = x_{i + 1 + k + e}$ for all $e < k$ belongs to T, and is extendible in T, and so $Ψ (g ↾ k, σ) (0) ↓$ by choice of k. By assumption on Ψ, the value of this computation is a $^{1} {DNR}_{2}$ -solution to the instance we started with. Since we have shown that we can uniformly computably obtain this value from $⟨ x_{j} : j < i + 1 + 2 k ⟩$ , the proof is complete. □

The preceding result refines the $Π_{1}^{1}$ -conservation of $WKL$ mentioned above in an interesting way. Namely, it is known that $WKL$ is $Π_{1}^{1}$ -conservative not only over ${RCA}_{0}$ , but also over ${RCA}_{0}^{*} + I Σ_{n}^{0}$ and ${RCA}_{0}^{*} + B Σ_{n}^{0}$ , for all $n ⩾ 1$ . (See Hájek [15, Corollary 3.14] and Simpson and Smith [23, Corollary 4.7].) More recently, Fiori-Carones, Kołodziejczyk, Wong, and Yokoyama [13, Lemma 4.5] defined a version of $WKL$ for $Δ_{n}^{0}$ -definable trees, and proved that this is also $Π_{1}^{1}$ -conservative over ${RCA}_{0}^{*} + B Σ_{n}^{0}$ . Recall that in that Weihrauch degrees, ${(C_{2}^{*})}^{(n - 1)}$ corresponds to $B Σ_{n}^{0}$ , so our theorem above is precisely analogous to the latter result.

We next turn to the arithmetical comprehension axiom, $ACA$ , from reverse mathematics. Formally, this is ${RCA}_{0}$ plus comprehension for all arithmetically-definable subsets of numbers. Often, it is presented in the form $(\forall X) [X^{'} exists]$ , which relies on a formalization of computability theory in the base theory ${RCA}_{0}$ . (See [12, Corollary 5.6.3].) This in turn has an obvious problem form as the Turing jump problem, $TJ$ , whose instances are all $g \in ω^{ω}$ , with the unique solution to any such g being $g^{'}$ . But ${ACA}_{0}$ is also equivalent to the statement $(\forall X) [X^{(n + 1)} exists]$ , for any $n \in ω$ , so it could just as well be represented by ${TJ}^{(n)}$ or even $⨆_{n \in ω} {TJ}^{(n)}$ .

Theorem 4.2.

For all $n \in ω$ , $\begin{matrix} ^{1} ({TJ}^{(n)}) \equiv_{sW} C_{N}^{(n)} . \end{matrix}$

Proof.

First, we show that $^{1} ({TJ}^{(n)}) ⩽_{sW} C_{N}^{(n)}$ . By Proposition 2.5 and the monotonicity of the jump operator on $⩽_{sW}$ , it suffices to show that $^{1} TJ ⩽_{sW} C_{N}$ . So fix an instance of $^{1} TJ$ , which we may just think of as a pair $⟨ g, Ψ ⟩$ where $g \in ω^{ω}$ and $Ψ (g, g^{'}) (0) ↓$ . Let $m : ω \to ω$ be a g-computable limit approximation to the value of $Ψ (g, g^{'}) (0)$ . Define $v : ω \to ω$ as follows. For each s, find the least k such that $⟨ k, m (s) ⟩ \notin ran (v ↾ s)$ , and then let $v (s)$ be the least x different from $⟨ k, m (s) ⟩$ and not in the range of $v ↾ s$ . Note that since $y = {lim}_{s} m (s)$ exists, there is a k such that $⟨ k, y ⟩ \notin ran (v)$ . By construction, every $x \neq ⟨ k, y ⟩$ does belong to $ran (v)$ . Thus, v is an instance of $C_{N}$ with $⟨ k, y ⟩$ as its only solution. Moreover, v is uniformly computable from g because m is, as desired.

By Theorem 2.2, since $C_{N}^{(n)} \in F$ , to show that $C_{N}^{(n)} ⩽_{sW}^{1} ({TJ}^{(n)})$ it suffices to show that $C_{N}^{(n)} ⩽_{sW} {TJ}^{(n)}$ . By the monotonicity of the jump operator on $⩽_{sW}$ , for this it in turn suffices to show that $C_{N} ⩽_{sW} TJ$ . This is straightforward. □

Note that what the above actually shows is that $C_{N}^{(n)} ⩽_{sW} {TJ}^{(n)} ⩽_{sW} {UC}_{N}^{(n)}$ , where ${UC}_{N}^{(n)}$ is the unique choice problem on $N$ , or $C_{N}$ restricted to instances with unique solutions. For completeness we note that the fact that $C_{N} \equiv_{sW} {UC}_{N}$ is well-known; see, e.g., Brattka, Gherardi, and Pauly [2, Theorem 7.13].

Corollary 4.3.

$^{1} ⨆_{n \in ω} {TJ}^{(n)} \equiv_{sW} ⨆_{n \in ω} C_{N}^{(n)}$ .

As is well-known, ${ACA}_{0}$ is $Π_{1}^{1}$ -conservative over Peano arithmetic, $PA$ . (See, e.g., [16, Corollary 7.5] for a proof.) Effectively, this means that the first-order strength of ${ACA}_{0}$ is arithmetical induction. Corollary 4.3 bears this out very directly, while Theorem 4.2 can then be seen as a stratification of this result that is impossible to extract in the classical reverse mathematics setting.

For our final case study, we look at Ramsey’s theorem, which has been the subject of much study in reverse mathematics and computable analysis. (A detailed overview can be found in [12, Chapter 8 and Section 9.1].)

Definition 4.4.

Fix $X \subseteq ω$ and $n, k ⩾ 1$ .

${[X]}^{n}$ denotes the set of all $⟨ x_{0}, \dots, x_{n - 1} ⟩ \in X^{n}$ with $x_{0} < \dots < x_{n - 1}$ .

A k-coloring (or coloring for short) of ${[X]}^{n}$ is a map $c : {[X]}^{n} \to k$ .

A k-coloring $c : {[X]}^{n} \to k$ is stable if for all $x \in {[X]}^{n - 1}$ , ${lim}_{s} c (\vec{x}, s)$ exists.

A set $Y \subseteq X$ is homogeneous for $c : {[X]}^{n} \to k$ if $c ↾ {[Y]}^{n}$ is constant.

${RT}_{k}^{n}$ is the problem whose instances are all colorings $c : {[ω]}^{n} \to k$ , with the solutions to any such c being all its infinite homogeneous sets.

${SRT}_{k}^{n}$ is the restriction of ${RT}_{k}^{n}$ to stable colorings.

${RT}_{+}^{n} = ⨆_{k ⩾ 2} {RT}_{k}^{n}$ and ${SRT}_{+}^{n} = ⨆_{k ⩾ 2} {SRT}_{k}^{n}$ .

${RT}_{N}^{n} = ⋃_{k ⩾ 2} {RT}_{k}^{n}$ and ${SRT}_{N}^{n} = ⋃_{k ⩾ 2} {SRT}_{k}^{n}$ .

The variants ${RT}_{+}^{n}$ and ${RT}_{N}^{n}$ were introduced by Brattka and Rakotoniaina [5, Definition 3.1]. In both, the instances are k-colorings of exponent n for some k, with the difference being merely that in ${RT}_{+}^{n}$ , this k is specified as part of the instance, whereas in ${RT}_{N}^{n}$ it is not. Thus, ${RT}_{+}^{n} ⩽_{W} {RT}_{N}^{n}$ , and Brattka and Rakotoniaina [5, Corollary 4.23] proved that ${RT}_{N}^{n} ≰_{W} {RT}_{+}^{n}$ . But both problems correspond to one and the same $Π_{2}^{1}$ statement of second-order arithmetic, namely $(\forall k) {RT}_{k}^{n}$ , which is denoted in the reverse mathematics literature by ${RT}^{n}$ or ${RT}_{< \infty}^{n}$ . Analogously for the stable variants, ${SRT}_{+}^{n}$ and ${SRT}_{N}^{n}$ .

The upper bounds in the following theorem were obtained independently by Soldà and Valenti [26, Section 7.1], who were looking instead at the problems ${RT}_{k}^{n}$ and ${SRT}_{k}^{n}$ for finite values of k. The upper bound in the case $n = 0$ was also obtained, by different means, by Brattka and Rakotoniaina [5].

Theorem 4.5.

For all $n ⩾ 1$ , we have $\begin{matrix} {(C_{2}^{(n)})}^{*} ⩽_{W}^{1} {SRT}_{N}^{n} ⩽_{W}^{1} {RT}_{N}^{n} ⩽_{W} {(C_{2}^{*})}^{(n)} \end{matrix}$ and $\begin{matrix} {(C_{2}^{(n)})}^{*} ⩽_{W}^{1} {SRT}_{+}^{n} ⩽_{W}^{1} {RT}_{+}^{n} ⩽_{W} {(C_{2}^{*})}^{(n)} . \end{matrix}$

Proof.

Fix n. We have ${SRT}_{+}^{n} ⩽_{W} {SRT}_{N}^{n} ⩽_{W} {RT}_{N}^{n}$ and ${SRT}_{+}^{n} ⩽_{W} {RT}_{+}^{n} ⩽_{W} {RT}_{N}^{n}$ . Ergo, since ${(C_{2}^{(n)})}^{*} \in F$ , it suffices to show that ${(C_{2}^{(n)})}^{*} ⩽_{W} {SRT}_{+}^{n}$ , and that $^{1} {RT}_{N}^{n} ⩽_{W} {(C_{2}^{*})}^{(n)}$ .

For the first reduction, we first note that by Proposition 2.6 and the monotonicity of the jump operator on $⩽_{sW}$ we have $C_{2}^{(n)} ⩽_{sW} {BWT}_{2}^{(n - 1)}$ . By a result of Brattka and Rakotoniaina [5, Theorem 3.5], ${BWT}_{2}^{(n - 1)} ⩽_{W} {SRT}_{2}^{n}$ . (To see this, consider any instance of ${BWT}_{2}^{(n - 1)}$ . We regard this as a sequence $⟨ c_{\vec{s}} : \vec{s} \in ω^{n - 1} ⟩$ of colorings $c_{\vec{s}} : ω \to 2$ such that ${lim}_{\vec{s}} c_{\vec{s}} (x)$ exists for every x. Denote this limit by $c (x)$ , thereby defining a coloring $c : ω \to 2$ . We define a coloring $d : {[ω]}^{n} \to 2$ by $d (x, \vec{s}) = c_{\vec{s}} (x)$ . Then d is an instance of ${SRT}_{2}^{n}$ uniformly computable from $⟨ c_{\vec{s}} : \vec{s} \in ω^{n - 1} ⟩$ with the property that ${lim}_{\vec{s}} d (x, \vec{s}) = c (x)$ for all x. Now if H is any ${SRT}_{2}^{n}$ -solution for d then $d (H) = {lim}_{\vec{s}} d (x, \vec{s})$ for every $x \in H$ , so H is an infinite homogeneous for c with color $d (H)$ . We have that $d (H)$ is uniformly computable from $d \oplus H$ , which is in turn uniformly computable from $⟨ c_{\vec{s}} : \vec{s} \in ω^{n - 1} ⟩ \oplus H$ . Thus, $d (H)$ is a ${BWT}_{2}^{(n - 1)}$ -solution to $⟨ c_{\vec{s}} : \vec{s} \in ω^{n - 1} ⟩$ , as wanted.) We can thus also conclude that ${(C_{2}^{(n)})}^{*} ⩽_{W} {({SRT}_{2}^{n})}^{*}$ . But for any $k ⩾ 1$ , the k-fold product ${SRT}_{2}^{n} \times \dots \times {SRT}_{2}^{n}$ is Weihrauch reducible to ${SRT}_{2^{k}}^{n}$ . (See, e.g., Dorais et al. [8], Proposition 2.1.) Thus, ${({SRT}_{2}^{n})}^{*} ⩽_{W} {SRT}_{+}^{n}$ and so also ${(C_{2}^{(n)})}^{*} ⩽_{W} {SRT}_{+}^{n}$ . This is what was to be shown.

We next show that $^{1} {RT}_{N}^{n} ⩽_{W} {(C_{2}^{*})}^{(n)}$ . As shown by Wang [27, Theorem 4.2] and independently by Brattka and Rakotoniaina [5, Corollary 4.15], we have ${RT}_{N}^{n} ⩽_{W} {WKL}^{(n)}$ . Thus $^{1} {RT}_{N}^{n} ⩽_{W}^{1} {WKL}^{(n)}$ , and now the desired conclusion follows by Theorem 4.1. □

In reverse mathematics, the first-order parts of ${SRT}_{< \infty}^{n}$ and ${RT}_{< \infty}^{n}$ are now fully understood. Hirst [19, Theorem 6.4] showed that ${RT}_{< \infty}^{1}$ is equivalent over ${RCA}_{0}$ to $B Σ_{2}^{0}$ , and so this is its first-order part. By results of Jockusch [20, Lemma 5.9] and Simpson [22, Theorem III.7.6], if $n ⩾ 3$ then ${RT}_{< \infty}^{n}$ is equivalent over ${RCA}_{0}$ to ${ACA}_{0}$ , and so the first-order part of ${RT}_{< \infty}^{n}$ is arithmetical induction. For $n = 2$ , the classification is more recent. Cholak, Jockusch, and Slaman [6, Theorem 11.4] showed that ${SRT}_{< \infty}^{2}$ implies $B Σ_{3}^{0}$ , while Slaman and Yokoyama [24, Theorem 2.1] showed that ${RT}_{< \infty}^{2}$ is $Π_{1}^{1}$ -conservative over ${RCA}_{0} + B Σ_{3}^{0}$ . In light of the correspondence, mentioned in Section 1, between induction and bounding schemes on the one hand, and jumps of choice problems on the other, these bounds comport with those given by Theorem 4.5. However, the theorem leaves a gap, as ${(C_{2}^{*})}^{(n)} ≰_{W} {(C_{2}^{(n)})}^{*}$ when $n ⩾ 1$ . (We leave this as an exercise to the reader. In both problems, instances are finite sequences of approximations to instances of $C_{2}^{*}$ . But in the case of ${(C_{2}^{(n)})}^{*}$ the length of each such sequences is explicitly a part of the instance, while in the case of ${(C_{2}^{*})}^{(n)}$ the length is itself approximated.) This gap raises the following question, with which we conclude.

Question 4.6.

Can the first-order parts of ${SRT}_{+}^{n}$ , ${RT}_{+}^{n}$ , ${SRT}_{N}^{n}$ , and ${RT}_{N}^{n}$ be more precisely characterized?

Footnotes

Acknowledgements

Dzhafarov and Solomon were partially supported by a Focused Research Group grant from the National Science Foundation of the United States, DMS-1854355. Yokoyama was partially supported by JSPS KAKENHI grants, numbers JP19K03601 and JP21KK0045. The authors thank Ludovic Levy Patey, Alberto Marcone, and Manlio Valenti for helpful comments during the preparation of this paper. They also thank the two anonymous referees for their valuable feedback and suggestions for improvement.

References

Brattka,

Gherardi and

Marcone, The Bolzano–Weierstrass theorem is the jump of weak Kőnig’s lemma, Ann. Pure Appl. Logic163(6) (2012), 623–655. doi:10.1016/j.apal.2011.10.006.

Brattka,

Gherardi and

Pauly, Weihrauch complexity in computable analysis. in: Handbook of Computability and Complexity in Analysis, Theory Appl. Comput.2021, 367–417.

Brattka,

Hendtlass and

A.P.

Kreuzer, On the uniform computational content of computability theory, Theory Comput. Syst.61(4) (2017), 1376–1426. doi:10.1007/s00224-017-9798-1.

Brattka and

Pauly, On the algebraic structure of Weihrauch degrees, Log. Methods Comput. Sci., to appear.

Brattka and

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

P.A.

Cholak,

C.G.

Jockusch and

T.A.

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

Cipriani,

Marcone and

Valenti, The Weihrauch lattice at the level of

Π_{1}^{1} - {CA}_{0}

: The Cantor–Bendixson theorem.

F.G.

Dorais,

D.D.

Dzhafarov,

J.L.

Hirst,

J.R.

Mileti and

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

R.G.

Downey and

D.R.

Hirschfeldt, Algorithmic Randomness and Complexity, Theory and Applications of Computability, Springer, New York, 2010.

10.

D.D.

Dzhafarov,

Le Goh,

D.R.

Hirschfeldt,

Patey and

Pauly, Ramsey’s theorem and products in the Weihrauch degrees, Computability9(2) (2020), 85–110. doi:10.3233/COM-180203.

11.

D.D.

Dzhafarov and

Mummert, On the strength of the finite intersection principle, Israel J. Math.196(1) (2013), 345–361. doi:10.1007/s11856-012-0150-9.

12.

D.D.

Dzhafarov and

Mummert, Reverse Mathematics: Problems, Reductions, and Proofs, Theory and Applications of Computability, Springer, New York, 2022.

13.

Fiori-Carones,

L.A.

Kołodziejczyk,

T.L.

Wong and

Yokoyama, An isomorphism theorem for models of Weak König’s lemma without primitive recursion, J. Europ. Math. Soc. (2021).

14.

Gherardi and

Marcone, How incomputable is the separable Hahn–Banach theorem? in: Proceedings of the Fifth International Conference on Computability and Complexity in Analysis (CCA 2008), Electron. Notes Theor. Comput. Sci., Vol. 221, Elsevier Sci. B. V., Amsterdam, 2008, pp. 85–102.

15.

Hájek, Interpretability and fragments of arithmetic, in: Arithmetic, Proof Theory, and Computational Complexity, Prague, 1991, Oxford Logic Guides, Vol. 23, Oxford Univ. Press, New York, 1993, pp. 185–196.

16.

D.R.

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

17.

D.R.

Hirschfeldt and

C.G.

JockuschJr., On notions of computability-theoretic reduction between

Π_{2}^{1}

principles, J. Math. Log.16(1) (2016), 1650002, 59.

18.

D.R.

Hirschfeldt,

R.A.

Shore and

T.A.

Slaman, The atomic model theorem and type omitting, Trans. Amer. Math. Soc.361(11) (2009), 5805–5837. doi:10.1090/S0002-9947-09-04847-8.

19.

J.L.

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

20.

C.G.

Jockusch, Jr. Ramsey’s theorem and recursion theory, J. Symbolic Logic37 (1972), 268–280. doi:10.2307/2272972.

21.

Le Goh,

Pauly and

Valenti, Finding descending sequences through ill-founded linear orders, J. Symb. Log.86(2) (2021), 817–854. doi:10.1017/jsl.2021.15.

22.

S.G.

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

23.

S.G.

Simpson and

R.L.

Smith, Factorization of polynomials and

Σ_{1}^{0}

induction, in: Special issue: Second Southeast Asian logic conference, Bangkok, 1984, Vol. 31, 1986, pp. 289–306.

24.

T.A.

Slaman and

Yokoyama, The strength of Ramsey’s theorem for pairs and arbitrarily many colors, J. Symb. Log.83(4) (2018), 1610–1617. doi:10.1017/jsl.2018.19.

25.

R.I.

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

26.

Solda and

Valenti, Algebraic properties of the first-order part of a problem, Ann. Pure Appl. Logic174(7) (2023), 103270.

27.

Wang, Some reverse mathematics of rainbow Ramsey theorems, unpublished.