Weihrauch degrees without roots

Abstract

We answer the following question by Arno Pauly: “Is there a square root operator on the Weihrauch degrees?”. In fact, we show that there are uncountably many pairwise incomparable Weihrauch degrees without any roots. We also prove that the omniscience principles of $L P O$ and $L L P O$ do not have roots.

Keywords

Weihrauch reducibility compositional product limited principle of omniscience

1. Introduction

Weihrauch reducibility captures the idea of using a mathematical problem exactly once as an oracle in order to solve some other problem in an otherwise computable manner. We give a short introduction to this topic. For more details, see [5]. Given two spaces X and Y, a problem is simply given by a relation between X and Y. We interpret any such relation R as a partial multi-valued function $f :\subseteq X ⇉ Y$ , where $x \in X$ is in the domain of f (write $d o m (f)$ ) if and only if there exists some $y \in Y$ with $x R y$ . Then, $f (x)$ is the set of all such y. Elements $x \in d o m (f)$ are interpreted as instances of the problem f, and elements $y \in f (x)$ are interpreted as solutions for the given instance x of f. For example, $W K L$ is the problem that takes any infinite binary tree as an instance and returns a path through this tree as solution. Notice that $W K L$ is multi-valued since there may be multiple possible paths.

In the context of Weihrauch reducibility, problems are partial multi-valued functions $f :\subseteq X ⇉ Y$ whose spaces X and Y are so-called represented spaces (cf. [10]). Since we are only concerned with algebraical properties, we can restrict ourselves to the case $X := Y := N^{N}$ (cf. [5, Lemma 11.3.8]). Under this restriction, Weihrauch reducibility may be defined as follows:

Definition 1.1.
Given two problems $f, g :\subseteq N^{N} ⇉ N^{N}$ , we say that f is Weihrauch reducible to g (write $f ⩽_{W} g$ ) if and only if there are partial computable functions $h, k :\subseteq N^{N} \to N^{N}$ such that for any instance $x \in d o m (f)$ , the value $k (x)$ is an instance of g and any solution y for $k (x)$ of g results in a solution $h (⟨ x, y ⟩)$ for x of f.

Here, we write $⟨ x, y ⟩$ for one of the usual (uniformly) computable ways to express two number sequences $x, y \in N^{N}$ as a single one. In the following, we will often say that h and k (in this order) realize the Weihrauch reduction $f ⩽_{W} g$ .

Given two problems f and g, we may write $f \equiv_{W} g$ if both $f ⩽_{W} g$ and $g ⩽_{W} f$ hold. Taking the quotient of all problems with respect to $\equiv_{W}$ results in the lattice structure of Weihrauch degrees (cf. [5, Theorem 11.3.9], [3, Theorem 3.14], [12, Corollary 4.7]). Finally, we write $f <_{W} g$ , if both $f ⩽_{W} g$ and $f ≢_{W} g$ hold. Interesting examples of problems include the following (cf. [1] and [7] for the origins of $L P O$ and $L L P O$ , see [3, Definition 6.1] for the definitions that we are using): Definition 1.2.
Let us express any natural number $n \in N$ by a sequence $n \in N^{N}$ where every member of n is equal to n. We define the following problems:
The identity problem $i d : N^{N} \to N^{N}$ with
$\begin{aligned} i d (x) := x . \end{aligned}$

