Compositions of multivalued functions

Abstract

In reverse mathematics, one sometimes encounters proofs which invoke some theorem multiple times in series, or invoke different theorems in series. One example is the standard proof that Ramsey’s theorem for 2 colors implies Ramsey’s theorem for 3 colors. A natural question is whether such repeated applications are necessary. Questions like this can be studied under the framework of Weihrauch reducibility. For example, one can attempt to capture the notion of one multivalued function being uniformly reducible to multiple instances of another multivalued function in series. There are three known ways to formalize this notion: the compositional product, the reduction game, and the step product. We clarify the relationships between them by giving sufficient conditions for them to be equivalent. We also show that they are not equivalent in general.

Keywords

Weihrauch reducibility compositional product reduction game step product

1. Introduction

Many mathematical theorems can be thought of as problems; that is, they have the form “for every instance X, there exists a solution Y”. For example, instances of the intermediate value theorem (on $[0, 1]$ ) are continuous functions $f : [0, 1] \to R$ such that 0 lies strictly between $f (0)$ and $f (1)$ , and solutions to f are zeroes of f. Another example is König’s lemma, which states that every infinite finitely branching tree has an infinite path. Instances of König’s lemma are infinite finitely branching trees T, and solutions to T are infinite paths on T.

What would it mean to solve a problem? Given an instance of the problem, we must provide some solution to said instance. Since each instance of a problem may have many solutions, there may be many possible mappings which take each instance to a solution. Intuitively, a problem is easily solvable if some such mapping can be constructed in a simple way.

This gives us a way to study the computational content of theorems: we study how difficult it is to solve the associated problem. The machinery to do the latter was first studied by computable analysts: for many theorems of interest, the instances and solutions of their associated problems can be represented as elements of Baire space $N^{N}$ . The problems are then (possibly partial) multivalued functions on $N^{N}$ , and the realizers are single-valued functions on $N^{N}$ with the same domain.

We are particularly interested in the relative computational strength of problems. Given any realizer for problem Q, can we computably transform it into some realizer for problem P? In order to formalize this, we will use a reducibility relation known as Weihrauch reducibility.

Our interest in comparing mathematical theorems up to Weihrauch reducibility is closely related to, and partially motivated by, the program of reverse mathematics, which studies the proof-theoretic strength of mathematical theorems over some base theory. The standard base theory is a weak subsystem of second-order arithmetic known as ${RCA}_{0}$ , which roughly corresponds to computable mathematics. In that context, one considers the following question. For any two theorems P and Q, do we have ${RCA}_{0} + Q ⊢ P$ ?

For example, consider Ramsey’s theorem for k-colorings of n-tuples ( ${RT}_{k}^{n}$ ): for every coloring $c : {[N]}^{n} \to k$ , there is an infinite c-homogeneous set. Then ${RCA}_{0} + {RT}_{3}^{n} ⊢ {RT}_{2}^{n}$ (view the given 2-coloring as a 3-coloring). This proof only invokes ${RT}_{3}^{n}$ once, and it can be translated into a Weihrauch reduction from ${RT}_{2}^{n}$ to ${RT}_{3}^{n}$ .

Less trivially, we also have that ${RCA}_{0} + {RT}_{2}^{n} ⊢ {RT}_{3}^{n}$ . The usual proof invokes ${RT}_{2}^{n}$ twice, in series: given a 3-coloring of ${[N]}^{n}$ by red, green, and blue, first define a 2-coloring of ${[N]}^{n}$ by red and “grue”. Then use ${RT}_{2}^{n}$ to obtain an infinite homogeneous set for it. If we obtain a red homogeneous set, then we are done. If we obtain a “grue” homogeneous set, then we apply ${RT}_{2}^{n}$ to the original coloring restricted to this set, and we are done.

Is there a proof of ${RT}_{3}^{n}$ which only invokes ${RT}_{2}^{n}$ once?1

¹
In the reverse mathematics setting, Hirst and Mummert [10] gave such a proof in ${RCA}_{0}$ . Their proof was not “uniform”. In the setting of Weihrauch reducibility, Hirschfeldt and Jockusch [9], Brattka and Rakotoniaina [5], and Patey [11] independently showed that there is no reduction.

If not, is there a proof of

{RT}_{3}^{n}

which invokes

{RT}_{2}^{n}

twice, but in parallel?2

Note that invoking a theorem in parallel is a special case of invoking a theorem in series.

We want to study such questions from the point of view of Weihrauch reducibility. In order to do so, we must define some reducibility which would capture the notion of P being reducible to multiple instances of Q in series. There are three known ways to formalize this idea:

the compositional product (Definition 5);

reduction games (Definition 10);

the step product (Definition 18).

In this paper, we clarify the relationships between these three notions (for example, Theorems 23, 27, Corollary 29). We conclude that they are (mostly) equivalent, and hence one is (mostly) free to use whichever definition is convenient for one’s purposes. Along the way, we prove some basic properties of these notions, and give counterexamples where appropriate.

We are also interested in capturing the notion of P being reducible to different theorems $Q_{0}, \dots, Q_{n - 1}$ in series. One motivating example is Cholak, Jockusch, and Slaman’s [6] proof of ${RT}_{2}^{2}$ which proceeds by first using one theorem to obtain an infinite set on which the given coloring is stable, and then restricting to said set and obtaining, by another theorem, an infinite homogeneous set. To formalize this notion, we consider a generalized reduction game and show how it relates to the other formalizations (Theorem 34).

In the rest of the introduction, we give some notation and basic definitions. In this paper, P, Q, $\overline{Q}$ , etc., refer to multivalued functions from $N^{N}$ to $N^{N}$ . All multivalued functions and single-valued functions are allowed to be partial, unless otherwise stated. Their domains could be empty. Their domains and graphs need not be arithmetically definable, or even definable. If X is in the domain of P, then we say that X is a P-instance. If $(X, Y) \in P$ , then we say that Y is a P-solution to X. If Φ is a Turing functional and X is an oracle for Φ, we will sometimes write $Φ (X)$ instead of $Φ^{X}$ . Since Φ formally only takes numbers as input, this should not cause confusion.

We begin by defining Weihrauch reducibility on multivalued functions:

Definition 1.

For multivalued functions P and Q, we say that P is Weihrauch reducible (strongly Weihrauch reducible resp.) to Q, written $P ⩽_{W} Q$ ( $P ⩽_{s W} Q$ resp.), if there is a forward functional Γ and a backward functional Δ such that

for every P-instance X, $Γ^{X}$ is a Q-instance;

if X is a P-instance, then for every Q-solution Y to $Γ^{X}$ ,

$Δ (X \oplus Y)$ ( $Δ (Y)$ resp.) is a P-solution to X.

Intuitively, $P ⩽_{W} Q$ means that one can uniformly computably transform a realizer for Q into a realizer for P. In this paper, we focus on Weihrauch reducibility, but we use strong Weihrauch reducibility to state some of the results we need.

Note the uniformity in the above definitions: Γ and Δ have to satisfy the above conditions for all P-instances X. In fact, Weihrauch reducibility on multivalued functions was independently rediscovered by Dorais, Dzhafarov, Hirst, Mileti, and Shafer [7], who named it uniform reducibility. See Brattka, Gherardi, and Marcone [3] for historical remarks about Weihrauch reducibility, and an equivalent definition.

It is easy to see that $⩽_{W}$ is reflexive and transitive, so we can define the associated notion of Weihrauch equivalence and Weihrauch degrees: for multivalued functions P and Q, we say that P and Q are Weihrauch equivalent, written $P \equiv_{W} Q$ , if $P ⩽_{W} Q$ and $Q ⩽_{W} P$ . For a multivalued function P, its Weihrauch degreep is its $\equiv_{W}$ -class. Weihrauch reducibility lifts to Weihrauch degrees in the usual way; that is, we say that $p ⩽_{W} q$ if and only if there is some $P \in p$ and $Q \in q$ such that $P ⩽_{W} Q$ , if and only if for all $P \in p$ and $Q \in q$ , we have $P ⩽_{W} Q$ . We will abuse notation and use $P ⩽_{W} q$ to mean that there is some $Q \in q$ such that $P ⩽_{W} Q$ , or equivalently, for all $Q \in q$ , we have $P ⩽_{W} Q$ . We give $P \equiv_{W} q$ the analogous meaning.

We can define strong Weihrauch equivalence and strong Weihrauch degrees in the same way.

The Weihrauch degrees form a distributive lattice (Brattka, Gherardi [2], Pauly [12]). The join (coproduct) of multivalued functions $P_{0}$ and $P_{1}$ , denoted $P_{0} ⊔ P_{1}$ , has instances $⋃_{i = 0, 1} {(i, X) : X is a P_{i} -instance}$ . For $i = 0, 1$ , $(i, Y)$ is a $(P_{0} ⊔ P_{1})$ -solution to $(i, X)$ if Y is a $P_{i}$ -solution to X. The meet (sum) of $P_{0}$ and $P_{1}$ , denoted $P_{0} ⊓ P_{1}$ , has instances ${(X_{0}, X_{1}) : X_{i} is a P_{i} -instance}$ . For $i = 0, 1$ , $(i, Y)$ is a $(P_{0} ⊓ P_{1})$ -solution to $(X_{0}, X_{1})$ if Y is a $P_{i}$ -solution to $X_{i}$ . It is easy to see that the join and meet operations lift to the $\equiv_{W}$ -degrees.

Another useful notion is that of a uniformly computable multivalued function: a multivalued function P is uniformly computable if it has a computable realizer; that is, there is a functional Γ such that for every P-instance X, $Γ (X)$ is a P-solution to X. Note that the uniformly computable multivalued functions do not all lie in the same degree.3

In fact, it is easy to see that the Medvedev degrees embed into the set of Weihrauch degrees which contain a uniformly computable multivalued function.

2. Formalizing compositions

In this section, we present several ways to formalize what it means for P to be reducible to multiple instances of Q, and prove some basic properties about them.

2.1. Parallel product

We begin by considering what it means for P to be reducible to multiple instances of Q in parallel. This notion is captured by the parallel product:

Definition 2 (Brattka, Gherardi [2]).

Given multivalued functions P and Q, the parallel product $P \times Q$ is the Cartesian product of P and Q. That is, instances are pairs $(X, Y)$ , where X is a P-instance and Y is a Q-instance. $(Z, W)$ is a $(P \times Q)$ -solution to $(X, Y)$ if Z is a P-solution to X and W is a Q-solution to Y.

For example, we have that ${RT}_{j}^{n} \times {RT}_{k}^{n} ⩽_{W} {RT}_{j k}^{n}$ : given a j-coloring and a k-coloring, we can pair them to obtain a $j k$ -coloring. A homogeneous set for the $j k$ -coloring will be homogeneous for both the j-coloring and the k-coloring. For other examples, see [3] and [7].

Up to Weihrauch degree, the parallel product is well-defined, associative, and monotone in both components [2, Proposition 3.2].

While we will not study the parallel product in this paper, we will use it to state a later definition.

2.2. Compositional product

In this section, we define the compositional product of multivalued functions (Brattka, Gherardi, Marcone [3]; Brattka, Pauly [4]), which attempts to capture the notion of P being reducible to multiple instances of Q in series. We begin by defining the composition of multivalued functions, which forms a building block for the compositional product. Intuitively, $Q \circ P$ corresponds to invoking P and then Q, with no extra steps allowed in between; that is, the solution to the P-instance has to be a Q-instance.

Definition 3.
Given multivalued functions P and Q, their composition $Q \circ P$ is the following multivalued function. Instances are P-instances X such that every P-solution Y to X is itself a Q-instance. Z is a $(Q \circ P)$ -solution to X if there is some P-solution Y to X such that Z is a Q-solution to Y.

Note that the composition of P and Q as multivalued functions is more restrictive than the composition of P and Q as relations. This restriction implies that, for example, the composition of realizers for P and Q is a realizer of the composition $Q \circ P$ .

It is easy to see that ∘ is associative:
Proposition 4.
∘ is associative up to equality of multivalued functions; that is, for multivalued functions P, Q, R, we have $(R \circ Q) \circ P = R \circ (Q \circ P)$ .

However, ∘ is not monotone (in either component) with respect to Weihrauch reducibility. To illustrate what can go wrong, here are some examples.

Take any Q which is not uniformly computable and has a computable instance $X_{0}$ with a computable solution. (For example, take Q to be ${RT}_{2}^{1}$ .) Take $P_{0}$ to be the identity function, and take $P_{1}$ to be the identity function restricted to ${X_{0}}$ . It is easy to see that $P_{0} ⩽_{W} P_{1}$ and $Q \circ P_{0} ≰_{W} Q \circ P_{1}$ .

Take any P which is not uniformly computable. For $i = 0, 1$ , define $P_{i}$ as follows: $P_{i}$ -instances are P-instances, and $(i, Y)$ is a $P_{i}$ -solution to X if and only if Y is a P-solution to X. Define Q as follows: instances are pairs $(i, Y)$ , for any set Y and $i = 0, 1$ . For each $(0, Y)$ , Y is the only Q-solution, and for each $(1, Y)$ , 0 is the only Q-solution. It is easy to see that $P_{0} ⩽_{W} P_{1}$ and $Q \circ P_{0} ≰_{W} Q \circ P_{1}$ .

Take any R which is not uniformly computable. Define P as follows: instances are pairs $(i, X)$ for any set X and $i = 0, 1$ . For each $(0, X)$ , the P-solutions are pairs $(0, Y)$ , where Y is an R-solution to X, and for each $(1, X)$ , 0 is the only P-solution. Define $Q_{0}$ to be the identity function restricted to instances $(0, Y)$ , for any set Y. Define $Q_{1}$ to be the identity function with only one instance 0. It is easy to see that $Q_{0} ⩽_{W} Q_{1}$ and $Q_{0} \circ P ≰_{W} Q_{1} \circ P$ .

Define P as follows: instances are pairs $(i, X)$ for any set X and $i = 0, 1$ . Each $(i, X)$ has a unique P-solution $(0, X)$ . For $i = 0, 1$ , define $Q_{i}$ to be the identity function restricted to pairs $(i, X)$ . We have that $Q_{0} ⩽_{W} Q_{1}$ . But $Q_{0} \circ P$ has nonempty domain while $Q_{1} \circ P$ has empty domain, so $Q_{0} \circ P ≰_{W} Q_{1} \circ P$ .

Having defined ∘, we are now ready to define the compositional product $Q ⋆ P$ , which attempts to capture the power of one invocation of P, followed by one invocation of Q in series.
Definition 5 (Brattka, Gherardi, Marcone [3]; Brattka, Pauly [4]).

The compositional product4

⁴
Brattka and Pauly [4] give a different definition of $q ⋆ p$ and show that it is equal to the supremum of all $Q \circ P$ , where $Q ⩽_{W} q$ and $P ⩽_{W} p$ are multivalued functions on arbitrary represented spaces, not just $N^{N}$ . Nevertheless, this definition is equivalent to theirs: suppose f is a multivalued function from $(X, δ_{X})$ to $(Y, δ_{Y})$ and g is a multivalued function from $(Y, δ_{Y})$ to $(Z, δ_{Z})$ . Then $f \equiv_{W} δ_{Y}^{- 1} \circ f \circ δ_{X}$ , $g \equiv_{W} δ_{Z}^{- 1} \circ g \circ δ_{Y}$ , and $g \circ f \equiv_{W} (δ_{Z}^{- 1} \circ g \circ δ_{Y}) \circ (δ_{Y}^{- 1} \circ f \circ δ_{X})$ .

of Weihrauch degrees p and q, written

q ⋆ p

, is defined to be the Weihrauch degree

sup {Q \circ P : Q ⩽_{W} q, P ⩽_{W} p}

That the supremum in the definition exists is in fact a theorem:

Theorem 6 (Brattka, Pauly [4, Corollaries 18, 20]).

For every p and q , there are multivalued functions P of degree p and Q of degree q such that $Q \circ P$ has degree $q ⋆ p$ .

We abuse notation and use $Q ⋆ P$ to refer to the Weihrauch degree $q ⋆ p$ , where P has degree p and Q has degree q. Since ⋆ is monotone in both coordinates, this is well-defined.

In order to state more facts about the compositional product, we use the notion of a cylinder due to Brattka and Gherardi [2]. We say that a multivalued function P is a cylinder if $P \equiv_{s W} id \times P$ . It is easy to see that if $Q ⩽_{W} P$ , then $Q ⩽_{s W} id \times P$ . Therefore, if P is a cylinder, then $Q ⩽_{W} P$ if and only if $Q ⩽_{s W} P$ .

The compositional product has a cylindrical decomposition:

Lemma 7 (Brattka, Pauly [4, Lemma 21]).

For all P and Q which are cylinders, there exists a computable function K such that $Q ⋆ P \equiv_{W} Q \circ K \circ P$ . Furthermore, $Q \circ K \circ P$ is a cylinder.

We also have that

Proposition 8 (Brattka, Pauly [4, Proposition 32]).

⋆ is associative. ⋆ is monotone in both components with respect to Weihrauch reducibility.

In order to prove our main results, we will use the following version of Theorem 6 for multiple multivalued functions.

Lemma 9.
For every $Q_{0}, \dots, Q_{n - 1}$ , there are multivalued functions $R_{0}, \dots, R_{n - 1}$ such that for each $i < n$ , $R_{i} ⩽_{W} Q_{i}$ , and $Q_{n - 1} ⋆ \dots ⋆ Q_{0} \equiv_{W} R_{n - 1} \circ \dots \circ R_{0}$ .
Proof.
First, by replacing each $Q_{i}$ with $id \times Q_{i}$ , we may assume that each $Q_{i}$ is a cylinder. Next, by induction using Lemma 7, we obtain computable functions $K_{0}, \dots, K_{n - 2}$ such that $\begin{matrix} Q_{n - 1} ⋆ \dots ⋆ Q_{0} \equiv_{W} Q_{n - 1} \circ K_{n - 2} \circ Q_{n - 2} \circ \dots \circ K_{0} \circ Q_{0} . \end{matrix}$ Then define $R_{n - 1} = Q_{n - 1}$ , and for $i < n - 1$ , define $R_{i} = K_{i} \circ Q_{i}$ . For each i, it is easy to see that $R_{i} ⩽_{W} Q_{i}$ . □

2.3. Reduction games

In this section, we present another formalization of the notion of P being reducible to multiple instances of Q in series. The process of solving an instance of P using multiple instances of Q in series can be thought of as a game. Roughly speaking, Player I starts by posing a P-instance for Player II to solve. At each turn, Player II has oracle access to all of Player I’s previous plays, and it can either compute a Q-instance for Player I to solve, or it can win by computing a solution to the P-instance posed by Player I.

Definition 10 (Hirschfeldt, Jockusch [9, Definition 4.1]).

Define the game reducing P to Q as follows. In round $n = 1$ , Player I starts by playing a P-instance $X_{0}$ . Player II responds with either of the following:

an $X_{0}$ -computable Q-instance $Y_{1}$ ;

an $X_{0}$ -computable P-solution to $X_{0}$ ;

and an indication of which case it is (for the second case, Player II declares victory.)

In round $n > 1$ , Player I plays a solution $X_{n - 1}$ to the Q-instance $Y_{n - 1}$ . Player II responds with either of the following:

a $(⨁_{i < n} X_{i})$ -computable Q-instance $Y_{n}$ ;

a $(⨁_{i < n} X_{i})$ -computable P-solution to $X_{0}$ ;

and an indication of which case it is (for the second case, Player II declares victory.)

If Player II ever declares victory or Player I cannot move (which can only happen in the first round), then Player II wins and the game ends. Otherwise Player I wins, which happens either if the game goes on forever, or Player II cannot move (which can only happen in the first round).

In the game reducing P to Q, even though II can only play sets which are computable in the join of all of I’s previous plays, II is allowed to employ non-uniform strategies to decide which set to play. Since we are interested in solving P uniformly from multiple instances of Q, we will only consider computable strategies for II, defined as follows.

We recall some notation from [9]. First, we assume that we have defined the join operation for finitely many sets so that we can compute n from $⨁_{i < n} X_{i}$ . In general, when we write $X_{0} \oplus X_{1}$ we mean ${2 n : n \in X_{0}} \cup {2 n + 1 : n \in X_{1}}$ as usual. However, we will sometimes write $X_{0} \oplus X_{1}$ for $⨁_{i < 2} X_{i}$ , when it is clear that this is what we mean. Similarly, we will write simply $X_{0}$ instead of $⨁_{i < 1} X_{i}$ .