The limited principle of omniscience $L P O : N^{N} \to N^{N}$ with
$\begin{aligned} L P O (x) := {\begin{cases} 0 & if x ~has a zero, \\ 1 & otherwise . \end{cases} \end{aligned}$

The lesser limited principle of omniscience $L L P O :\subseteq N^{N} ⇉ N^{N}$ where $d o m (L L P O)$ only contains number sequences that have at most one non-zero member, with
$\begin{aligned} L L P O (x) := & {0 ∣ if x is zero at all even ~indices} \cup \\ {1 ∣ if x is zero at all o d d ~indices} . \end{aligned}$

Notice that $L L P O (0) = {0, 1}$ holds. For these examples, we have the following reducibilities: $i d <_{W} L L P O$ , $L L P O <_{W} L P O$ (cf. [16, Theorem 4.2]), and by transitivity $i d <_{W} L P O$ . Sometimes, we want to use one problem after another. This is captured by the compositional product: Definition 1.3.
We define the composition of problems f and g to be the multi-valued function $f \circ g :\subseteq N^{N} ⇉ N^{N}$ with $d o m (f \circ g) := {x \in d o m (g) ∣ g (x) \subseteq d o m (f)}$ and
$\begin{aligned} (f \circ g) (x) := {z \in N^{N} ∣ there exists y \in g (x) ~with~ z \in f (y)} . \end{aligned}$
For arbitrary problems f and g, we write $f * g$ for the compositional product, i.e., the degree satisfying
$\begin{aligned} f * g \equiv_{W} {max}_{⩽_{W}} {f^{'} \circ g^{'} ∣ f^{'} ⩽_{W} f ~and~ g^{'} ⩽_{W} g} . \end{aligned}$

Intuitively, $f * g$ contains the problem where we first apply g and then f by transforming the solution given by g into an instance of f. The compositional product was first defined in [4, Section 4]. Since maxima (or suprema) of sets of problems do not exist in general (cf. [8, Proposition 3.15]), the existence of compositional products for any given pair of problems had to be proven, which was done in [6, Corollary 3.7]. Moreover, compositions and compositional products enjoy properties like associativity (cf. [2, Proposition 2.4.1] and [6, Proposition 4.2]), and $i d$ is a neutral element with respect to $$ (cf. [6, Observation 4.3]). With (compositional) products defined, we can ask about roots: Definition 1.4.
Given a problem f and a number $n \in N$ , let us write $f^{[n]}$ for the compositional product of n-many copies of f (we set $f^{[0]} := i d$ ). Given a number $n ⩾ 2$ , we call a problem r an n-th root of f if and only if $f \equiv_{W} r^{[n]}$ holds.

Now, we have all the necessary ingredients in order to talk about the following open question by Arno Pauly (cf. [13]): Question 1.5.
Is there a square root operator on the Weihrauch degrees?

We show that such an operator cannot exist by proving the following theorem: Theorem 1.6.
There are uncountably many Weihrauch degrees that do not have an n-th root for any* $n ⩾ 2$ . In fact, the Turing degrees embed into a set of Weihrauch degrees with this property.

Moreover, we can also show that this result does not only hold for artificial Weihrauch degrees: Theorem 1.7.
The problems $L P O$ and $L L P O$ do not have an n-th root for any number $n ⩾ 2$ .

Finally, there are problems that only have some roots: Theorem 1.8.
For any $n ⩾ 2$ , there is a problem that has an n-th root but no $(n + 1)$ -th root.

2. Using Turing degrees

In this section, we prove the first part of Theorem 1.6 using the following family of problems:

Definition 2.1.
Let a be a Turing degree. We define $w_{a} : N^{N} ⇉ N^{N}$ with
$\begin{aligned} w_{a} (x) := {\begin{cases} {y \in N^{N} ∣ y is non-computable} & if x is computable, \\ {y \in N^{N} ∣ y has Turing degree > a} & if x is non-computable . \end{cases} \end{aligned}$

Before we state and prove all required lemmas, let us give a short sketch of the proof idea: Consider $w_{a}$ for some non-zero Turing degree a and assume that r is one of its roots. First, we notice that $w_{a}$ is defined everywhere and only has non-computable solutions. In particular: It has a computable instance that only has non-computable solutions. We show that this property must also hold for r. Then, we consider $w_{a} \circ r$ and easily conclude that this problem has a computable instance such that all of its solutions have a degree greater than or equal to a. By $w_{a} \circ r ⩽_{W} w_{a} * r ⩽_{W} r * w_{a}$ , we conclude that $r * w_{a}$ must have the same property. From this, we can extract some computable function e such that all solutions of $(r \circ e) (x)$ have a degree greater than or equal to a for any non-computable x. We conclude that $r \circ e \circ r$ has a computable instance such that all of its solutions have a degree greater than or equal to a. Finally, with $r \circ e \circ r ⩽_{W} r * i d * r ⩽_{W} w_{a}$ , we conclude that the same must hold for $w_{a}$ . This clearly contradicts the definition of $w_{a}$ .

When working with compositional products, we have to be extra careful because of the linear nature of Weihrauch reducibility (cf. [5, Section 11.9.1]). For example, there are problems f and g such that we cannot reduce f to $f * g$ or $g * f$ : Take $f := i d$ and let g be the problem with empty domain.

In the following, we are looking at roots r of problems with a domain that contains computable instances. Thus, r must also contain some computable element in its domain. We conclude $i d ⩽_{W} r$ . Now, given any problem f, we can always derive $f ⩽_{W} f * i d ⩽_{W} f * r$ and $f ⩽_{W} i d * f ⩽_{W} r * f$ . In particular, we have $r * r ⩽_{W} r^{[n]}$ for $n ⩾ 2$ . We will apply this observation implicitly.
Lemma 2.2.
The map $a \mapsto w_{a}$ is an embedding from Turing degrees into Weihrauch degrees.
Proof.
Let a and b be Turing degrees such that a is reducible to b. Then, $w_{a} ⩽_{W} w_{b}$ is realized by the identity functions: If x is computable, then any solution for $w_{b} (x)$ is a solution for $w_{a} (x)$ . Otherwise, if x is non-computable, then any solution for $w_{b} (x)$ has a Turing degree greater than or equal to b. Clearly, any such solution also yields a Turing degree greater than or equal to a. Thus, it is also a solution for $w_{a} (x)$ .

Let a and b be Turing degrees such that $w_{a}$ Weihrauch reduces to $w_{b}$ . First, assume that b is computable. Assume, for contradiction, that a is non-computable. Then, let $x \in N^{N}$ be of a Turing degree that is incomparable to a (cf. [9, Corollary 1]). Consider some arbitrary computable solution of $w_{b}$ for x. Nothing that we can compute using this solution and x has a Turing degree that is greater than or equal to a. This contradiction shows that a must have been the computable degree.

Otherwise, let b be non-computable. Assume that $h, k :\subseteq N^{N} \to N^{N}$ realize the Weihrauch reduction $w_{a} ⩽_{W} w_{b}$ . Let $x \in N^{N}$ have degree b. Since b is non-computable, x itself is a solution for the instance $k (x)$ of $w_{b}$ . Thus, $h (⟨ x, x ⟩)$ is a solution for the instance x of $w_{a}$ . Since this solution is Turing reducible to b, our claim follows from the fact that any solution for the instance x of $w_{a}$ has degree greater than or equal to a.

Next, we show that having a computable instance that only has non-computable solutions (or only solutions above a certain degree) is transferred to higher Weihrauch degrees.
Lemma 2.3.
Let a be some Turing degree and let f and g be problems with $f ⩽_{W} g$ . If f has a computable instance such that the degree b of any solution satisfies $b ⩾ a$ (or $b > a$ ), then g also has a computable instance with the same property.
Proof.
Let $x \in N^{N}$ be a computable instance of f such that all solutions in $f (x)$ have a degree b with $b ⩾ a$ (or $b > a$ ). Moreover, let $h, k :\subseteq N^{N} \to N^{N}$ realize the Weihrauch reduction $f ⩽_{W} g$ . Given an arbitrary solution y of $g (k (x))$ , we know that the degree b of the solution $h (⟨ x, y ⟩)$ must satisfy $b ⩾ a$ (or $b > a$ ). Thus, b is Turing reducible to the degree c of y. Finally, we conclude that the degree c of any solution y for the computable instance $k (x)$ of g must satisfy $c ⩾ a$ (or $c > a$ ).

Now, we see that having some computable instance that only has non-computable solutions is in a certain sense atomic, i.e., roots inherit this property.
Lemma 2.4.
Let a be some non-zero Turing degree and let $n \in N$ with $n ⩾ 2$ be such that r is an n-th root of $w_{a}$ . Then, r has a computable instance whose solutions are all non-computable.
Proof.
For contradiction, assume that all computable instances of r have a computable solution. Using this assumption and Lemma 2.3 (applied to the degree $a := 0$ ), we show that all computable instances of $r^{[k]}$ have a computable solution for $k \in N$ with $k ⩾ 1$ , by induction: For $k := 1$ , this holds by assumption. Now, assume that our claim has already been shown for $k ⩾ 1$ . Let $f ⩽_{W} r$ and $g ⩽_{W} r^{[k]}$ be such that $f \circ g$ has Weihrauch degree $r^{[k + 1]}$ . Let $x \in N^{N}$ be a computable instance of $f \circ g$ . By induction hypothesis, $g (x)$ has a computable solution $y \in N^{N}$ . By assumption on r, $f (y)$ has a computable solution $z \in N^{N}$ . We conclude that $(f \circ g) (x)$ has a computable solution z. Applying Lemma 2.3 to the reduction $r^{[k + 1]} ⩽_{W} f \circ g$ yields our claim that all computable instances of $r^{[k + 1]}$ have a computable solution. However, this is clearly false for $r^{[n]} \equiv_{W} w_{a}$ .
Lemma 2.5.
Let f be a problem and $h, k :\subseteq N^{N} \to N^{N}$ two computable functions. Then, we have $h \circ f \circ k ⩽_{W} f$ .
Proof.
The Weihrauch reduction is realized directly by the computable functions h and k: Let $x \in d o m (h \circ f \circ k)$ . By definition of the domain of compositions, $k (x)$ is defined and an instance of f. Now, let y be an arbitrary solution for the instance $k (x)$ of f. Again, by definition of the domain of compositions, y must be in the domain of h. Finally, $h (y) \in (h \circ f \circ k) (x)$ clearly is a solution for the instance x of $h \circ f \circ k$ .

Finally, we combine everything in order to prove the first part of Theorem 1.6. Proof of Theorem 1.6, first part. Proof of Theorem 1.6, first part.

We show that for any non-zero Turing degree a, the problem $w_{a}$ has no n-th root for $n \in N$ with $n ⩾ 2$ . Then, our claim follows from Lemma 2.2 and the well-known fact that there are uncountably many pairwise incomparable Turing degrees (cf. [14]). In fact, we can embed the non-zero Turing degrees into a set of Weihrauch degrees with the claimed property. We will see the extension to all Turing degrees in a proof at the end of Section 3.

Assume that r is an n-th root of $w_{a}$ for some non-zero Turing degree a. Let $f ⩽_{W} r$ and $g ⩽_{W} w_{a}$ be such that $f \circ g$ has Weihrauch degree $r * w_{a}$ . We have the chain of reductions $w_{a} \circ r ⩽_{W} w_{a} * r ⩽_{W} r * w_{a} ⩽_{W} f \circ g$ . From Lemma 2.4, we know that r has a computable instance such that all of its solutions are non-computable. Thus, $w_{a} \circ r$ has a computable instance such that all of its solutions have a degree that is greater than or equal to a. Via Lemma 2.3, this property is transferred to $f \circ g$ . We define $c \in N^{N}$ to be such a computable instance of $f \circ g$ .

Let $h, k :\subseteq N^{N} \to N^{N}$ realize the Weihrauch reduction $g ⩽_{W} w_{a}$ . Since $k (c)$ is computable, every non-computable $x \in N^{N}$ (which is a solution of $w_{a} (k (c))$ ) can be converted into a solution $h (⟨ c, x ⟩)$ of $g (c)$ . Let us write this process in form of a computable function: Let $e :\subseteq N^{N} \to N^{N}$ be the computable map defined by $e (x) := h (⟨ c, x ⟩)$ for any non-computable $x \in N^{N}$ .1 We have that $e (x)$ is a solution of $g (c)$ for any non-computable x.

Recall that r has a computable instance such that all its solutions are non-computable. Thus, $f \circ e \circ r$ has the same instance (since the range of e is a subset of $g (c) \subseteq d o m (f)$ ) and all of its solutions have a degree that is greater than or equal to a. Recall $f ⩽_{W} r$ . Also, we have $e \circ r ⩽_{W} r$ simply by Lemma 2.5. By definition of $r * r$ , this entails $f \circ (e \circ r) ⩽_{W} r * r ⩽_{W} r^{[n]} ⩽_{W} w_{a}$ . By Lemma 2.3, $w_{a}$ must have a computable instance that only has solutions of a degree greater than or equal to a. However, inspecting the definition of $w_{a}$ reveals that this is not the case.

3. Using continuity

In this section, we prove Theorem 1.7. While the arguments of the previous section relied on Turing degrees, our next proofs use continuity. Our arguments will make use of so-called continuous Weihrauch reducibility. This is defined like regular Weihrauch reducibility but now the functions h, k that realize the reducibility only have to be continuous and not necessarily computable. For problems f and g, we write $f ⩽_{W}^{*} g$ if and only if f continuously Weihrauch reduces to g. Similarly, we write $f \equiv_{W}^{*} g$ if and only if both $f ⩽_{W}^{*} g$ and $g ⩽_{W}^{*} f$ hold. Taking the quotient of the structure of problems with respect to $\equiv_{W}^{*}$ leads to the continuous Weihrauch degrees. Finally, we write $f <_{W}^{*} g$ if and only if both $f ⩽_{W}^{*} g$ and $f ≢_{W}^{*} g$ hold.

Let us, again, give a short sketch of the proof idea for $L P O$ (for $L L P O$ it is quite similar): First, we introduce a notion of weak continuity that is preserved by composing problems and that is transferred to lower Weihrauch problems. Then, we show that $L P O$ is weakly discontinuous. Therefore, any root r of $L P O$ must also be weakly discontinuous. We prove that $L P O$ continuously Weihrauch reduces to any weakly discontinuous problem, in particular, to r. Thus, we conclude $L P O * L P O ⩽_{W}^{*} L P O$ , a statement whose falsity is well-known.

There seems to be some connection between the following notion of k-weakly continuity and Weihrauch’s k-continuity (for single-valued functions) as discussed at Lemmas 3.4 and 3.5 (cf. [16, Definition 3.3]).

Definition 3.1.
Given a number sequence $x \in N^{N}$ and a number $n \in N$ , let us write $x ↾_{n}$ for the initial segment of x of length n.

Let $f :\subseteq N^{N} ⇉ N^{N}$ be a partial multi-valued function and let $k \in N$ be positive. We say that f is k-weakly continuous if and only if for any element $x \in d o m (f)$ and sequence $(y_{n})_{n \in N} \subseteq d o m (f)$ with $lim_{n \to \infty} y_{n} = x$ , there exists a solution $u \in f (x)$ such that for any $l < k$ and $m \in N$ , we can find $n ⩾ m$ together with a solution $v \in f (y_{n \cdot k + l})$ with $u ↾_{m} = v ↾_{m}$ . We say that f is k-weakly discontinuous if it is not k-weakly continuous.

Notice that if $f :\subseteq N^{N} ⇉ N^{N}$ is k-weakly continuous, then it is also $k^{'}$ -weakly continuous for $k > k^{'} ⩾ 1$ : Given a sequence $(y_{n})_{n \in N} \subseteq d o m (f)$ that is supposed to satisfy the properties of $k^{'}$ -weakly continuous, we define $(z_{n})_{n \in N} \subseteq d o m (f)$ with $z_{n \cdot k + l} := y_{n \cdot k^{'} + l}$ for $l < k^{'}$ and $z_{n \cdot k + l} := x$ , otherwise.

Moreover, if $f :\subseteq N^{N} \to N^{N}$ is single-valued and continuous, then it is k-weakly continuous for all $k \in N$ .
Lemma 3.2.
(i)
$L P O$ is 1 -weakly discontinuous.
(ii)
$L L P O$ is 2 -weakly discontinuous.

Proof.
For $L P O$ , choose $x := 1$ and let $y_{n}$ be the sequence with $y_{n} (n) = 0$ and $y_{n} (m) = 1$ for all $m \neq n$ , for all $n \in N$ . Clearly, $(y_{n})_{n \in N}$ converges to x. Now, for any solution $u \in f (x)$ , i.e. $u = 1$ , there exists $m := 1$ such that for all $n ⩾ m = 1$ and all solutions $v \in f (y_{n})$ , i.e. $v = 0$ , we have $u ↾_{m} = 1 ↾_{m} \neq 0 ↾_{m} = v ↾_{m}$ .

For $L L P O$ , choose $x := 0$ and let $y_{n}$ be the sequence with $y_{n} (n) = 1$ and $y_{n} (m) = 0$ for all $m \neq n$ , for all $n \in N$ . Similar to before, $(y_{n})_{n \in N}$ converges to x. Notice that for every even n, there is a 0 at every odd position in $y_{n}$ , and for every odd n, there is a 0 at every even position in $y_{n}$ . This entails $f (y_{n}) = {1}$ for even n and $f (y_{n}) = {0}$ for odd n. Now, for any solution $u \in f (x)$ , i.e. $u = 0$ (or $u = 1$ ), there exist $l := 0$ (or $l := 1$ ) and $m := 1$ such that for all $n ⩾ m = 1$ and all solutions $v \in f (y_{n \cdot k + l})$ , i.e. $v = 1$ (or $v = 0$ ), we have $u ↾_{m} = 0 ↾_{m} \neq 1 ↾_{m} = v ↾_{m}$ (or $u ↾_{m} = 1 ↾_{m} \neq 0 ↾_{m} = v ↾_{m}$ ).
Lemma 3.3.
Let $f, g :\subseteq N^{N} ⇉ N^{N}$ be two partial multi-valued functions and let $k \in N$ be a positive number. (i)
If $f ⩽_{W}^{} g$ holds and g is k-weakly continuous, then so is f.*
(ii)
If both f and g are k-weakly continuous, then so is $f \circ g$ .

In the presence of this lemma, we see that being k-weakly continuous actually is a property that transfers to any other problem of the same equivalence class, i.e., it is a property of the whole (continuous) Weihrauch degree.
Proof.
For (i), let $h, k :\subseteq N^{N} \to N^{N}$ realize the continuous Weihrauch reduction $f ⩽_{W}^{} g$ . In order to avoid naming collisions, let us say that g is i-weakly continuous for $i ⩾ 1$ . Given $x \in d o m (f)$ and $(y_{n})_{n \in N} \subseteq d o m (f)$ with $lim_{n \to \infty} y_{n} = x$ , we use the continuity of k, which yields $k (x) \in d o m (g)$ and $(k (y_{n}))_{n \in N} \subseteq d o m (g)$ with $lim_{n \to \infty} k (y_{n}) = k (x)$ . Now, we apply the assumption that g is i-weakly continuous. This provides a solution $u \in g (k (x))$ that satisfies the requirements of the continuity for g. Using the Weihrauch reducibility, we know that $u^{'} := h (⟨ x, u ⟩)$ is a solution of $f (x)$ . Let $l < i$ and $m^{'} \in N$ be arbitrary. Using the continuity of h, we know that there must be some $m_{1} \in N$ such that h only uses the first $m_{1}$ -many members of x and u in order to compute the first $m^{'}$ -many members of $u^{'}$ . Moreover, since we have $lim_{n \to \infty} y_{n} = x$ , we can find $m_{2} \in N$ such that $y_{n} ↾_{m_{1}} = x ↾_{m_{1}}$ holds for all $n ⩾ m_{2}$ . We take the maximum $m := max (m_{1}, m_{2})$ . Using the i-weakly continuity of g, we can find $n ⩾ m$ together with $v \in g (k (y_{n \cdot i + l}))$ satisfying $u ↾_{m} = v ↾_{m}$ . Using the Weihrauch reducibility, we find that $v^{'} := h (⟨ y_{n \cdot i + l}, v ⟩)$ is a solution for the instance $y_{n \cdot i + l}$ of f. We prove $u^{'} ↾_{m^{'}} = v^{'} ↾_{m^{'}}$ : First, $y_{n \cdot i + l} ↾_{m_{1}} = x ↾_{m_{1}}$ holds because of $n \cdot i + l ⩾ n ⩾ m ⩾ m_{2}$ . Second, $u ↾_{m_{1}} = v ↾_{m_{1}}$ holds because of $u ↾_{m} = v ↾_{m}$ and $m ⩾ m_{1}$ . By definition of $m_{1}$ , this entails $u^{'} ↾_{m^{'}} = v^{'} ↾_{m^{'}}$ .

For (ii), let $x \in d o m (f \circ g)$ and $(y_{n})_{n \in N} \subseteq d o m (f \circ g)$ with $lim_{n \to \infty} y_{n} = x$ . We use that fact that g is k-weakly continuous: Let $u \in g (x)$ be such that for any $l < k$ and $m \in N$ , we can find $n ⩾ m$ with a solution $v \in g (y_{n \cdot k + l})$ satisfying $u ↾_{m} = v ↾_{m}$ . From this, we can define a family of indices $(n_{(l, m)})_{(l, m) \in N \times N}$ with $n_{(l, m)} ⩾ m$ for all $m \in N$ and $l < k$ together with a sequence of elements $(v_{i})_{i \in N}$ with $v_{m \cdot k + l} \in g (y_{n_{(l, m)} \cdot k + l})$ such that $u ↾_{m} = v_{m \cdot k + l} ↾_{m}$ holds for all $m \in N$ and $l < k$ . Clearly, $(v_{i})_{i \in N}$ converges to u. Thus, we can use the fact that f is k-weakly continuous: This yields $u^{'} \in f (u) \subseteq (f \circ g) (x)$ such that for any $l < k$ and $m \in N$ , we can find $i ⩾ m$ together with a solution $v^{'} \in f (v_{i \cdot k + l}) \subseteq (f \circ g) (y_{n_{(l, i)} \cdot k + l})$ with $u^{'} ↾_{m} = v^{'} ↾_{m}$ . We conclude that for any $l < k$ and $m \in N$ , we can find $j := n_{(l, i)} ⩾ i ⩾ m$ together with a solution $v^{'} \in (f \circ g) (y_{j \cdot k + l})$ with $u^{'} ↾_{m} = v^{'} ↾_{m}$ .
Lemma 3.4.
Let f be a problem. Then, f is* 1 -weakly discontinuous if and only if we have $L P O ⩽_{W}^{*} f$ .

Compare this to Weihrauch’s result that $L P O$ continuously reduces to a single-valued problem $f :\subseteq N^{N} \to N^{N}$ if and only if f is discontinuous (cf. [16, Theorem 3.7]). Thus, the notion of 1-weakly continuity may be seen as an extension of (regular) continuity for multi-valued functions.
Proof of Lemma 3.4. Proof of Lemma 3.4.

If $L P O ⩽_{W}^{*} f$ holds, then f is 1-weakly discontinuous by Lemmas 3.2 and 3.3. If f is 1-weakly discontinuous, then there exist an element $x \in d o m (f)$ and a sequence $(y_{n})_{n \in N} \subseteq d o m (f)$ with $lim_{n \to \infty} y_{n} = x$ such that for any $u \in f (x)$ there exists some $m \in N$ such that for all $n ⩾ m$ any solution $v \in f (y_{n})$ satisfies $u ↾_{m} \neq v ↾_{m}$ .

For the construction of the continuous function $k : N^{N} \to N^{N}$ that produces instances of f, we set

\begin{aligned} k (z) := {\begin{cases} x & if z has no zero, \\ y_{n} & if the first zero in z is at index n \in N . \end{cases} \end{aligned}

Let us quickly check that k is continuous: Let

z \in N^{N}

and

n \in N

be arbitrary. If z does not contain a zero, then let

m \in N

be an index such that

x ↾_{n} = y_{m^{'}} ↾_{n}

holds for all

m^{'} ⩾ m

. Such an index m exists since

(y_{n})_{n \in N}

converges to x. Now, any

z^{'} \in N^{N}

with

z ↾_{m} = z^{'} ↾_{m}

does not have a zero at an index below m. Thus,

k (z^{'})

either maps to x or

y_{m^{'}}

for some

m^{'} ⩾ m

. We conclude

k (z) ↾_{n} = k (z^{'}) ↾_{n}

. Otherwise, if z does contain a zero, let

m \in N

be the first such index. Now, any

z^{'}

with

z ↾_{(m + 1)} = z^{'} ↾_{(m + 1)}

also has its first zero at index m. We conclude

k (z) = k (z^{'})

For the construction of the continuous function $h :\subseteq N^{N} \to N^{N}$ that produces solutions of $L P O$ , recall that for each $u \in f (x)$ there exists some $m \in N$ such that for all $n ⩾ m$ any solution $v \in f (y_{n})$ satisfies $u ↾_{m} \neq v ↾_{m}$ . For each $u \in f (x)$ and $m \in N$ , let us collect the finite number sequence $u ↾_{m}$ . Since there can only be at most countably infinitely many such number sequences, we can collect them in a list L that we may code in form of an infinite number sequence. Let us assume that this number sequence is available to us in form of an oracle. We will provide the definition of h in form of a computation that uses this oracle. Consequently, h will be continuous.

Let $z \in N^{N}$ be an instance of $L P O$ and let $w \in N^{N}$ be a solution for $k (z)$ of f. The computation works in stages: At stage $s \in N$ , take the next finite number sequence t of length m from L. First, we check if there is a zero in z with index below m or $s + 1$ . If this is the case, we terminate and return $0$ . Otherwise, we check if t is an initial segment of w. If this is the case, we terminate and return $1$ .

Let us verify that this procedure must eventually terminate for any input $z \in N^{N}$ : If z does contain a zero at position $n \in N$ , then this will be found out by stage $n + 1$ if the program did not already terminate at an earlier point. If z does not contain a zero, then the instance of f produced by $k (z)$ is x. Thus, w is a solution for $f (x)$ . Therefore, L must contain an initial segment of w. At some point during the execution, this initial segment will be considered and will make our program terminate with output $1$ .

Finally, we show that our program always gives the right answer: If it returns $0$ , then, by definition, this can only be the case if we have actually found a zero in z. If it returns $1$ , then we have found a finite number sequence t of length m in L such that t is an initial segment of w. Moreover, we know that z does not contain a zero at an index below m since we explicitly check for that. This will be important in a moment. By definition of t and m in L, we know that for all $n ⩾ m$ any solution $v \in f (y_{n})$ satisfies $t \neq v ↾_{m}$ . Thus, w cannot be a solution for the instance $y_{n}$ of f for $n ⩾ m$ . Therefore, $k (z)$ must be different from $y_{n}$ for $n ⩾ m$ . By definition of k, this entails that any zero in z must have an index below m. However, we explicitly ensured that this is not the case. We conclude that z does not contain any zeros.

Lemma 3.5.
Let f be a problem. Then, f is 2 -weakly discontinuous if and only if we have $L L P O ⩽_{W}^{*} f$ .

Again, this suggests a close connection to Weihrauch’s notion of 2-continuous.
Proof of Lemma 3.5. Proof of Lemma 3.5.

If $L L P O ⩽_{W}^{*} f$ holds, then f is 2-weakly discontinuous by Lemmas 3.2 and 3.3. If f is 2-weakly discontinuous, then there exist an element $x \in d o m (f)$ and a sequence $(y_{n})_{n \in N} \subseteq d o m (f)$ with $lim_{n \to \infty} y_{n} = x$ such that for any $u \in f (x)$ there exist $l < 2$ and $m \in N$ such that for all $n ⩾ m$ any solution $v \in f (y_{2 n + l})$ satisfies $u ↾_{m} \neq v ↾_{m}$ . For the construction of the continuous function $k : N^{N} \to N^{N}$ that produces instances of f, we choose

\begin{aligned} k (z) := {\begin{cases} x & if z only consists of zeros, \\ y_{n} & if the first non-zero value in z is at index n \in N . \end{cases} \end{aligned}

The proof that k is continuous works similar to the matching step in the proof of Lemma 3.4.

For the construction of the continuous function $h :\subseteq N^{N} \to N^{N}$ that produces solutions of $L L P O$ , recall that for each $u \in f (x)$ there exist $l < 2$ and $m \in N$ such that for all $n ⩾ m$ any solution $v \in f (y_{n \cdot 2 + l})$ satisfies $u ↾_{m} \neq v ↾_{m}$ . Similar to before, for each $u \in f (x)$ and $m \in N$ , we collect the finite number sequence $u ↾_{m}$ . Additionally, we remember the value of l, i.e., L consists of pairs $(u ↾_{m}, l)$ for any such u, l, and m.

Let $z \in N^{N}$ be an instance of $L L P O$ and let $w \in N^{N}$ be a solution for $k (z)$ of f. Similar to before, we work in stages: At stage $s \in N$ , take the next pair $(t, l)$ consisting of a finite number sequence t of length m and a value $l < 2$ from L. First, we check if there is a non-zero value in z with index below $2 m$ or $s + 1$ . If this is the case, we terminate and return $0$ (or $1$ ) if this index is odd (or even). Otherwise, we check if t is an initial segment of w. If this is the case, we terminate and return $0$ (or $1$ ) if l is equal to zero (or one).

We verify that this procedure terminates for any input $z \in N^{N}$ . If z does contain a non-zero value at index $n \in N$ , then our program terminates at stage $n + 1$ if it has not already terminated. Otherwise, if z only consists of zeros, then, the instance for f produced by k is equal to x. Thus, w is a solution for $f (x)$ . By definition of L, there must be some stage at which we choose a pair $(t, l)$ from L such that t is an initial segment of w. This will also make our program terminate.

Finally, we show that our program always gives a correct answer: If it terminates because it has found a non-zero value in z at index $n \in N$ , then, by definition of the domain of $L L P O$ , we know that this is the only index at which z can have a non-zero value. If n is odd, then all even indices of z must be equal to zero. Thus, $0$ , which is the output of our program in this case, is the only correct answer. Similarly, if n is even, our program returns the only correct answer $1$ .

If it terminates because it has found a pair $(t, l)$ in L such that t of length m is an initial segment of w, then we also know that every number in z with index below $2 m$ is equal to zero. If our program returns $0$ , then we can infer $l = 0$ . Thus, by definition of t, l, and m in L, we know that for all $n ⩾ m$ any solution $v \in f (y_{2 n + 0})$ satisfies $t \neq v ↾_{m}$ . Therefore, $w = y_{i}$ can only hold for indices $i \in N$ that are odd or satisfy $i < 2 m$ . From the definition of k, we conclude that if z has a non-zero member, then its index must be odd or lie below $2 m$ . Since we have already ensured that the latter case does not hold, we know that z either has no non-zero member or only at an odd position. In both cases, $0$ is a correct solution. The argument for output $1$ , which entails $l = 1$ , works analogously.

This is already enough for the following irreducibility result:

Corollary 3.6.
Both $L P O$ and $L L P O$ are $$ -irreducible (cf. [* 6 , Section 6.2]) with respect to continuous Weihrauch degrees: Let f and g be problems such that the equality $L P O \equiv_{W}^{} f g$ holds. Then, we have $L P O \equiv_{W}^{} f$ or $L P O \equiv_{W}^{} g$ . The statement also holds true if we replace $L P O$ with $L L P O$ .
Proof.
Assume, for contradiction, that f and g are both 1-weakly continuous (2-weakly continuous). Then, by Lemma 3.3, the degree $f * g$ and, therefore, $L P O$ ( $L L P O$ ) must also be 1-weakly continuous (2-weakly continuous), which disagrees with Lemma 3.2. Thus, one of f or g must be 1-weakly discontinuous (2-weakly discontinuous). W.l.o.g., assume that this is the case for f. Then, by Lemma 3.4 (Lemma 3.5), we derive $L P O ⩽_{W}^{} f$ ( $L L P O ⩽_{W}^{} f$ ). Together with $f ⩽_{W}^{} f g$ and $f * g ⩽_{W}^{} L P O$ ( $f g ⩽_{W}^{} L L P O$ ), this yields our claim. Notice that $f ⩽_{W}^{} f * g$ holds since, by $L P O ⩽_{W}^{} f g$ ( $L L P O ⩽_{W}^{} f g$ ), the problem g must have a non-empty domain.
Lemma 3.7.
Let f be a problem and $h, k :\subseteq N^{N} \to N^{N}$ two continuous functions. Then, we have the reduction $h \circ f \circ k ⩽_{W}^{} f$ .
Proof.
The proof works like that of Lemma 2.5 if we replace the term “computable” with “continuous”.
Lemma 3.8.
Let* $f_{1}, f_{2}, g_{1}, g_{2} :\subseteq N^{N} ⇉ N^{N}$ be problems satisfying $f_{1} ⩽_{W}^{} g_{1}$ and* $f_{2} ⩽_{W}^{} g_{2}$ . Then, we have* $f_{1} * f_{2} ⩽_{W}^{} g_{1} g_{2}$ .

In order to prove this lemma (and also to state some later results), we introduce some common constructions of problems (cf. [2, Definition 2.3.1]): Definition 3.9.
Let f and g be problems. We define (i)
$⟨ f, g ⟩ :\subseteq N^{N} ⇉ N^{N}$ with $d o m (⟨ f, g ⟩) := d o m (f) \cap d o m (g)$ and
$\begin{aligned} ⟨ f, g ⟩ (x) := {⟨ u, v ⟩ ∣ u \in f (x) ~and~ v \in g (x)} . \end{aligned}$

(ii)
$f \times g :\subseteq N^{N} ⇉ N^{N}$ with $d o m (f \times g) := {⟨ x, y ⟩ ∣ x \in d o m (f) ~and~ y \in d o m (g)}$ and
$\begin{aligned} (f \times g) (⟨ x, y ⟩) := {⟨ u, v ⟩ ∣ u \in f (x) ~and~ v \in g (y)} . \end{aligned}$

Given problems f, g, h, and k, we can easily calculate
$\begin{aligned} ⟨ f \circ g, h \circ k ⟩ = (f \times h) \circ ⟨ g, k ⟩ \end{aligned}$
such that even the domains are the same on both sides. Moreover, if a (continuous) Weihrauch reduction $f ⩽_{W} g$ (or $f ⩽_{W}^{*} g$ ) between problems f and g is realized by functions $h, k :\subseteq N^{N} \to N^{N}$ , then we have
$\begin{aligned} f (x) \supseteq (h \circ ⟨ i d, g \circ k ⟩) (x) \end{aligned}$
for all $x \in d o m (f)$ .
Proof of Lemma 3.8. Proof of Lemma 3.8.

W.l.o.g, assume that $f_{1} \circ f_{2} \equiv_{W} f_{1} * f_{2}$ holds. Otherwise, let $f_{1}^{^{'}}$ and $f_{2}^{^{'}}$ be problems with $f_{1}^{^{'}} ⩽_{W} f_{1}$ , $f_{2}^{^{'}} ⩽_{W} f_{2}$ and $f_{1}^{^{'}} \circ f_{2}^{^{'}} \equiv_{W} f_{1} * f_{2}$ and continue with those. At the end, our claim follows from the reduction $f_{1} * f_{2} \equiv_{W} f_{1}^{^{'}} \circ f_{2}^{^{'}} ⩽_{W}^{*} g_{1} * g_{2}$ .

Let $h_{1}$ , $k_{1}$ be the continuous functions that realize the reduction $f_{1} ⩽_{W}^{*} g_{1}$ and let $h_{2}$ , $k_{2}$ be such functions that realize $f_{2} ⩽_{W}^{*} g_{2}$ . Clearly, we have the following by simply using the identity functions as realizers for the Weihrauch reduction:

\begin{aligned} f_{1} \circ f_{2} ⩽_{W} h_{1} \circ ⟨ i d, g_{1} \circ k_{1} ⟩ \circ h_{2} \circ ⟨ i d, g_{2} \circ k_{2} ⟩ \end{aligned}

Now, we expand

⟨ i d, g_{i} \circ k_{i} ⟩

for

i \in {1, 2}

\begin{aligned} = h_{1} \circ (i d \times g_{1}) \circ ⟨ i d, k_{1} ⟩ \circ h_{2} \circ (i d \times g_{2}) \circ ⟨ i d, k_{2} ⟩ \end{aligned}

We define a continuous function

p :\subseteq N^{N} \to N^{N}

with

p = ⟨ i d, k_{1} ⟩ \circ h_{2}

\begin{aligned} = h_{1} \circ (i d \times g_{1}) \circ p \circ (i d \times g_{2}) \circ ⟨ i d, k_{2} ⟩ \end{aligned}

Using Lemma 3.7, we can omit both

h_{1}

and

⟨ i d, k_{2} ⟩

\begin{aligned} ⩽_{W}^{*} (i d \times g_{1}) \circ p \circ (i d \times g_{2}) \end{aligned}

Let

x \in N^{N}

be an oracle that computes p, i.e., let

p^{'} :\subseteq N^{N} \to N^{N}

be computable such that

p = p^{'} \circ ⟨ c_{x}, i d ⟩

holds, where

c_{x}

is the problem that maps everything to x.

\begin{aligned} = (i d \times g_{1}) \circ p^{'} \circ ⟨ c_{x}, i d ⟩ \circ (i d \times g_{2}) \end{aligned}

Some calculation reveals the equality

⟨ c_{x}, i d ⟩ \circ (i d \times g_{2}) = (i d \times (i d \times g_{2})) \circ ⟨ c_{x}, i d ⟩

\begin{aligned} = (i d \times g_{1}) \circ p^{'} \circ (i d \times (i d \times g_{2})) \circ ⟨ c_{x}, i d ⟩ \end{aligned}

We apply Lemma 3.7 for a second time.

\begin{aligned} ⩽_{W}^{*} (i d \times g_{1}) \circ p^{'} \circ (i d \times (i d \times g_{2})) \\ ⩽_{W} g_{1} * i d * g_{2} \equiv_{W} g_{1} * g_{2} \end{aligned}

This yields our claim.

With this lemma, we can show that compositional products for continuous Weihrauch degrees are already given by our current definition:

Corollary 3.10.
For any problems f and g, the continuous Weihrauch degree
$\begin{aligned} {max}_{⩽_{W}^{}} {f^{'} \circ g^{'} ∣ f^{'} ⩽_{W}^{} f ~and~ g^{'} ⩽_{W}^{} g} \end{aligned}$
exists and is equal to the continuous Weihrauch degree associated with* $f * g$ .
Proof.
First, let $f^{'}$ and $g^{'}$ be problems with $f^{'} ⩽_{W} f$ and $g^{'} ⩽_{W} g$ such that $f^{'} \circ g^{'} \equiv_{W} f * g$ holds. Clearly, we have $f^{'} ⩽_{W}^{} f$ and $g^{'} ⩽_{W}^{} g$ and, thus, $f * g$ inhabits the set of problems that we are taking the maximum of. Now, we only have to show that any other problem in this set continuously Weihrauch reduces to $f * g$ : Let $f^{'}$ and $g^{'}$ be problems with $f^{'} ⩽_{W}^{} f$ and $g^{'} ⩽_{W}^{} g$ . By Lemma 3.8, we have $f^{'} \circ g^{'} ⩽_{W} f^{'} * g^{'} ⩽_{W}^{} f g$ .

The final ingredients for the proof of our theorem are that, even in the context of continuous Weihrauch degrees, both $L P O * L P O$ and $L L P O * L L P O$ are strictly stronger than $L P O$ and $L L P O$ , respectively.
Lemma 3.11.
(i)
$L P O * L P O$ is not continuously Weihrauch reducible to $L P O$ .
(ii)
$L L P O * L L P O$ is not continuously Weihrauch reducible to $L L P O$ .

These essentially follow from [16, Theorem 3.8 and Theorem 5.4.2]. In order to stay self-contained, let us quickly prove them ourselves. They are almost immediate from the following slightly stronger result:
Lemma 3.12.
$L L P O \times L L P O$ is not continuously Weihrauch reducible to $L P O$ .
Proof.
Let $h, k :\subseteq N^{N} \to N^{N}$ be partial continuous functions that realize the reduction $L L P O \times L L P O ⩽_{W}^{*} L P O$ . Moreover, let $(y_{n})_{n \in N} \subseteq N^{N}$ be a list of sequences where $y_{n}$ only consists of zeros except for the value at index n, for any $n \in N$ . First, we show that there is an $n \in N$ such that $x_{n} := k (⟨ y_{n}, 0 ⟩)$ has a zero. Assume, for contradiction, that this is not the case. If the sequence $k (⟨ 0, 0 ⟩)$ has a zero, then it is clear by continuity of k that such an n exists. Otherwise, $L P O$ must reply with the solution $1$ for this instance, and h produces $b_{1}, b_{2} \in {0, 1}$ with $⟨ b_{1}, b_{2} ⟩ = h (⟨ ⟨ 0, 0 ⟩, 1 ⟩)$ . W.l.o.g., assume that $b_{1}$ is equal to $0$ . Then, by continuity of h and the assumption that h always produces valid solutions for $L L P O \times L L P O$ , there must exist some $n \in N$ such that $⟨ b_{1}, b_{2} ⟩ = h (⟨ ⟨ y_{2 n}, 0 ⟩, 1 ⟩)$ holds. However, $b_{1} = 0$ is not a valid solution for the instance $y_{2 n}$ of $L L P O$ . Thus, $1$ must not be a valid solution for the instance $x_{2 n} = k (⟨ y_{2 n}, 0 ⟩)$ of $L P O$ . We conclude that $x_{2 n}$ must have a zero. The argument for $b_{1} = 1$ works analogously by simply using $y_{2 n + 1}$ instead of $y_{2 n}$ .

Let $n \in N$ be such that $x_{n}$ has a zero. Now, we consider $(z_{m})_{m \in N} \subseteq N^{N}$ with $z_{m} := k (⟨ y_{n}, y_{m} ⟩)$ for any $m \in N$ . Similar to before, let $b_{1}, b_{2} \in {0, 1}$ be such that $⟨ b_{1}, b_{2} ⟩ = h (⟨ ⟨ y_{n}, 0 ⟩, 0 ⟩)$ holds. Notice that the solution for $x_{n}$ of $L P O$ must be $0$ since $x_{n}$ contains a zero. W.l.o.g., assume that $b_{2}$ is equal to $0$ . Now, by continuity of both k and h, there must be some $m \in N$ such that both $z_{2 m}$ has a zero (because of $lim_{m \to \infty} z_{m} = x_{n}$ ) and $⟨ b_{1}, b_{2} ⟩ = h (⟨ ⟨ y_{n}, y_{2 m} ⟩, 0 ⟩)$ holds. Since $z_{2 m}$ has a zero, $0$ is still the valid solution for the instance $z_{2 m}$ of $L P O$ . But now, the reducibility tells us that $b_{2} = 0$ is a correct solution for the instance $y_{2 m}$ of $L L P O$ . This leads to a contradiction. The argument for $b_{2} = 1$ works analogously by using $z_{2 m + 1}$ instead of $z_{2 m}$ .

Now, we can prove the previous lemma:
Proof of Lemma 3.11. Proof of Lemma 3.11.

It is a classical result that $L L P O ⩽_{W} L P O$ holds (cf. [16, Theorem 4.2]), which we can quickly verify: Let $k : N^{N} \to N^{N}$ be some computable function that maps any instance $x \in N^{N}$ of $L L P O$ to $k (x) \in N^{N}$ with $k (x) (n) = 0$ if and only if $x (n) \neq 0$ . If $L P O$ tells us that $k (x)$ has a zero, then x has a non-zero member. Thus, we can simply search for it and determine whether all even positions (or odd positions) in x are zeros. Otherwise, if $L P O$ tells us that $k (x)$ does not have a zero, then $x = 0$ must hold and any of $0$ or $1$ is a valid solution for $L L P O$ of x.

Under any of the assumptions $L P O * L P O ⩽_{W}^{*} L P O$ or $L L P O * L L P O ⩽_{W}^{*} L L P O$ , we can use the previous paragraph and Lemma 3.8 in order to derive $L L P O * L L P O ⩽_{W}^{*} L P O$ . Thus, we have (cf. [4, Lemma 4.3])

\begin{aligned} L L P O \times L L P O ⩽_{W} (i d \times L L P O) \circ (L L P O \times i d) ⩽_{W} L L P O * L L P O ⩽_{W}^{*} L P O . \end{aligned}

Now, we simply invoke Lemma 3.12 and derive a contradiction.

With the previous results and Corollary 3.6, we can already infer that $L P O$ and $L L P O$ do not have square roots. Moreover, together with the obvious reductions $L P O ⩽_{W} L P O * L P O$ and $L L P O ⩽_{W} L L P O * L L P O$ , Theorem 1.7 follows from the following slightly more general result:

Theorem 3.13.
Given a number $n ⩾ 2$ , any problem f with (i)
$L P O ⩽_{W}^{} f <_{W}^{} {L P O}^{[n]}$ or
(ii)
$L L P O ⩽_{W}^{} f <_{W}^{} {L L P O}^{[n]}$
does not have m-th roots for $m ⩾ n$ .

In order to derive Theorem 1.7 from this, use $n := 2$ together with $f := L P O$ or $f := L L P O$ .
Proof.
Assume that $L P O ⩽_{W}^{} f <_{W}^{} {L P O}^{[n]}$ holds and that f has an m-th root r. Now, assume for contradiction that r is 1-weakly continuous. Inductively, we can show that $r^{[i]}$ is 1-weakly continuous for any $i ⩾ 1$ . For the induction step, let $g ⩽_{W} r$ and $h ⩽_{W} r^{[i]}$ be such that $g \circ h$ has degree $r^{[i + 1]}$ . Since r and $r^{[i]}$ are 1-weakly continuous, Lemma 3.3 transfers this to g and h and, hence, to $g \circ h$ and $r^{[i + 1]}$ . By the same lemma, we know that f must be 1-weakly discontinuous since $L P O$ has this property by Lemma 3.2. Finally, for $i := m$ , this leads to a contradiction.

Now, by Lemma 3.4, we have $L P O ⩽_{W}^{} r$ and, therefore, Lemma 3.8 yields ${L P O}^{[m]} ⩽_{W}^{} r^{[m]} \equiv_{W} f$ . Now, by assumption, this entails ${L P O}^{[m]} ⩽_{W}^{} f <_{W}^{} {L P O}^{[n]}$ . Since $m ⩾ n$ holds, this is a contradiction.

The argument for $L L P O$ is the same, we simply have to replace “1-weakly continuous” and “Lemma 3.4” by “2-weakly continuous” and “Lemma 3.5”, respectively.

The proof of Theorem 3.13 can be used to prove the second part of Theorem 1.6:
Proof of Theorem 1.6, second part. Proof of Theorem 1.6, second part.

Consider problems $L P O \times {d e g}_{a}$ for non-zero Turing degrees a, where ${d e g}_{a}$ is the constant multi-valued function that maps everything to all number sequences of degree greater than or equal to a. Using a simple argument (similar to that of Lemma 2.2), we can see that the map $a \mapsto L P O \times {d e g}_{a}$ is an embedding from the Turing degrees into the Weihrauch degrees. Then, by Theorem 3.13, we can see that no such problem has n-th roots for $n ⩾ 2$ .

Still, the proof from the previous section is much simpler and the considered problems $w_{a}$ have another interesting property: While they do not have roots in the Weihrauch lattice, they do have roots in the continuous Weihrauch lattice. For this, we prove $w_{a} \equiv_{W}^{*} i d$ . The direction $i d ⩽_{W}^{*} w_{a}$ is trivial and for non-zero a, the reduction $w_{a} ⩽_{W}^{*} i d$ is realized by continuous functions h and k with $h := c_{x}$ for a number sequence x of Turing degree a and $k := i d$ . For $w_{0} ⩽_{W}^{*} i d$ , the construction is similar: Choose $h := c_{x}$ for some arbitrary non-computable x. Clearly, $i d$ is its own n-th root for $n ⩾ 2$ . Thus, $w_{a}$ has all roots in the continuous Weihrauch lattice, in contrast to $L P O \times {d e g}_{a}$ .

4. Finitely many compositions of $L P O$

In this section, we want to prove Theorem 1.8. An important ingredient for this result is the following theorem:

Theorem 4.1.
For any $n \in N$ , we have ${L P O}^{[n]} <_{W} {L P O}^{[n + 1]}$ . The same result holds if we replace $<_{W}$ with $<_{W}^{}$ .

This theorem seems to be folklore. However, to the best of our knowledge, a proof of this result does not appear in literature, yet. There are several different ways to derive this theorem. Some of them might be more straightforward than our presentation, depending on one’s individual background in the field of Weihrauch reducibility. We will have a short discussion at the end of this section.
Definition 4.2.
Given a natural number $n \in N$ , we say that a Weihrauch problem $f :\subseteq N^{N} ⇉ N^{N}$ has at most n-many solutions, if there is a set $S \subset N^{N}$ of exactly n-many elements such that any solution for any instance of f lies in S.

As a first observation, we may note that $L P O$ has two (“2-many”) solutions.
Lemma 4.3.
Let* $f_{1}, f_{2}, g_{1}, g_{2} :\subseteq N^{N} ⇉ N^{N}$ be problems satisfying $f_{1} ⩽_{W}^{} g_{1}$ and* $f_{2} ⩽_{W}^{} g_{2}$ such that* $g_{1}$ and $g_{2}$ have at most m-many and n-many solutions, respectively. Then, there exists a problem $g :\subseteq N^{N} ⇉ N^{N}$ with at most $m n$ -many solutions such that $f_{1} * f_{2} ⩽_{W}^{} g$ holds.*

In the presence of $f_{1} ⋆ f_{2}$ , i.e. the witness of $f_{1} * f_{2}$ discussed in [6, Section 3], this lemma becomes trivial (and can be stated in a more direct way). However, in this article our goal is to prove all results using only the abstract definition of $f_{1} * f_{2}$ :
Proof of Lemma 4.3. Proof of Lemma 4.3.

Let $h_{1}, k_{1} :\subseteq N^{N} \to N^{N}$ realize the reduction $f_{1} ⩽_{W}^{*} g_{1}$ and let $h_{2}, k_{2} :\subseteq N^{N} \to N^{N}$ realize $f_{2} ⩽_{W}^{*} g_{2}$ . W.l.o.g., we can assume that $f_{1} \circ f_{2}$ already witnesses the degree $f_{1} * f_{2}$ . We define the problem g with $d o m (g) := d o m (f_{1} \circ f_{2})$ and

\begin{aligned} g (x) := {⟨ u, v ⟩ ∣ u \in (g_{2} \circ k_{2}) (x) ~and~ v \in (g_{1} \circ k_{1} \circ h_{2}) (⟨ x, u ⟩)} . \end{aligned}

First, we see that g has at most

m n

-many solutions since each such solution is a pair

⟨ u, v ⟩

of a solution u for

g_{2}

together with a solution v for

g_{1}

. Moreover, using the assumptions on our realizers, we know that any

x \in d o m (g) = d o m (f_{1} \circ f_{2})

is an instance of

g_{2} \circ k_{2}

and given any solution

u \in (g_{2} \circ k_{2}) (x)

, the pair

⟨ x, u ⟩

is an instance of

g_{1} \circ k_{1} \circ h_{2}

. Thus, our definition is well-defined. Finally, we prove that there are (continuous) functions

h, k :\subseteq N^{N} \to N^{N}

that realize the reduction

f_{1} \circ f_{2} ⩽_{W}^{*} g

Let h be given by $h (⟨ x, ⟨ u, v ⟩ ⟩) := h_{1} (⟨ h_{2} (⟨ x, u ⟩), v ⟩)$ and let k simply be the identity function. Let $x \in d o m (f_{1} \circ f_{2})$ be arbitrary. By definition, we know that $x = k (x)$ is also in the domain of g. Now, let $⟨ u, v ⟩$ be a solution for the instance x of g. Then, $h (⟨ x, ⟨ u, v ⟩ ⟩)$ is, by definition, a solution for the instance $h_{2} (⟨ x, u ⟩)$ of $f_{1}$ , which is a solution for the instance x of $f_{2}$ . Thus, we conclude $h (⟨ x, ⟨ u, v ⟩ ⟩) \in (f_{1} \circ f_{2}) (x)$ .

Lemma 4.4.
Let ${L P O}^{n}$ denote the combination of n-many copies of $L P O$ using the ×-operator. For any $n, m \in N$ , if there is a problem $f :\subseteq N^{N} ⇉ N^{N}$ with at most $(m + 1)$ -many solutions and ${L P O}^{n + 1} ⩽_{W}^{} f$ , then we can construct a problem* $g :\subseteq N^{N} ⇉ N^{N}$ with at most m-many solutions satisfying ${L P O}^{n} ⩽_{W}^{} g$ .
Proof.
The continuous Weihrauch reduction yields partial continuous functions $h_{0}, \dots, h_{n} :\subseteq N^{N} \to N^{N}$ and $k :\subseteq N^{N} \to N^{N}$ such that the following holds: For any instances $x_{0}$ , …, $x_{n}$ of $L P O$ , we produce an instance $k (⟨ x_{0}, \dots, x_{n} ⟩)$ of f such that any solution y for this instance yields solutions $h_{0} (⟨ x_{0}, \dots, x_{n}, y ⟩)$ , …, $h_{n} (⟨ x_{0}, \dots, x_{n}, y ⟩)$ for $x_{0}, \dots, x_{n}$ of ${L P O}^{n + 1}$ .

Let y be some solution of f for the instance $k (⟨ 1, \dots, 1 ⟩)$ . Assume that for all $i \in N$ our y is a solution of f for the instance $k (⟨ x_{0}, \dots, x_{n} ⟩)$ for some sequences $x_{0}$ , …, $x_{n}$ that begin with i-many ones such that $x_{0}$ contains a zero. Thus, for any $i \in N$ and such sequences $x_{0}$ , …, $x_{n}$ , we have $h_{0} (⟨ x_{0}, \dots, x_{n}, y ⟩) = 0$ . By continuity of $h_{0}$ , this leads to $h_{0} (⟨ 1, \dots, 1, y ⟩) = 0$ , which cannot be. We conclude that there is some $i \in N$ such that y is no solution of f for any instance $k (⟨ x_{0}, \dots, x_{n} ⟩)$ with sequences $x_{0}$ , …, $x_{n}$ that begin with i-many ones where $x_{0}$ contains a zero.

Let us fix some $x_{0}$ with this property and write $1_{i}$ for the finite sequence of length i that only contains ones. We define $g :\subseteq N^{N} ⇉ N^{N}$ to be the problem with
$\begin{aligned} g (⟨ x_{1}, \dots, x_{n} ⟩) := f (k (⟨ x_{0}, 1_{i} x_{1}, \dots, 1_{i} * x_{n} ⟩)) \end{aligned}$
for all sequences $x_{1}$ , …, $x_{n}$ in $N^{N}$ . By construction, it is immediately clear that y is no solution for any instance of g. Thus, g has at most m-many solutions. Let $x_{1}$ , …, $x_{n}$ be an arbitrary instance of ${L P O}^{n}$ . Of course, $x_{0}$ , $1_{i} * x_{1}$ , …, $1_{i} * x_{n}$ are an instance of ${L P O}^{n + 1}$ . Thus, $g (⟨ x_{1}, \dots, x_{n} ⟩)$ has a solution. Let z be such a solution. Then $h_{1} (⟨ x_{0}, 1_{i} * x_{1}, \dots, 1_{i} * x_{n}, z ⟩)$ , …, $h_{n} (⟨ x_{0}, 1_{i} * x_{1}, \dots, 1_{i} * x_{n}, z ⟩)$ , by definition of g, are equal to $L P O (1_{i} * x_{1})$ , …, $L P O (1_{i} * x_{n})$ , respectively. For each index j with $1 ⩽ j ⩽ n$ , it is clear that $x_{j}$ contains a zero if and only if $1_{i} * x_{j}$ does. Hence, we have $L P O (x_{j}) = L P O (1_{i} * x_{j})$ for any such index j and, finally, our solution of ${L P O}^{n}$ for $x_{1}$ , …, $x_{n}$ . We conclude that ${L P O}^{n} ⩽_{W}^{} g$ holds.
Corollary 4.5.
For every* $n \in N$ , there is no problem $f :\subseteq N^{N} ⇉ N^{N}$ with at most n-many solutions such that ${L P O}^{n} ⩽_{W}^{} f$ holds.*
Proof.
By applying Lemma 4.4 inductively, this yields a problem $f :\subseteq N^{N} ⇉ N^{N}$ with no solution, and therefore no instance, satisfying $i d ⩽_{W}^{*} f$ , which cannot be.

Now, we have all required ingredients for our proof of Theorem 4.1:
Proof of Theorem 4.1. Proof of Theorem 4.1.

Assume for contradiction that there is some $n \in N$ such that ${L P O}^{[n]} <_{W} {L P O}^{[n + 1]}$ or ${L P O}^{[n]} <_{W}^{*} {L P O}^{[n + 1]}$ does not hold. In this case, we have ${L P O}^{[n]} \equiv_{W}^{*} {L P O}^{[n + 1]}$ . Moreover, by composing with m-many copies of $L P O$ , we get ${L P O}^{[n + m]} \equiv_{W}^{*} {L P O}^{[n + m + 1]}$ . Thus, we have ${L P O}^{[n]} \equiv_{W}^{*} {L P O}^{[m]}$ for any $m > n$ .

By Lemma 4.3, we know that there exists some problem $g :\subseteq N^{N} ⇉ N^{N}$ with at most $2^{n}$ -many solutions such that ${L P O}^{[n]} ⩽_{W}^{*} g$ holds. By our assumption on n, this entails ${L P O}^{[2^{n}]} ⩽_{W}^{*} g$ . A simple induction (cf. [4, Lemma 4.3]) reveals that ${L P O}^{m} ⩽_{W} {L P O}^{[m]}$ holds for any $m \in N$ . Thus, we conclude ${L P O}^{2^{n}} ⩽_{W}^{*} g$ . However, by Corollary 4.5, a problem g with at most $2^{n}$ -many solutions satisfying this relation cannot exist. Therefore, our assumption must have been wrong and both ${L P O}^{[n]} <_{W} {L P O}^{[n + 1]}$ and ${L P O}^{[n]} <_{W}^{*} {L P O}^{[n + 1]}$ must hold for all $n \in N$ .

Finally, we can use this result in order to prove Theorem 1.8:

Proof of Theorem 1.8. Proof of Theorem 1.8.

Let $m ⩾ 2$ . We apply Theorem 3.13 for $f := {L P O}^{[m]}$ and $n := m + 1$ . By Theorem 4.1, we know that this a valid instance since the reductions $L P O ⩽_{W}^{*} {L P O}^{[m]} <_{W}^{*} {L P O}^{[m + 1]}$ hold. Now, we conclude that ${L P O}^{[m]}$ does not have an $(m + 1)$ -th root. However, it clearly has an m-th root.

As already claimed at the beginning of this section, there are multiple different ways to prove Theorem 4.1. For instance, instead of introducing the notion of “at most n-many solutions”, we could have used the notion of n-continuity (cf. [16, Definition 3.3]). With this, we could have shown that ${L P O}^{[n]}$ is $2^{n}$ -continuous and ${L P O}^{n}$ is not n-continuous, for all $n \in N$ . The final arguments of this proof would be similar to ours.

Also, as noted by Giovanni Soldà and one of the referees, ${L P O}^{[n]} \equiv_{W} {L P O}^{[n + 1]}$ for some $n \in N$ leads to ${L P O}^{[n]} \equiv_{W} {L P O}^{⋄}$ (cf. [17, Theorem 1]), for a certain problem ${L P O}^{⋄}$ . Combining this with ${L P O}^{⋄} \equiv_{W} C_{N}$ (cf. [11, Proposition 10]) leads to a contradiction as $C_{N}$ cannot continuously reduce to a problem that has at most k-many solutions for some $k \in N$ (cf. [15, Theorem 2.1]). Adapting these steps to the continuous Weihrauch lattice should yield another proof of Theorem 4.1.

Footnotes

Acknowledgements

I would like to thank Arno Pauly and Giovanni Soldà for our correspondence, and the referees for their many helpful remarks and insights. Also, I would like to thank Nicholas Pischke without whom some of these results would still be in some drawer.

The author is funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – Project number 460597863.

Notes

References

Bishop

Bridges

, Constructive Analysis, Springer-Verlag, Berlin, Heidelberg, 1985. ISBN 978-3-642-61667-9. doi:10.1007/978-3-642-61667-9.

Brattka

, Recursive and computable operations over topological structures, PhD thesis, Department of Computer Science, University of Hagen, Hagen, Germany, 1998.

Brattka

Gherardi

, Weihrauch degrees, omniscience principles and weak computability, The Journal of Symbolic Logic 76(1) (2011), 143–176. doi:10.2178/jsl/1294170993.

Brattka

Gherardi

Marcone

, The Bolzano–Weierstrass theorem is the jump of weak Kőnig’s lemma, Annals of Pure and Applied Logic 163(6) (2012), 623–655, Computability in Europe 2010. doi:10.1016/j.apal.2011.10.006.

Brattka

Gherardi

Pauly

, Weihrauch complexity in computable analysis, in: Handbook of Computability and Complexity in Analysis, Brattka

Hertling

, eds, Springer International Publishing, Cham, 2021, pp. 367–417. ISBN 978-3-030-59234-9. doi:10.1007/978-3-030-59234-9_11.

Brattka

Pauly

, On the algebraic structure of Weihrauch degrees, Logical Methods in Computer Science 14 (2018), 1–36. doi:10.23638/LMCS-14(4:4)2018.

Bridges

Richman

, Varieties of Constructive Mathematics, London Mathematical Society Lecture Note Series, Cambridge University Press, 1987. doi:10.1017/CBO9780511565663.

Higuchi

Pauly

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

Kleene

S.C.

Post

E.L.

, The upper semi-lattice of degrees of recursive unsolvability, Ann. of Math. (2) 59 (1954), 379–407. doi:10.2307/1969708.

10.

Kreitz

Weihrauch

, Theory of representations, Theoretical Computer Science 38 (1985), 35–53. doi:10.1016/0304-3975(85)90208-7.

11.

Neumann

Pauly

, A topological view on algebraic computation models, J. Complexity 44 (2018), 1–22. doi:10.1016/j.jco.2017.08.003.

12.

Pauly

, On the (semi)lattices induced by continuous reducibilities, Mathematical Logic Quarterly 56(5) (2010), 488–502. doi:10.1002/malq.200910104.

13.

Pauly

, An update on Weihrauch complexity, and some open questions, 2020, arXiv:2008.11168. doi:10.48550/arXiv.2008.11168.

14.

Shoenfield

J.R.

, An uncountable set of incomparable degrees, Proc. Amer. Math. Soc. 11 (1960), 61–62. doi:10.2307/2032716.

15.

Soldà

Valenti

, Algebraic properties of the first-order part of a problem, Ann. Pure Appl. Logic 174(7) (2023), 1–41. Paper no. 103270. doi:10.1016/j.apal.2023.103270.

16.

Weihrauch

, The TTE-Interpretation of Three Hierarchies of Omniscience Principles, Informatik Berichte, Vol. 130, FernUniversität Hagen, Hagen, 1992.

17.

Westrick

, A note on the diamond operator, Computability 10(2) (2021), 107–110. doi:10.3233/COM-200295.

Weihrauch degrees without roots

Abstract

Keywords

1. Introduction

3. Using continuity

Lemma 3.5. Let f be a problem. Then, f is 2 -weakly discontinuous if and only if we have L L P O ⩽ W * f . Again, this suggests a close connection to Weihrauch’s notion of 2-continuous. Proof of Lemma 3.5. Proof of Lemma 3.5.

4. Finitely many compositions of L P O

Proof of Theorem 1.8. Proof of Theorem 1.8.

Footnotes

Acknowledgements

Notes

References

Lemma 3.5.
Let f be a problem. Then, f is 2 -weakly discontinuous if and only if we have $L L P O ⩽_{W}^{*} f$ .

Again, this suggests a close connection to Weihrauch’s notion of 2-continuous.
Proof of Lemma 3.5. Proof of Lemma 3.5.

4. Finitely many compositions of $L P O$