Second, if Z is a set and Φ is a Turing functional, then we define ${\hat{Φ}}^{Z}$ to be ${n : 2 n + 1 \in Φ^{Z}}$ .

Definition 11 (Hirschfeldt, Jockusch [9, Definition 4.3]).

A Turing functional Φ is a computable strategy for II for the game reducing P to Q if for all $n ⩾ 1$ , if $Z = ⨁_{i < n} X_{i}$ is the join of Player I’s first n moves in some run of said game, then

if $Φ^{Z} (0) ↓ = 0$ , then ${\hat{Φ}}^{Z}$ is a Z-computable Q-instance;

otherwise, $Φ^{Z} (0) ↓ = 1$ and ${\hat{Φ}}^{Z}$ is a Z-computable P-solution to $X_{0}$ .

We will frequently define

Φ^{Z}

by first defining

{\hat{Φ}}^{Z}

and then setting

Φ^{Z} = \emptyset \oplus {\hat{Φ}}^{Z}

Φ^{Z} = {0} \oplus {\hat{Φ}}^{Z}

We say that $P ⩽_{g W} Q$ if there is a computable winning strategy for II for the game reducing P to Q. We say that $P ⩽_{g W}^{n} Q$ if there is a computable strategy for II for the game reducing P to Q such that II always wins in round $n + 1$ or before.

In this paper, we will not discuss $⩽_{g W}$ , only its bounded versions $⩽_{g W}^{n}$ . In order to understand $⩽_{g W}^{n}$ better, we start by considering $⩽_{g W}^{1}$ . If $P ⩽_{g W}^{1} Q$ , that means that there is a strategy Φ for II which wins the game reducing P to Q in round 1 or 2. Those P-instances for which Φ wins in round 1 have uniformly computable solutions, while all other P-instances can be solved by solving some corresponding Q-instance (given by Φ). More precisely, Φ provides a Weihrauch reduction from the restriction of P to those latter instances, to Q. This indicates that $⩽_{g W}^{1}$ and $⩽_{W}$ are related. We explore their relationship in the following propositions.

First, the above discussion can be formally stated as follows:

Proposition 12.
The following are equivalent:
$P ⩽_{g W}^{1} Q$ ;

the domain D of P can be computably partitioned into $D_{0}$ and $D_{1}$ , such that $P ↾ D_{0}$ is uniformly computable and $P ↾ D_{1} ⩽_{W} Q$ ;

there is some uniformly computable R such that $P ⩽_{W} Q ⊔ R$ .

$P ⩽_{W} Q ⊔ id$ .

Second, if every P-instance uniformly computes a Q-instance, then we can upgrade a $⩽_{g W}^{1}$ -reduction from P to Q to a $⩽_{W}$ -reduction:
Proposition 13.
$P ⩽_{W} Q$ if and only if every P-instance uniformly computes a Q-instance (that is, $dom (Q)$ is Medvedev reducible to $dom (P)$ ) and $P ⩽_{g W}^{1} Q$ .
Proof.
(⇒). Fix Γ and Δ witnessing that $P ⩽_{W} Q$ . First, Γ witnesses that every P-instance uniformly computes a Q-instance. Next, we give a strategy Φ witnessing that $P ⩽_{g W}^{1} Q$ : $\begin{array}{l} Φ^{X_{0}} = \emptyset \oplus Γ^{X_{0}} \\ Φ^{X_{0} \oplus X_{1}} = {0} \oplus Δ^{X_{0} \oplus X_{1}} . \end{array}$

Note that in the two cases of the definition above, the oracles of Φ are meant to be $⨁_{i ⩽ 0} X_{i}$ and $⨁_{i ⩽ 1} X_{i}$ respectively. This is because Φ’s action depends on which round of the game it is playing, hence it must be able to compute that information from the oracle.

(⇐). Fix a strategy Φ witnessing that $P ⩽_{g W}^{1} Q$ , and fix a functional Ξ which takes in any P-instance and computes a Q-instance from it. We define functionals Γ and Δ witnessing that $P ⩽_{W} Q$ : $\begin{matrix} Γ^{X_{0}} = \{\begin{matrix} {\hat{Φ}}^{X_{0}} & if Φ^{X_{0}} (0) ↓ = 0 \\ Ξ^{X_{0}} & otherwise \end{matrix} \end{matrix}$ and $\begin{matrix} Δ^{X_{0} \oplus X_{1}} = \{\begin{matrix} {\hat{Φ}}^{X_{0} \oplus X_{1}} & if Φ^{X_{0}} (0) ↓ = 0 \\ {\hat{Φ}}^{X_{0}} & otherwise . \end{matrix} \end{matrix}$ □

Most problems that arise directly from mathematical theorems have computable instances. Such problems are called pointed (Brattka, de Brecht, Pauly [1]).
Corollary 14.
If Q is pointed, then $P ⩽_{W} Q$ if and only if $P ⩽_{g W}^{1} Q$ .

It is clear that Q is pointed if and only if $id ⩽_{W} Q$ . Hence if Q is not pointed, then there is a trivial counterexample to the above Corollary: $id ≰_{W} Q$ yet $id ⩽_{g W}^{1} Q$ . These results clarify a statement in $§ 4.4$ of [9], where they claim that $P ⩽_{g W}^{1} Q$ if and only if $P ⩽_{W} Q$ .

Moving on to $n ⩾ 1$ , observe that if $P ⩽_{g W}^{n} Q$ , then there is a computable strategy for II for the game reducing P to Q which wins in round 1 or round $n + 1$ . This is because everytime II declares victory in round k for $1 < k < n + 1$ , II could instead repeatedly play the Q-instance which it played in round 1, and wait until round $n + 1$ to declare victory. Using this observation, we obtain
Proposition 15.
$P ⩽_{g W}^{n} Q$ if and only if the domain D of P can be computably partitioned into $D_{0}$ and $D_{1}$ , such that
$P ↾ D_{0}$ is uniformly computable;

if $D_{1}$ is nonempty, then there is a strategy for II witnessing that $P ↾ D_{1} ⩽_{g W}^{n} Q$ which always wins in round $n + 1$ .

Proof.
(⇒). Fix a strategy Φ witnessing that $P ⩽_{g W}^{n} Q$ . For $i = 0, 1$ , define $D_{i} = {X \in D : Φ^{X} (0) ↓ = 1 - i}$ . $D_{0}$ and $D_{1}$ form a computable partition of D. $P ↾ D_{0}$ is uniformly computable, as witnessed by $\hat{Φ}$ .

If $D_{1}$ is nonempty, then, as discussed above, we may modify Φ to give a strategy Ψ which always wins the game reducing $P ↾ D_{1}$ to Q in round $n + 1$ .

(⇐). Fix a computable partition of D into $D_{0}$ and (nonempty) $D_{1}$ , a functional Ξ which solves $P ↾ D_{0}$ , and a strategy Φ which always wins the game reducing $P ↾ D_{1}$ to Q in round $n + 1$ .

We give a strategy for II which witnesses that $P ⩽_{g W}^{n} Q$ . I starts by playing a P-instance, say $X_{0}$ . II starts by computing whether $X_{0}$ lies in $D_{0}$ or $D_{1}$ . If $X_{0}$ lies in $D_{0}$ , then II applies Ξ to solve $X_{0}$ and declares victory. If $X_{0}$ lies in $D_{1}$ , then II follows the strategy Φ to solve $X_{0}$ and declare victory in round $n + 1$ . Either way, II declares victory by round $n + 1$ . □

Another useful property about $⩽_{g W}^{n}$ is that it is well-defined on Weihrauch degrees, which we show below. Since we only defined the compositional product up to Weihrauch degree, this allows us to make sense of statements such as $P ⩽_{g W}^{n} Q ⋆ Q$ (such as in Theorem 30).

The desired statement follows from the following proposition. Proposition 16.
If $P ⩽_{g W}^{m} Q$ with a strategy that always wins in round $m + 1$ and $Q ⩽_{g W}^{n} R$ with a strategy that always wins in round $n + 1$ , then $P ⩽_{g W}^{m n} R$ with a strategy that always wins in round $m n + 1$ . If $P ⩽_{g W}^{m} Q$ and $Q ⩽_{g W}^{n} R$ , then $P ⩽_{g W}^{m n} R$ .
Proof.
To prove the first statement, fix a strategy Φ for $P ⩽_{g W}^{m} Q$ which always wins in round $m + 1$ , and a strategy Ψ for $Q ⩽_{g W}^{n} R$ which always wins in round $n + 1$ . We describe a strategy for $P ⩽_{g W}^{m n} R$ which always wins in round $m n + 1$ . The idea is to play the game G reducing P to R by playing the game $G^{'}$ reducing P to Q, interleaved with m many consecutive games $G_{0}, \dots, G_{m - 1}$ , each reducing Q to R.

Say that in G, I starts by playing a P-instance $X_{0}$ . Then $\hat{Φ} (X_{0})$ is a Q-instance, so we simulate a parallel game $G^{'}$ reducing P to Q where I starts by playing $X_{0}$ and II responds with $\hat{Φ} (X_{0})$ . In order to come up with a valid response for I in $G^{'}$ , we simulate yet another parallel game $G_{0}$ reducing Q to R where I starts by playing $\hat{Φ} (X_{0})$ . Then $\hat{Ψ} (\hat{Φ} (X_{0}))$ is an R-instance, so II plays $\hat{Ψ} (\hat{Φ} (X_{0}))$ in G (and in $G_{0}$ ).

Next, in G, I responds with some R-solution $X_{1}$ to $\hat{Ψ} (\hat{Φ} (X_{0}))$ . We copy that response to $G_{0}$ . Then $\hat{Ψ} (\hat{Φ} (X_{0}) \oplus X_{1})$ is an R-instance, so II plays it in G (and in $G_{0}$ ).

We continue playing G as above (and simulating $G_{0}$ ) until II wins $G_{0}$ and provides a Q-solution $Z_{0}$ to $\hat{Φ} (X_{0})$ . At that point we return to simulating $G^{'}$ : I can now respond with $Z_{0}$ .

In $G^{'}$ , II responds with the Q-instance $\hat{Φ} (X_{0} \oplus Z_{0})$ . In order to simulate I’s response in $G^{'}$ , we simulate another parallel game $G_{1}$ reducing Q to R where I starts by playing $\hat{Φ} (X_{0} \oplus Z_{0})$ . Proceed as we did for $G_{0}$ .

Since Φ always wins in round $m + 1$ and Ψ always wins in round $n + 1$ , the above strategy always wins in round $m n + 1$ .

The proof of the second statement is similar. □
Corollary 17.
$⩽_{g W}^{n}$ is well-defined up to Weihrauch degree, i.e., if $P_{1} ⩽_{W} P_{0}$ , $P_{0} ⩽_{g W}^{n} Q_{0}$ , and $Q_{0} ⩽_{W} Q_{1}$ , then $P_{1} ⩽_{g W}^{n} Q_{1}$ .
Proof.
Use Propositions 16 and 13. □

2.4. Step product

The step product generalizes the composition of multivalued functions. Intuitively, $Q ∙_{Θ} P$ corresponds to invoking P, transforming the result by Θ (allowing Θ access to the original P-instance), and then invoking Q.

Definition 18 (Dorais, Dzhafarov, Hirst, Mileti, Shafer [7, §5.2]).

Given multivalued functions P and Q and a Turing functional Θ, the multivalued function $Q ∙_{Θ} P$ is defined as follows. A is an instance of $Q ∙_{Θ} P$ if

A is a P-instance;

for every P-solution B to A, we have that $Θ^{A \oplus B}$ is a Q-instance.

In that case, a

(Q ∙_{Θ} P)

-solution to A is a pair

(B, C)

such that

B is a P-solution to A;

C is a Q-solution to $Θ^{A \oplus B}$ .

Note that $Q ∙_{Θ} P$ may very well be the empty multivalued function, but that will not affect any of our results.

Note also that if we define Θ to be the projection $A \oplus B \mapsto B$ , then $Q ∙_{Θ} P$ is exactly $Q \circ P$ .

Many compositions that we encounter in proofs can be thought of as some step product. However, the step product does not satisfy several of the properties one would desire of a product, such as monotonicity. First we give a positive result: in some sense, the step product is monotone in the first coordinate with respect to Weihrauch reducibility.

Proposition 19.
Suppose $Q_{0} ⩽_{W} Q_{1}$ , Θ is a functional, and P is a multivalued function. Then there is a functional Λ such that $Q_{0} ∙_{Θ} P ⩽_{W} Q_{1} ∙_{Λ} P$ .
Proof.
We define a functional Λ, and forward and backward functionals witnessing that $Q_{0} ∙_{Θ} P ⩽_{W} Q_{1} ∙_{Λ} P$ . We will take the forward functional to be the identity.

Fix Γ and Δ witnessing that $Q_{0} ⩽_{W} Q_{1}$ . We define Λ such that every $(Q_{0} ∙_{Θ} P)$ -instance X is also a $(Q_{1} ∙_{Λ} P)$ -instance: for every P-solution Y to X, $Θ (X \oplus Y)$ is a $Q_{0}$ -instance, so $Γ (Θ (X \oplus Y))$ is a $Q_{1}$ -instance. Hence we define $Λ = Γ \circ Θ$ .

Next, for every $(Q_{1} ∙_{Λ} P)$ -solution $(Y, Z)$ to X, we have that Y is a P-solution to X and Z is a $Q_{1}$ -solution to $Λ (X \oplus Y) = Γ (Θ (X \oplus Y))$ . Hence $Δ (Θ (X \oplus Y) \oplus Z)$ is a $Q_{0}$ -solution to $Θ (X \oplus Y)$ , so $(Y, Δ (Θ (X \oplus Y) \oplus Z))$ is a $(Q_{0} ∙_{Θ} P)$ -solution to X. Therefore, we define the backward functional by $\begin{matrix} X \oplus (Y, Z) \mapsto (Y, Δ (Θ (X \oplus Y) \oplus Z)) . \end{matrix}$ This completes the proof that $Q_{0} ∙_{Θ} P ⩽_{W} Q_{1} ∙_{Λ} P$ . □

However, the step product is not monotone (in the above sense) in the second coordinate. (Take $Q = {RT}_{2}^{1}$ , $P_{0} = id$ , $P_{1} = id ↾ {N}$ . Then $P_{0} ⩽_{W} P_{1}$ but for all Λ, $Q \circ P_{0} ≰_{W} Q ∙_{Λ} P_{1}$ . See Example 26 for a more sophisticated example.) We have the following partial positive result:
Proposition 20.
Suppose $P_{0} ⩽_{W} P_{1}$ , $P_{1}$ is a cylinder, Θ is a functional, and Q is a multivalued function. Then there is a functional Λ such that $Q ∙_{Θ} P_{0} ⩽_{s W} Q ∙_{Λ} P_{1}$ .
Proof.
Fix Γ and Δ witnessing that $P_{0} ⩽_{W} P_{1}$ . Fix Φ and Ψ witnessing that $id \times P_{1} ⩽_{s W} P_{1}$ . We define a functional Λ, and forward and backward functionals witnessing that $Q ∙_{Θ} P_{0} ⩽_{W} Q ∙_{Λ} P_{1}$ . We will take the forward functional to be $X \mapsto Φ (X, Γ (X))$ .

We define Λ such that for every $(Q ∙_{Θ} P_{0})$ -instance X, $Φ (X, Γ (X))$ is a $(Q ∙_{Λ} P_{1})$ -instance: first note that $Φ (X, Γ (X))$ is a $P_{1}$ -instance. Next, for every $P_{1}$ -solution Z to $Φ (X, Γ (X))$ , $Ψ (Z)$ is an $(id \times P_{1})$ -solution to $(X, Γ (X))$ ; that is, ${(Ψ (Z))}_{0} = X$ and ${(Ψ (Z))}_{1}$ is a $P_{1}$ -solution to $Γ (X)$ . It follows that $Δ (Ψ (Z))$ is a $P_{0}$ -solution to X. Therefore, $Θ (X \oplus Δ (Ψ (Z)))$ is a Q-instance. So we define $\begin{matrix} Λ (A \oplus Z) = Θ ({(Ψ (Z))}_{0} \oplus Δ (Ψ (Z))) . \end{matrix}$

Now, for every $(Q ∙_{Λ} P_{1})$ -solution $(Z, W)$ to $Φ (X, Γ (X))$ , we have that Z is a $P_{1}$ -solution to $Φ (X, Γ (X))$ and W is a Q-solution to $Λ (Φ (X, Γ (X)) \oplus Z) = Θ (X \oplus Δ (Ψ (Z)))$ . Then $(Δ (Ψ (Z)), W)$ is a $(Q ∙_{Θ} P_{0})$ -solution to X. Therefore, we define the backward functional by $\begin{matrix} (Z, W) \mapsto (Δ (Ψ (Z)), W) . \end{matrix}$ This completes the proof that $Q ∙_{Θ} P_{0} ⩽_{s W} Q ∙_{Λ} P_{1}$ . □

Proposition 20 suggests that the class of $Q ∙_{Θ} P$ where P is a cylinder may be well-behaved (see also Lemma 7). Note that any multivalued function P is Weihrauch equivalent to a cylinder, for example $id \times P$ .
3. Composing a multivalued function with itself

In this section, we study the relationships between the various products for the simplest nontrivial case: two invocations of P. We will see in Theorem 23 that the compositional product and the reduction game are equivalent in the case where P is pointed, and the compositional product and the step product can be made equivalent if we modify the second factor in the step product.

We begin by showing that ⋆ is always at least as strong as $∙_{Θ}$ .

Proposition 21.
For any functional Θ, we have that $Q ∙_{Θ} P ⩽_{W} Q ⋆ P$ .
Proof.
Define the multivalued function $P_{0}$ as follows. Instances of $P_{0}$ are instances of $Q ∙_{Θ} P$ . $(Y, Z)$ is a solution to the $P_{0}$ -instance Y if Z is a P-solution to Y.

We have $P_{0} ⩽_{W} P$ : take the forward functional to be the identity, and define the backward functional by mapping $Y \oplus Z$ to $(Y, Z)$ .

Next, define $Q_{0}$ : its instances are pairs $(Y, Z)$ such that Y is a $Q ∙_{Θ} P$ -instance and Z is a P-solution to Y. $(Z, W)$ is a solution to the $Q_{0}$ -instance $(Y, Z)$ if W is a solution to the Q-instance $Θ^{Y \oplus Z}$ .

We have $Q_{0} ⩽_{W} Q$ : define the forward functional by mapping $(Y, Z)$ to $Θ^{Y \oplus Z}$ , and define the backward functional by mapping $(Y, Z) \oplus W$ to $(Z, W)$ .

Finally, we see that $Q_{0} \circ P_{0}$ is equal to $Q ∙_{Θ} P$ , so we are done. □

Next, in order to state our first main result, we need the following definition.
Definition 22.
Given a multivalued function R, define the multivalued function $\overline{R}$ as follows. Instances of $\overline{R}$ are pairs $(X, Y)$ , where X is any set and Y is an R-instance. Z is an $\overline{R}$ -solution to $(X, Y)$ if Z is an R-solution to Y.

Note that $\overline{R} \equiv_{W} R$ . Note also that $\overline{R}$ is not a cylinder. Now we prove our first main theorem relating ⋆, reduction games, and $∙_{Θ}$ .
Theorem 23.
The following are equivalent:
$P ⩽_{W} Q ⋆ Q$ ;

there is a strategy for II witnessing that $P ⩽_{g W}^{2} Q$ , which always wins in the third round, or P has empty domain;

every P-instance uniformly computes a Q-instance, and

$P ⩽_{g W}^{2} Q$ ;

there is a functional Θ such that $P ⩽_{W} Q ∙_{Θ} \overline{Q}$ .

Proof.
(1) ⇒ (2). By Theorem 6, since $P ⩽_{W} Q ⋆ Q$ , there are multivalued functions $Q_{0}, Q_{1} ⩽_{W} Q$ such that $P ⩽_{W} Q_{1} \circ Q_{0}$ . We define a strategy Φ for II witnessing that $Q_{1} \circ Q_{0} ⩽_{g W}^{2} Q$ , which always wins in the third round. The desired result then follows from Corollary 17. Fix $Γ_{0}$ and $Δ_{0}$ witnessing that $Q_{0} ⩽_{W} Q$ . Fix $Γ_{1}$ and $Δ_{1}$ witnessing that $Q_{1} ⩽_{W} Q$ .

I begins the game by playing a $(Q_{1} \circ Q_{0})$ -instance, say X. (If the domain of $Q_{1} \circ Q_{0}$ is empty, then the domain of P is empty and we are done.) In particular, note that X is a $Q_{0}$ -instance. II responds by playing the Q-instance $Γ_{0} (X)$ .

I then plays a Q-solution to $Γ_{0} (X)$ , say Z. Then $Δ_{0} (X \oplus Z)$ is a $Q_{0}$ -solution to X. Since X is a $(Q_{1} \circ Q_{0})$ -instance, $Δ_{0} (X \oplus Z)$ must be a $Q_{1}$ -instance. Therefore, II responds with the Q-instance $Γ_{1} (Δ_{0} (X \oplus Z))$ .

Finally, I plays a Q-solution W to $Γ_{1} (Δ_{0} (X \oplus Z))$ . Then

$Δ_{1} (Δ_{0} (X \oplus Z) \oplus W)$ is a $Q_{1}$ -solution to $Δ_{0} (X \oplus Z)$ , which implies that it is a $(Q_{1} \circ Q_{0})$ -solution to X. II declares victory and responds with $Δ_{1} (Δ_{0} (X \oplus Z) \oplus W)$ .

(2) ⇒ (3). If P has empty domain, (3) vacuously holds. Otherwise, fix a strategy Φ for II witnessing that $P ⩽_{g W}^{2} Q$ which always wins in the third round. For every P-instance X, ${\hat{Φ}}^{X}$ is always a Q-instance (because Φ does not win in the first round).

(3) ⇒ (4). Fix some Φ witnessing that $P ⩽_{g W}^{2} Q$ , and fix some Ξ which computes Q-instances from P-instances. First define a forward functional for $P ⩽_{W} Q ∙_{Θ} \overline{Q}$ : $\begin{matrix} Γ^{X} = \{\begin{matrix} (X, {\hat{Φ}}^{X}) & if Φ^{X} (0) ↓ = 0 \\ (X, Ξ^{X}) & otherwise . \end{matrix} \end{matrix}$ Then define $\begin{matrix} Θ^{(X, Y) \oplus Z} = \{\begin{matrix} {\hat{Φ}}^{X \oplus Z} & if Φ^{X} (0) ↓ = 0 and Φ^{X \oplus Z} (0) ↓ = 0 \\ Ξ^{X} & otherwise . \end{matrix} \end{matrix}$ Observe that for every P-instance X, $Γ^{X}$ is a $\overline{Q}$ -instance, and for every $\overline{Q}$ -solution Z to $Γ^{X}$ , $Θ^{Γ^{X} \oplus Z}$ is a Q-instance. Therefore $Γ^{X}$ is a $Q ∙_{Θ} \overline{Q}$ -instance.

Finally, define a backward functional $\begin{matrix} Δ^{X \oplus (Z, W)} = \{\begin{matrix} {\hat{Φ}}^{X \oplus Z \oplus W} & if Φ^{X} (0) ↓ = 0 and Φ^{X \oplus Z} (0) ↓ = 0 \\ {\hat{Φ}}^{X \oplus Z} & if Φ^{X} (0) ↓ = 0 and Φ^{X \oplus Z} (0) ↓ = 1 \\ {\hat{Φ}}^{X} & if Φ^{X} (0) ↓ = 1 . \end{matrix} \end{matrix}$

(4) ⇒ (1). We have that $\begin{array}{l} P & ⩽_{W} Q ∙_{Θ} \overline{Q} \\ ⩽_{W} Q ⋆ \overline{Q} & Proposition 21 \\ ⩽_{W} Q ⋆ Q & \overline{Q} ⩽_{W} Q and definition of ⋆ . \end{array}$ □

We note that a statement similar to (2) ⇒ (4) was proven in Remark 4.23 in [9]. (They use $\hat{Q} : = id \times Q$ instead of $\overline{Q}$ , but the same result holds: use Proposition 20 and the fact that $\hat{Q}$ is a cylinder.) However, they (implicitly) assume that if $P ⩽_{g W}^{2} Q$ , then (2) holds. This is true if Q is pointed, but false otherwise (see Proposition 28).

Let us now study corollaries of Theorem 23. First, we obtain a simple realization of the compositional product (cf. Theorem 6):
Corollary 24.
For all Q, there is a functional Θ such that $Q ⋆ Q \equiv_{W} Q ∙_{Θ} \overline{Q}$ .
Proof.
(1) ⇔ (4) in Theorem 23. □

If Q is a cylinder, we note that a nicer result follows from the cylindrical decomposition of Brattka and Pauly (Lemma 7):
Corollary 25.
If Q is a cylinder, then there is a functional Θ such that $Q ⋆ Q \equiv_{W} Q ∙_{Θ} Q$ .
Proof.
By the cylindrical decomposition lemma, there is some uniformly computable K such that $Q ⋆ Q \equiv_{W} Q \circ K \circ Q$ . Taking $Θ : A \oplus B \mapsto K (B)$ , we get $Q ⋆ Q \equiv_{W} Q ∙_{Θ} Q$ . □

The above corollary cannot hold for all Q in general:
Example 26.
We construct Q and Θ such that for all Λ, $Q ∙_{Θ} \overline{Q} ≰_{W} Q ∙_{Λ} Q$ (and hence $Q ⋆ Q ≰_{W} Q ∙_{Λ} Q$ for all Λ). We take Θ to be the identity. Fix four sets A, B, C and D such that no three of these sets compute the other. (Such sets can be obtained from a Cohen generic.) Define Q as follows: the instance B has a unique solution C, and the instance $((A, B), C)$ has a unique solution D. Observe that $(A, B)$ is a $(Q ∙_{id} \overline{Q})$ -instance with unique solution $(C, D)$ .

Suppose towards a contradiction that Λ is such that $Q ∙_{id} \overline{Q} ⩽_{W} Q ∙_{Λ} Q$ . Fix Γ and Δ witnessing this. We show that they fail to solve the $(Q ∙_{id} \overline{Q})$ -instance $(A, B)$ . First, $Γ (A \oplus B)$ must be a Q-instance. The only Q-instance computable in $A \oplus B$ is B, which has a unique Q-solution C. Next, $Λ (B \oplus C)$ must be a Q-instance. The only Q-instance computable in $B \oplus C$ is B, which has a unique Q-solution C. Hence the unique $(Q ∙_{Λ} Q)$ -solution to B must be $(C, C)$ . Finally, $Δ ((A \oplus B) \oplus (C \oplus C))$ must be the unique $(Q ∙_{id} \overline{Q})$ -solution to $(A, B)$ , which is $(C, D)$ . But $A \oplus B \oplus C$ does not compute D, contradiction.

Another application of Theorem 23 is to compare ∙, ⋆, and $⩽_{g W}^{2}$ on the same footing. The following suprema are taken with respect to Weihrauch reducibility.
Theorem 27.
For all Q, ${sup}_{Λ} Q ∙_{Λ} \overline{Q}$ exists and for all Θ, $\begin{matrix} Q ∙_{Θ} Q ⩽_{W} sup_{Λ} Q ∙_{Λ} \overline{Q} \equiv_{W} Q ⋆ Q ⩽_{g W}^{2} Q . \end{matrix}$
Proof.
First, by (1) ⇒ (4) in Theorem 23, there is Λ such that $Q ⋆ Q ⩽_{W} Q ∙_{Λ} \overline{Q}$ . By (4) ⇒ (1) in Theorem 23, $Q ∙_{Λ} \overline{Q} ⩽ Q ⋆ Q$ for all Λ. Hence ${sup}_{Λ} Q ∙_{Λ} \overline{Q}$ exists and is equal to $Q ⋆ Q$ .

Next, by Proposition 21, $Q ∙_{Θ} Q ⩽_{W} Q ⋆ Q$ .

Finally, by (1) ⇒ (2) in Theorem 23, $Q ⋆ Q ⩽_{g W}^{2} Q$ . □

We do not know whether ${sup}_{Θ} Q ∙_{Θ} Q$ or $sup {P : P ⩽_{g W}^{2} Q}$ exist in general. If Q is pointed, we have some partial results.
Proposition 28.
If Q is pointed, then $sup {P : P ⩽_{g W}^{2} Q}$ exists and is equal to $Q ⋆ Q$ . If Q is not pointed, then there is some $P ⩽_{g W}^{2} Q$ (in fact, $P ⩽_{g W}^{1} Q$ ) such that $P ≰_{W} Q ⋆ Q$ .
Proof.
Suppose that Q has a computable instance. If we fix a computable Q-instance A, then for every multivalued function P, every P-instance uniformly computes A. By (1) ⇔ (3) in Theorem 23, $sup {P : P ⩽_{g W}^{2} Q}$ exists and is equal to $Q ⋆ Q$ .

Suppose that Q has no computable instance. Consider $P = id$ . We have that $P ⩽_{g W}^{1} Q$ , yet P-instances do not uniformly compute Q-instances. By the contrapositive of (1) ⇒ (3) in Theorem 23, $P ≰_{W} Q ⋆ Q$ . □
Corollary 29.
If Q is pointed, then $\begin{matrix} sup_{Λ} Q ∙_{Λ} \overline{Q} \equiv_{W} Q ⋆ Q \equiv_{W} sup {P : P ⩽_{g W}^{2} Q} . \end{matrix}$

Proposition 28 inspired us to consider $⩽_{g W}^{1}$ instead of $⩽_{W}$ . That gives us a cleaner analog of Theorem 23: Theorem 30.
The following are equivalent:
$P ⩽_{g W}^{1} Q ⋆ Q$ ;

$P ⩽_{g W}^{2} Q$ ;

there is a functional Θ such that $P ⩽_{g W}^{1} Q ∙_{Θ} \overline{Q}$ .

Proof.
(1) ⇒ (2). Let D be the domain of P. By Proposition 12, fix a computable partition $D_{0}$ and $D_{1}$ of D such that $P ↾ D_{0}$ is uniformly computable and $P ↾ D_{1} ⩽_{W} Q ⋆ Q$ . By (1) ⇒ (2) in Theorem 23, there is a strategy for II witnessing that $P ↾ D_{1} ⩽_{g W}^{2} Q$ , which always wins in the third round. By Proposition 15, $P ⩽_{g W}^{2} Q$ as desired.

(2) ⇒ (3). Let D be the domain of P. By Proposition 15, fix a computable partition $D_{0}$ and $D_{1}$ of D such that $P ↾ D_{0}$ is uniformly computable, and there exists a strategy Φ witnessing that $P ↾ D_{1} ⩽_{g W}^{2} Q$ which always wins in the third round. By (2) ⇒ (4) in Theorem 23, there is some Θ such that $P ↾ D_{1} ⩽_{W} Q ∙_{Θ} \overline{Q}$ . By Proposition 12, $P ⩽_{g W}^{1} Q ∙_{Θ} \overline{Q}$ as desired.

(3) ⇒ (1). By Theorem 27, $Q ∙_{Θ} \overline{Q} ⩽_{W} Q ⋆ Q$ . The desired result follows from Corollary 17. □

4. Finite compositions of arbitrary multivalued functions

Many of the results in Section 3 can be easily generalized to finite compositions of a multivalued function with itself. In this section, we generalize some of our results to the finite composition of (possibly) different multivalued functions. We show that such a composition can be thought of in terms of the following generalized reduction game.

Definition 31.
For multivalued functions P, $Q_{0}, \dots, Q_{n - 1}$ , define the game reducing P to $Q_{n - 1}, \dots, Q_{0}$ as follows. In round 1, Player I starts by playing a P-instance $X_{0}$ . Player II responds with either of the following:
an $X_{0}$ -computable P-solution to $X_{0}$ ;

an $X_{0}$ -computable $Q_{0}$ -instance $Y_{1}$ ;
and an indication of which case it is (for the first case, II declares victory).

Subsequently, for $k ⩾ 1$ , in round $k + 1$ , Player I plays a solution $X_{k}$ to the $Q_{k - 1}$ -instance $Y_{k}$ . Player II responds with either of the following:
a $(⨁_{i < k + 1} X_{i})$ -computable P-solution to $X_{0}$ ;

if $k < n$ , a $(⨁_{i < k + 1} X_{i})$ -computable $Q_{k}$ -instance $Y_{k + 1}$ ;
and an indication of which case it is (for the first case, II declares victory).

Player II wins if it declares victory on round $n + 1$ or before, after which the game ends. Otherwise Player I wins, which happens exactly if Player II has no possible move in some round. (If the game reaches round $n + 1$ , the only possible move for II is to declare victory, if it can.)
Note.
In the game reducing P to Q, if II was able to make a move in round 1, then it can repeat said move for all subsequent rounds. This is not always possible for the game reducing P to $Q_{n - 1}, \dots, Q_{0}$ .
Definition 32.
A Turing functional Φ is a computable strategy for II for the game reducing P to $Q_{n - 1}, \dots, Q_{0}$ if for all $k ⩽ n$ , if $Z = ⨁_{i < k + 1} X_{i}$ is the join of Player I’s first $k + 1$ moves in some run of said game, then $Φ^{Z} = V \oplus Y$ , where
if $V = {0}$ , then Y is a Z-computable solution to the P-instance $X_{0}$ (this must happen if $k = n$ );

otherwise, $V = \emptyset$ and Y is a Z-computable $Q_{k}$ -instance.
We define $\hat{Φ}$ and the join operation as before.

We say that $P ⩽_{g W}^{(n)} Q_{n - 1}, \dots, Q_{0}$ if there is a computable winning strategy for II for the game reducing P to $Q_{n - 1}, \dots, Q_{0}$ .

Unlike $⩽_{g W}^{n}$ , $⩽_{g W}^{(n)}$ does not seem to admit a nice characterization like that in Proposition 15. That is, assuming that $P ⩽_{g W}^{(n)} Q_{n - 1}, \dots, Q_{0}$ , one may not be able to divide the domain of P into finitely many sets, on each of which II has a strategy which always wins in a certain number of rounds. Take for example a run where a strategy Φ wins the game reducing P to $Q_{n - 1}, \dots, Q_{0}$ in some round $1 < k < n + 1$ . We may not be able to delay Φ’s victory because there may not be any $Q_{k + 1}$ -instance which is computable in I’s plays. Even if there is such a $Q_{k + 1}$ -instance, we may not be able to compute it uniformly from I’s plays. Whether we can do so may depend on I’s choice of solutions to the instances played by II. Therefore, we do not have an analog of Theorem 30 in this context.

Next, we prove an analog of Corollary 17. We could prove an analog of Proposition 16 and use that to derive an analog of Corollary 17, but that would be messy.
Proposition 33.
Suppose $P_{0} ⩽_{W} P_{1}$ and $Q_{i} ⩽_{W} R_{i}$ for each $i < n$ . If $P_{1} ⩽_{g W}^{(n)} Q_{n - 1}, \dots, Q_{0}$ , then $P_{0} ⩽_{g W}^{(n)} R_{n - 1}, \dots, R_{0}$ . Moreover, if $P_{1} ⩽_{g W}^{(n)} Q_{n - 1}, \dots, Q_{0}$ with a strategy that always wins in the last round, then $P_{0} ⩽_{g W}^{(n)} R_{n - 1}, \dots, R_{0}$ with a strategy that always wins in the last round as well.
Proof.
Fix Γ and Δ witnessing that $P_{0} ⩽_{W} P_{1}$ , and for each $i < n$ , fix $Γ_{i}$ and $Δ_{i}$ witnessing that $Q_{i} ⩽_{W} R_{i}$ . Fix a strategy Φ witnessing that $P_{1} ⩽_{g W}^{(n)} Q_{n - 1}, \dots, Q_{0}$ . We describe a strategy Ψ witnessing that $P_{0} ⩽_{g W}^{(n)} R_{n - 1}, \dots, R_{0}$ , such that if Φ always wins in round $n + 1$ , then so does Ψ. The idea is as follows: while we play the game $G_{0}$ reducing $P_{0}$ to $R_{n - 1}, \dots, R_{0}$ , we play a parallel game $G_{1}$ reducing $P_{1}$ to $Q_{n - 1}, \dots, Q_{0}$ , where II follows the strategy Φ.

In the game $G_{0}$ , I starts by playing a $P_{0}$ -instance $X_{0}$ . Then $Γ (X_{0})$ is a $P_{1}$ -instance, so we may start the game $G_{1}$ with the $P_{1}$ -instance $Γ (X_{0})$ and with II following the strategy Φ. In $G_{1}$ , II either plays a $P_{1}$ -solution to $Γ (X_{0})$ and declares victory, or a $Q_{0}$ -instance.

If II plays a $P_{1}$ -solution to $Γ (X_{0})$ , then we may apply Δ to obtain a $P_{0}$ -solution to $X_{0}$ . II can then play this set in $G_{0}$ and declare victory.

On the other hand, if II plays a $Q_{0}$ -instance, then we may apply $Γ_{0}$ to obtain an $R_{0}$ -instance. II can then play this set in $G_{0}$ , continuing the game.

In $G_{0}$ (if II has not already won), I responds by playing an $R_{0}$ -solution to II’s previous play in $G_{0}$ . Then we may apply $Δ_{0}$ to obtain a $Q_{0}$ -solution to II’s previous play in $G_{1}$ . We make I play this set in $G_{1}$ .

Next, in $G_{1}$ , II (following Φ) either plays a $P_{1}$ -solution to $Γ (X_{0})$ and declares victory, or plays a $Q_{1}$ -instance. The rest of the game proceeds as above.

We have described our strategy for the first two rounds of $G_{0}$ . We omit the formal construction and verification. □

Our final main theorem (analogous to Theorem 23) is as follows:
Theorem 34.
For multivalued functions $P, Q_{n - 1}, \dots, Q_{0}$ , the following are equivalent:
$P ⩽_{W} Q_{n - 1} ⋆ \dots ⋆ Q_{0}$ ;

there is a strategy for II witnessing that $P ⩽_{g W}^{(n)} Q_{n - 1}, \dots, Q_{0}$ which always wins in round $n + 1$ , or P has empty domain;

there are functionals $Θ_{0}, \dots, Θ_{n - 2}$ such that

$P ⩽_{W} \overline{Q_{n - 1}} ∙_{Θ_{n - 2}} (\overline{Q_{n - 2}} ∙_{Θ_{n - 3}} (\dots (\overline{Q_{1}} ∙_{Θ_{0}} \overline{Q_{0}})))$ .

Before we give the proof, we state some observations. First, if all $Q_{i}$ are pointed, then the extra condition in (2) is unnecessary (cf. the observation before Proposition 15):
Corollary 35.
For multivalued functions $P, Q_{n - 1}, \dots, Q_{0}$ such that P has nonempty domain and all $Q_{i}$ are pointed, $P ⩽_{W} Q_{n - 1} ⋆ \dots ⋆ Q_{0}$ if and only if $P ⩽_{g W}^{(n)} Q_{n - 1}, \dots, Q_{0}$ .
Proof.
(⇒) follows from (1) ⇒ (2) in Theorem 34. For (⇐), fix computable instances of each $Q_{i}$ . Then any strategy witnessing that $P ⩽_{g W}^{(n)} Q_{n - 1}, \dots, Q_{0}$ can be padded to obtain a strategy which always wins in the last round: simply play the appropriate computable instances and ignore the solutions. Then apply (2) ⇒ (1) from Theorem 34. □

Unlike Proposition 28, even if for all P, we have $P ⩽_{W} Q_{n - 1} ⋆ \dots ⋆ Q_{0}$ if and only if $P ⩽_{g W}^{(n)} Q_{n - 1}, \dots, Q_{0}$ , it does not follow that all $Q_{i}$ have computable instances. (See the comments before Proposition 33.)

Next, note that strategies in the game reducing P to $Q_{n - 1}, \dots, Q_{0}$ are allowed to refer to each $Q_{i}$ -instance played thus far, while $∙_{Θ}$ only allows reference to the $Q_{i}$ -instance just played. Therefore in (3), we use $\overline{Q_{i}}$ instead of $Q_{i}$ . The extra coordinate in a $\overline{Q_{i}}$ -instance can be used to encode every $Q_{j}$ -instance played thus far. For the last factor ( $i = n - 1$ ), we can get away with $Q_{n - 1}$ instead of $\overline{Q_{n - 1}}$ (as is the case in Theorem 23). Nevertheless, we state the theorem with $\overline{Q_{n - 1}}$ because this obviates the need to consider an extra case in the proof of (2) ⇒ (3).

We now prove Theorem 34: Proof.
(1) ⇒ (2). By Lemma 9, since $P ⩽_{W} Q_{n - 1} ⋆ \dots ⋆ Q_{0}$ , there are multivalued functions $R_{0}, \dots, R_{n - 1}$ such that $R_{i} ⩽_{W} Q_{i}$ for all $i < n$ , and $P ⩽_{W} R_{n - 1} \circ \dots \circ R_{0}$ .

By Proposition 33, it suffices to give a computable strategy for II which always wins the game reducing $R_{n - 1} \circ \dots \circ R_{0}$ to $Q_{n - 1}, \dots, Q_{0}$ in round $n + 1$ . For each $i < n$ , fix $Γ_{i}$ and $Δ_{i}$ witnessing that $R_{i} ⩽_{W} Q_{i}$ .

In order to illustrate the construction, we describe the strategy for the first three rounds before giving the general description. I starts by playing an $(R_{n - 1} \circ \dots \circ R_{0})$ -instance $X_{0}$ . (If $R_{n - 1} \circ \dots \circ R_{0}$ has empty domain, then so does P and we are done.) II has to respond with an $X_{0}$ -computable $Q_{0}$ -instance. Note that $X_{0}$ is in particular an $R_{0}$ -instance, so II can play the $Q_{0}$ -instance $Γ_{0} (X_{0})$ .

Next, I plays a $Q_{0}$ -solution $X_{1}$ to $Γ_{0} (X_{0})$ . II has to respond with an $(X_{0} \oplus X_{1})$ -computable $Q_{1}$ -instance. Since $X_{0}$ is an $(R_{n - 1} \circ \dots \circ R_{0})$ -instance, any $R_{0}$ -solution to $X_{0}$ is itself an $(R_{n - 1} \circ \dots \circ R_{1})$ -instance, which is in particular an $R_{1}$ -instance. We can obtain an $R_{0}$ -solution to $X_{0}$ by applying $Δ_{0}$ to $X_{0} \oplus X_{1}$ . As explained above, that gives us an $R_{1}$ -instance, to which we can apply $Γ_{1}$ to obtain a $Q_{1}$ -instance. Therefore II plays $Γ_{1} (Δ_{0} (X_{0} \oplus X_{1}))$ .

In the third round, I plays a $Q_{1}$ -solution $X_{2}$ to $Γ_{1} (Δ_{0} (X_{0} \oplus X_{1}))$ . II has to respond with an $(X_{0} \oplus X_{1} \oplus X_{2})$ -computable $Q_{2}$ -instance.

Since $Δ_{0} (X_{0} \oplus X_{1})$ is an $(R_{n - 1} \circ \dots \circ R_{1})$ -instance, any $R_{1}$ -solution to $Δ_{0} (X_{0} \oplus X_{1})$ is itself an $(R_{n - 1} \circ \dots \circ R_{2})$ -instance, which is in particular an $R_{2}$ -instance. We can obtain an $R_{1}$ -solution to $Δ_{0} (X_{0} \oplus X_{1})$ by applying $Δ_{1}$ to $Δ_{0} (X_{0} \oplus X_{1}) \oplus X_{2}$ . That gives us an $R_{2}$ -instance, to which we can apply $Γ_{2}$ to obtain a $Q_{2}$ -instance. Therefore II plays $Γ_{2} (Δ_{1} (Δ_{0} (X_{0} \oplus X_{1}) \oplus X_{2}))$ .

We have described our strategy for the first three rounds. Formally, define the auxiliary functional Ξ by recursion: $\begin{array}{l} Ξ (X_{0}) = X_{0} \\ Ξ (⨁_{j < k + 1} X_{j}) = Δ_{k - 1} (Ξ (⨁_{j < k} X_{j}) \oplus X_{k}) if k ⩽ n . \end{array}$ For example, $Ξ (X_{0} \oplus X_{1}) = Δ_{0} (X_{0} \oplus X_{1})$ . Then we can define our strategy as follows. Suppose that in round k, I plays $X_{k - 1}$ . In round $k < n + 1$ , II plays the $Q_{k - 1}$ -instance $Γ_{k - 1} (Ξ (⨁_{j < k} X_{j}))$ . In round $n + 1$ , II declares victory and plays $Ξ (⨁_{j < n + 1} X_{j})$ .

Verification. We show by simultaneous induction on k that:
for every $1 ⩽ k < n + 1$ , $Ξ (⨁_{j < k} X_{j})$ is an $(R_{n - 1} \circ \dots \circ R_{k - 1})$ -instance;

for every $1 ⩽ k ⩽ n + 1$ , II’s move in round k is legal;

for every $1 < k ⩽ n + 1$ , $Ξ (⨁_{j < k} X_{j})$ is an $R_{k - 2}$ -solution to the $(R_{n - 1} \circ \dots \circ R_{k - 2})$ -instance $Ξ (⨁_{j < k - 1} X_{j})$ .

Base case. By definition of Ξ and the game, (i) holds for $k = 1$ .

Inductive step 1. Suppose (i) holds for some $1 ⩽ k < n + 1$ . Then $Ξ (⨁_{j < k} X_{j})$ is in particular an $R_{k - 1}$ -instance, so by choice of $Γ_{k - 1}$ , II’s move in round k is a $Q_{k - 1}$ -instance. Also, $Γ_{k - 1} \circ Ξ$ is computable. Therefore (ii) holds for k.

Inductive step 2. Suppose (i) and (ii) hold for some $1 ⩽ k < n + 1$ . Then in round $k + 1$ , I plays a solution $X_{k}$ to II’s move in round k. By our choice of $Δ_{k - 1}$ and the definition of Ξ, (iii) holds for $k + 1$ .

Inductive step 3. Suppose (iii) holds for some $1 < k < n + 1$ . By definition of ∘, (i) is true for k as well.

The base case and inductive steps prove (i), (ii), and (iii) for the desired values of k, except (ii) for $k = n + 1$ . We prove that as follows. Since (iii) holds for every $1 < k ⩽ n + 1$ , by definition of ∘, $Ξ (⨁_{j < n + 1} X_{j})$ is a $(R_{n - 1} \circ \dots \circ R_{0})$ -solution to $X_{0}$ . Therefore $Ξ (⨁_{j < n + 1} X_{j})$ is a winning move for II in round $n + 1$ . We have defined a strategy for II which always wins the game reducing P to $Q_{n - 1}, \dots, Q_{0}$ in round $n + 1$ .

(2) ⇒ (3). If P has empty domain, (3) vacuously holds. Otherwise, fix a strategy Φ for II which always wins the game reducing P to $Q_{n - 1}, \dots, Q_{0}$ in round $n + 1$ . We have to define $Θ_{0}, \dots, Θ_{n - 2}$ and forward and backward functionals witnessing that $P ⩽_{W} \overline{Q_{n - 1}} ∙_{Θ_{n - 2}} (\overline{Q_{n - 2}} ∙_{Θ_{n - 3}} (\dots (\overline{Q_{1}} ∙_{Θ_{0}} \overline{Q_{0}})))$ .

Suppose we are given a P-instance $X_{0}$ , from which we need to compute a $\overline{Q_{n - 1}} ∙_{Θ_{n - 2}} (\overline{Q_{n - 2}} ∙_{Θ_{n - 3}} (\dots (\overline{Q_{1}} ∙_{Θ_{0}} \overline{Q_{0}})))$ -instance. Regardless of our definitions of $Θ_{0}, \dots, Θ_{n - 2}$ , such a set must be a $\overline{Q_{0}}$ -instance. As a starting point, we can obtain a $Q_{0}$ -instance by applying $\hat{Φ}$ to $X_{0}$ . Also, we want to include $X_{0}$ in the $\overline{Q_{0}}$ -instance so that we can use it in the future. Hence, we define the forward functional Γ to send $X_{0}$ to the $\overline{Q_{0}}$ -instance $(X_{0}, \hat{Φ} (X_{0}))$ .

Next, we need to define $Θ_{0}$ so that for every $\overline{Q_{0}}$ -solution $X_{1}$ to $(X_{0}, \hat{Φ} (X_{0}))$ , $Θ_{0} ((X_{0}, \hat{Φ} (X_{0})) \oplus X_{1})$ is a $\overline{Q_{1}}$ -instance. Since $X_{1}$ is a $Q_{0}$ -solution to $\hat{Φ} (X_{0})$ , we can obtain a $Q_{1}$ -instance by applying $\hat{Φ}$ to $X_{0} \oplus X_{1}$ . Also, we want to include $X_{0}$ and $X_{1}$ in the $\overline{Q_{1}}$ -instance so that we can use them in the future. Hence, we define $Θ_{0}$ to output the $\overline{Q_{1}}$ -instance $(X_{0} \oplus X_{1}, \hat{Φ} (X_{0} \oplus X_{1}))$ .

In general, for $0 ⩽ m ⩽ n - 2$ , define $Θ_{m}$ by $\begin{matrix} (X_{0}, \hat{Φ} (X_{0})) \oplus (((X_{1}, X_{2}), \dots), X_{m + 1}) \mapsto (⨁_{i < m + 2} X_{i}, \hat{Φ} (⨁_{i < m + 2} X_{i})) . \end{matrix}$

Finally, we want to solve $X_{0}$ using a $\overline{Q_{n - 1}} ∙_{Θ_{n - 2}} (\dots (\overline{Q_{1}} ∙_{Θ_{0}} \overline{Q_{0}}))$ -solution to $(X_{0}, \hat{Φ} (X_{0}))$ . Such a solution has the form $(((X_{1}, X_{2}), \dots), X_{n})$ . We will show in the verification that there is a run of the game reducing P to $Q_{n - 1}, \dots, Q_{0}$ where II follows the strategy Φ and at round m, I plays $X_{m - 1}$ . Since Φ always wins in round $n + 1$ , $\hat{Φ} (⨁_{i < n + 1} X_{i})$ must be a P-solution to $X_{0}$ . Therefore, we define the backward functional Δ by mapping $X_{0} \oplus (((X_{1}, X_{2}), \dots), X_{n})$ to $\hat{Φ} (⨁_{i < n + 1} X_{i})$ .

Verification. We show that $P ⩽_{W} \overline{Q_{n - 1}} ∙_{Θ_{n - 2}} (\overline{Q_{n - 2}} ∙_{Θ_{n - 3}} (\dots (\overline{Q_{1}} ∙_{Θ_{0}} \overline{Q_{0}})))$ via Γ and Δ. Fix a P-instance $X_{0}$ . We show by simultaneous induction on k that
for each $0 ⩽ k ⩽ n - 1$ , $Γ (X_{0})$ is a $\overline{Q_{k}} ∙_{Θ_{k - 1}} (\dots (\overline{Q_{1}} ∙_{Θ_{0}} \overline{Q_{0}}))$ -instance;

for each $0 ⩽ k ⩽ n - 1$ , if $(((X_{1}, X_{2}), \dots), X_{k + 1})$ is a $\overline{Q_{k}} ∙_{Θ_{k - 1}} (\dots (\overline{Q_{1}} ∙_{Θ_{0}} \overline{Q_{0}}))$ -solution to $Γ (X_{0})$ , then there is a partial run of the game reducing P to $Q_{n - 1}, \dots, Q_{0}$ where II follows the strategy Φ and at round $1 ⩽ m ⩽ k + 2$ , I plays $X_{m - 1}$ .

Base case. We show that (i) holds for $k = 0$ . Since $X_{0}$ is a P-instance and Φ always wins in round $n + 1$ , it follows that $\hat{Φ} (X_{0})$ is a $Q_{0}$ -instance. Therefore $Γ (X_{0}) = (X_{0}, \hat{Φ} (X_{0}))$ is a $\overline{Q_{0}}$ -instance.

Inductive step 1. Assuming that for some $0 ⩽ k ⩽ n - 1$ , we have that (ii) holds for all $0 ⩽ m < k$ and (i) holds for k, we show that (ii) holds for k. Let $(((X_{1}, X_{2}), \dots), X_{k + 1})$ be a $\overline{Q_{k}} ∙_{Θ_{k - 1}} (\dots (\overline{Q_{1}} ∙_{Θ_{0}} \overline{Q_{0}}))$ -solution to $Γ (X_{0})$ . We start by showing that there is a partial run where II follows the strategy Φ and at round $1 ⩽ m ⩽ k + 1$ , I plays $X_{m - 1}$ .

If $k = 0$ , then I starts by playing the P-instance $X_{0}$ . If $k > 0$ , by definition of ∙, $(((X_{1}, X_{2}), \dots), X_{k})$ is a $\overline{Q_{k - 1}} ∙_{Θ_{k - 2}} (\dots (\overline{Q_{1}} ∙_{Θ_{0}} \overline{Q_{0}}))$ -solution to $Γ (X_{0})$ . By assumption, (ii) holds for $k - 1$ , so there is a partial run where II follows the strategy Φ and at round $1 ⩽ m ⩽ k + 1$ , I plays $X_{m - 1}$ .

Now, we extend said partial run. By choice of $(((X_{1}, X_{2}), \dots), X_{k + 1})$ and definition of ∙, $X_{k + 1}$ is a $\overline{Q_{k}}$ -solution to $Θ_{k - 1} (Γ (X_{0}) \oplus (((X_{1}, X_{2}), \dots), X_{k}))$ , which is defined to be $(⨁_{i < k + 1} X_{i}, \hat{Φ} (⨁_{i < k + 1} X_{i}))$ . Therefore $X_{k + 1}$ is a $Q_{k}$ -solution to $\hat{Φ} (⨁_{i < k + 1} X_{i})$ , and so we may extend the aforementioned run by making I play $X_{k + 1}$ . This proves that (ii) holds for k.

Inductive step 2. Assuming that (i) and (ii) hold for some $0 ⩽ k < n - 1$ , we show that (i) holds for $k + 1$ . Since (i) holds for k, it remains to show that if $(((X_{1}, X_{2}), \dots), X_{k + 1})$ is a $\overline{Q_{k}} ∙_{Θ_{k - 1}} (\dots (\overline{Q_{1}} ∙_{Θ_{0}} \overline{Q_{0}}))$ -solution to $Γ (X_{0})$ , then $Θ_{k} (Γ (X_{0}) \oplus (((X_{1}, X_{2}), \dots), X_{k + 1})) = (⨁_{i < k + 2} X_{i}, \hat{Φ} (⨁_{i < k + 2} X_{i}))$ is a $\overline{Q_{k + 1}}$ -instance.

Indeed, let us apply (ii) for k to $(((X_{1}, X_{2}), \dots), X_{k + 1})$ . Since Φ always wins in round $n + 1$ and $k + 2 < n + 1$ , we have that $\hat{Φ} (⨁_{i < k + 2} X_{i})$ is a $Q_{k + 1}$ -instance. We have shown that (i) holds for $k + 1$ , completing the proof of inductive step 2.

Applying the above base case and inductive steps, we may deduce (i) and (ii) for $k = n - 1$ . To complete the proof, we show that if $(((X_{1}, X_{2}), \dots), X_{n})$ is a $\overline{Q_{n - 1}} ∙_{Θ_{n - 2}} (\dots (\overline{Q_{1}} ∙_{Θ_{0}} \overline{Q_{0}}))$ -solution to $Γ (X_{0})$ , then $Δ (X_{0} \oplus (((X_{1}, X_{2}), \dots), X_{n})) = \hat{Φ} (⨁_{i < n + 1} X_{i})$ is a P-solution to $X_{0}$ .

By (ii) for $k = n - 1$ , there is a partial run where II follows the strategy Φ and at round $1 ⩽ m ⩽ n + 1$ , I plays $X_{m - 1}$ . Since Φ wins in round $n + 1$ , $\hat{Φ} (⨁_{i < n + 1} X_{i})$ is a P-solution to $X_{0}$ as desired.

(3) ⇒ (1). Induction on n using Proposition 21. □

5. The $\equiv_{g W}^{1}$ -lattice

Recall from Proposition 12 that $P ⩽_{g W}^{1} Q$ if and only if $P ⩽_{W} Q ⊔ id$ . It follows that $⩽_{g W}^{1}$ is reflexive and transitive, so we can define the associated notion of $\equiv_{g W}^{1}$ and $\equiv_{g W}^{1}$ -degrees. As a notion of reduction between problems, we find $⩽_{g W}^{1}$ more intuitive than $⩽_{W}$ . This is because in order to show that $P ⩽_{W} Q$ , one is obliged to compute a Q-instance from every P-instance, even if one could already compute a solution to said P-instance. See also Theorem 30.

Using Proposition 12, it is easy to show that the $\equiv_{g W}^{1}$ -degrees form a distributive lattice with the usual join and meet operations. In fact, Pauly5

⁵
Arno Pauly, personal communication.

has pointed out that the

\equiv_{g W}^{1}

-lattice is isomorphic to the pointed Weihrauch lattice, which was studied by Higuchi and Pauly [8]. It is easy to show that the pointed Weihrauch degrees (under

⩽_{W}

) form a lattice under the usual join and meet operations.

Proposition 36 (Pauly).

The $\equiv_{g W}^{1}$ -lattice and the pointed Weihrauch lattice are isomorphic.

Proof.

By Proposition 12, $P ⩽_{g W}^{1} Q$ if and only if $P ⩽_{W} Q ⊔ id$ . Also, it is easy to see that $P ⩽_{W} Q ⊔ id$ if and only if $P ⊔ id ⩽_{W} Q ⊔ id$ . Next, note that if P is pointed, then $P ⊔ id \equiv_{W} P$ . So $P \mapsto P ⊔ id$ is an isomorphism between the $\equiv_{g W}^{1}$ -degrees and the pointed Weihrauch degrees. Hence $P \mapsto P ⊔ id$ is in fact a lattice isomorphism. □

Footnotes

Acknowledgements

We thank Richard A. Shore for many useful discussions and suggestions. We also thank the referees for their helpful comments. This research was partially supported by NSF grant DMS-1161175.

References

Brattka,

de Brecht and

Pauly, Closed choice and a uniform low basis theorem, Ann. Pure Appl. Logic163(8) (2012), 986–1008. doi:10.1016/j.apal.2011.12.020.

Brattka and

Gherardi, Weihrauch degrees, omniscience principles and weak computability, J. Symbolic Logic76(1) (2011), 143–176. doi:10.2178/jsl/1294170993.

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 and

Pauly, On the algebraic structure of Weihrauch degrees, Log. Methods Comput. Sci.14(4) (2018), Paper No. 4, 36. doi:10.1080/10724117.2007.11974704.

Brattka and

Rakotoniaina, On the uniform computational content of Ramsey’s theorem, J. Symb. Log.82(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.

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.

Higuchi and

Pauly, The degree structure of Weihrauch reducibility, Log. Methods Comput. Sci.9(2) (2013), 2:02, 17. doi:10.2168/LMCS-9(2:2)2013.

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. doi:10.1142/S0219061316500021.

10.

J.L.

Hirst and

Mummert, Using Ramsey’s theorem once, Arch. Math. Logic58(7–8) (2019), 857–866. doi:10.1007/s00153-019-00664-z.

11.

Patey, The weakness of being cohesive, thin or free in reverse mathematics, Israel J. Math.216(2) (2016), 905–955. doi:10.1007/s11856-016-1433-3.

12.

Pauly, On the (semi)lattices induced by continuous reducibilities, MLQ Math. Log. Q.56(5) (2010), 488–502. doi:10.1002/malq.200910104.

Compositions of multivalued functions

Abstract

Keywords

1. Introduction

1 In the reverse mathematics setting, Hirst and Mummert [10] gave such a proof in RCA 0 . Their proof was not “uniform”. In the setting of Weihrauch reducibility, Hirschfeldt and Jockusch [9], Brattka and Rakotoniaina [5], and Patey [11] independently showed that there is no reduction.

2.1. Parallel product

Definition 2 (Brattka, Gherardi [2]).

2.2. Compositional product

Lemma 7 (Brattka, Pauly [4, Lemma 21]).

Proposition 8 (Brattka, Pauly [4, Proposition 32]).

Definition 10 (Hirschfeldt, Jockusch [9, Definition 4.1]).

Definition 11 (Hirschfeldt, Jockusch [9, Definition 4.3]).

Definition 18 (Dorais, Dzhafarov, Hirst, Mileti, Shafer [7, §5.2]).

5 Arno Pauly, personal communication.

Footnotes

Acknowledgements

References

¹
In the reverse mathematics setting, Hirst and Mummert [10] gave such a proof in ${RCA}_{0}$ . Their proof was not “uniform”. In the setting of Weihrauch reducibility, Hirschfeldt and Jockusch [9], Brattka and Rakotoniaina [5], and Patey [11] independently showed that there is no reduction.

⁵
Arno Pauly, personal communication.