Projection operators in the Weihrauch lattice

Abstract

In this paper we study, for $n ⩾ 1$ , the projection operators over $R^{n}$ , that is the multi-valued functions that associate to $x \in R^{n}$ and $A \subseteq R^{n}$ closed, the points of A which are closest to x. We also deal with approximate projections, where we content ourselves with points of A which are almost the closest to x. We use the tools of Weihrauch reducibility to classify these operators depending on the representation of A and the dimension n. It turns out that, depending on the representation of the closed sets and the dimension of the space, the projection and approximate projection operators characterize some of the most fundamental computational classes in the Weihrauch lattice.

Keywords

Projection operators computable analysis Weihrauch degrees

1. Introduction

Projecting a point over a non-empty subset of a Euclidean space is an operation deeply grounded in our geometrical intuition of the spatial continuum and has many important applications in higher mathematics. More precisely, given $x \in R^{n}$ and $A \subseteq R^{n}$ we seek $y \in A$ such that $d (x, y) = d (x, A)$ (when A is closed, such a y does exist, although it might not be unique). In this paper we show that the intuitive, even empirical, naturalness of this problem leads to multi-valued function realizing some well-known levels of incomputability.

We work in the Weihrauch lattice, which has become a widespread tool to classify the level of incomputability of mathematical problems from several branches of classical mathematics since [16]. Intuitively, given two (multi-valued) functions f and g on represented spaces, f is Weihrauch reducible to g if f can be computed by g, with computable translations from $dom (f)$ to $dom (g)$ , and, viceversa, from $range (g)$ to $range (f)$ , allowed. (More details are in §2.2 below.)

Recall that in this approach mathematical objects are encoded by sequences of infinite length whose information is based on the topological properties of the underlying spaces. For example, $x \in R^{n}$ (for a fixed $n ⩾ 1$ ) is naturally represented by an effective Cauchy sequence in $Q^{n}$ converging to x. But if we want to project x onto a subset of $R^{n}$ we of course also need a suitable encoding for the set. We focus our investigation on closed sets (although we will also mention the special case of compact sets) and their standard topologies. The so-called negative representation for closed sets is based on the lower Fell topology $A_{-} (R^{n})$ and consists in enumerating an open cover of the complement. In contrast, their positive representation is based on the upper Fell topology $A_{+} (R^{n})$ and consists, for nonempty closed sets, in enumerating dense sequences of points in them. Finally, the total representation, corresponding to the Fell topology, is obtained by combining both kinds of information ([27]). More details about these representations will be given in §2.1 below. We thus obtain different projection operators, depending on the representation chosen for the closed set.

In the literature ([3,20]) it has been proved that the projection operators, for some metric spaces and closed sets with optimal conditions (such as convexity, boundedness of A, uniqueness of the solution) are computable. But what happens when such optimal conditions fail? It is not surprising that the problem is then no longer computably solvable for any of the above mentioned representations on closed sets, so the goal becomes the classification, depending on the type of information involved, of the corresponding degrees of incomputability in the Weihrauch lattice.

In many concrete applications one may be content already with approximations of arbitrarily accurate precision. In other words, we investigate the computational complexity of operators selecting points $y \in A$ such that $d (x, y) ⩽ (1 + ε) d (x, A)$ for some fixed $ε > 0$ . Intuitively, we expect that the loss of accuracy results in a simpler computational complexity. We indeed prove that these operators are simpler than their exact counterparts, but still not computable for negative and positive representations of closed sets. In contrast, the approximate projection operators with total information are computable.

Table 1 summarizes our main results. Quite surprisingly, it turns out that in most cases the (approximate) projection operators are Weihrauch complete with respect to some fundamental computational class which is represented in the last column by its emblematic representative, already studied in the literature, and defined in §2.3 below. In other words, the notion of projection allows us, by varying the kind of projection, the representation of the closed sets, and the dimension of the space, to characterize some of the most fundamental degrees in the Weihrauch lattice. In all cases, we obtain a characterization in terms of previously studied Weihrauch degrees.

Table 1
Summary of main results: The first column indicates the kind of projection, the second column the representation of the closed sets, the third one the dimension of the Euclidean space $R^{n}$ , the fourth one our results, and the last one the references to the results in this paper where the results are proved

Proj. Repr. Dim. Weihrauch degree Reference

Exact negative $n = 1$ $\equiv_{W} {BWT}_{2} \times lim$ Corollary 4.13

$n ⩾ 2$ $\equiv_{W} {BWT}_{R}$ Corollary 4.9

positive $n = 1$ $\equiv_{W} {BWT}_{2} \times lim$ Corollary 4.18

$n ⩾ 2$ $\equiv_{W} {BWT}_{R}$ Corollary 4.15

total $n = 1$ $\equiv_{W} LLPO$ Corollary 4.21

$n ⩾ 2$ $\equiv_{W} WKL$ Corollary 4.23

Approx. negative $n ⩾ 1$ $\equiv_{W} C_{R}$ Theorem 5.4

positive $n ⩾ 1$ $\equiv_{W} Sort$ Corollary 5.8

total $n ⩾ 1$ computable Theorem 5.10

Proj.	Repr.	Dim.	Weihrauch degree	Reference
Exact	negative	$n = 1$	$\equiv_{W} {BWT}_{2} \times lim$	Corollary 4.13

$n ⩾ 2$	$\equiv_{W} {BWT}_{R}$	Corollary 4.9

positive	$n = 1$	$\equiv_{W} {BWT}_{2} \times lim$	Corollary 4.18

$n ⩾ 2$	$\equiv_{W} {BWT}_{R}$	Corollary 4.15

total	$n = 1$	$\equiv_{W} LLPO$	Corollary 4.21

$n ⩾ 2$	$\equiv_{W} WKL$	Corollary 4.23
Approx.	negative	$n ⩾ 1$	$\equiv_{W} C_{R}$	Theorem 5.4

positive	$n ⩾ 1$	$\equiv_{W} Sort$	Corollary 5.8

total	$n ⩾ 1$	computable	Theorem 5.10

It is also remarkable that, as far as exact projections are concerned, negative or positive information for closed sets can be used interchangeably, as this has no effect in the classification obtained with respect to any given dimension $n ⩾ 1$ . The difference between negative and positive information only arises when approximations are allowed. Here, the relevant degrees are even incomparable (Corollary 5.9).

To see that the approximate projections are of practical importance we suggest a concrete application, which is actually the original motivation for our research. The Whitney Extension Theorem was originally proved in [31] and, roughly speaking, generalizes the well-known Urysohn-Tietze Extension Lemma to the case of differentiable functions. An expository paper on modern developments concerning the Whitney Extension Theorem and its generalizations is [15]. By using approximate projections in place of the exact ones originally used in the proof of the Whitney Extension Theorem as exposed in the classical textbook [28],1

Stein himself suggests on p.172 the possibility of using approximate projections, although our use probably is not the one he was foreseeing.

we sketch the computability of this theorem. Full details of this result are postponed to a forthcoming paper [17].

We now explain the organization of the paper. In Section 2 we give a brief introduction to computable analysis, introduce the representations we will be using throughout the paper, and recall Weihrauch reducibility and some milestones in the Weihrauch lattice. Section 3 provides a new characterization of the Weihrauch degree of the function Sort, introduced by Neumann and Pauly ([21]). Sections 4 and 5 are the core of the paper and are devoted respectively to the exact and approximated projection operators: after defining them we prove the results summarized in Table 1. In Section 6 we briefly sketch the application of approximate projections to the Whitney Extension Theorem.

2. Computable analysis: Notation and terminology

This Section recalls basic definitions and terminology of computable analysis and of Weihrauch reducibilities (see [11] for a self-contained introduction to the subject). The reader familiar with the topics can safely skip it and refer back to this section as needed.

We work in the framework is the so called Type-2 Theory of Effectivity (TTE), which finds a systematic foundation in [30] and provides a realistic and flexible model of computation. The salient features of TTE Turing machines are that they work on infinite sequences of bits and that no correction is allowed on the output. A partial function $F : \subseteq N^{N} \to N^{N}$ is computable if it is in computed by some TTE Turing machine. An immediate consequence of the restraint concerning the output is that all computable functions are continuous.

2.1. Representations

To extend the notion of computability to functions between spaces different from $N^{N}$ we need the notion of representation. Recall that a representation $σ_{X}$ of a set X is a surjective function $σ_{X} : \subseteq N^{N} \to X$ , and in this case we say that the pair $(X, σ_{X})$ is a represented space. If $x \in X$ a $σ_{X}$ -name for x is any $p \in N^{N}$ such that $σ_{X} (p) = x$ . By routine syntactic pairing techniques it is straightforward to obtain representations for finite and countably infinite product of represented spaces.

Given represented spaces $(X, σ_{X})$ and $(Y, σ_{Y})$ and a partial multi-valued function $f : \subseteq X ⇉ Y$ , we say that $F : \subseteq N^{N} \to N^{N}$ is a $(σ_{X}, σ_{Y})$ -realizer of f (and write $F ⊢ f$ ) if $σ_{Y} (F (p)) \in f (σ_{X} (p))$ , for all $p \in dom (f \circ σ_{X})$ . We can now say that a function between represented spaces is computable if it has a computable realizer.

For representations $σ_{X}$ and $σ_{X}^{'}$ of the same set X, we say that $σ_{X}$ is computably reducible to $σ_{X}^{'}$ (we write $σ_{X} ⩽_{c} σ_{X}^{'}$ ) if there is a computable $F : \subseteq N^{N} \to N^{N}$ such that for every $p \in dom (σ_{X})$ we have $σ_{X} (p) = σ_{X}^{'} (F (p))$ . If $σ_{X} ⩽_{c} σ_{X}^{'}$ and $σ_{X}^{'} ⩽_{c} σ_{X}$ , the two representations are computably equivalent ( $σ_{X} \equiv_{c} σ_{X}$ ).

The general notion of representation is too broad for practical purposes. Concretely, representations are associated to the final topologies they induce on the represented space, and usually admissible representations for $T_{0}$ -spaces are considered. Such representations are those that make the use of realizers meaningful: if X and Y are admissibly represented, a single valued $f : \subseteq X \to Y$ is continuous if and only if it admits a continuous realizer $F : \subseteq N^{N} \to N^{N}$ with respect to the Baire topology (see [30] and [25] for introductions to the theory of admissible representations).

An important example is the Cauchy representation which is admissible with respect to the topology of a separable (computable) metric space.

Definition 2.1 (Computable metric spaces).

A computable metric space is a triple $(X, d, α)$ , where d is a metric on X, $α : N \to X$ is a dense sequence in X, and $d \circ (α \times α)$ is a computable double sequence in $R$ . We then represent X by the Cauchy representation $δ_{X} : \subseteq N^{N} \to X$ , defined by $\begin{array}{l} p \in dom (δ_{X}) ⟺ (\forall i) (\forall j ⩾ i) d (α (p (i)), α (p (j))) ⩽ 2^{- i}; \\ δ_{X} (p) = x ⟺ lim_{n \to \infty} α (p (n)) = x . \end{array}$ When $δ_{X} (p) = x$ we say that ${(α (p (i)))}_{i}$ is an effective Cauchy sequence, and that it converges effectively to x.

Notice that with this representation, the metric $d : X \times X \to R$ is computable.

A particularly important example is provided by the Euclidean spaces $R^{n}$ , which are computable metric spaces when we fix a function $α : N \to Q^{n}$ enumerating in an effective way $Q^{n}$ . Here $d : R^{n} \times R^{n} \to R$ is the usual Euclidean metric.

By using the same effective numbering $α : N \to Q$ , there are other ways to represent real numbers, by changing the underlying topology over $R$ . The representation $ρ_{>}$ is given by $ρ_{>} (p) : = x$ iff $n \in range (p) ⟺ α (p (n)) < x$ , and analogously $ρ_{>}$ is given by $ρ_{>} (p) : = x$ iff $n \in range (p) ⟺ α (p (n)) > x$ . These two representations are admissible with respect to the topologies $R_{<}$ and $R_{>}$ whose open sets are of the form $] x, \infty [$ and $] - \infty, x [$ respectively (see [30] for more details).

Given a computable metric space $(X, δ_{X})$ we can effectively enumerate the open balls with center in $range (α)$ and rational radius in an obvious way using a computable pairing function: to $k = ⟨ n, m ⟩ \in N$ we associate the open ball $B_{k} : = B (α (n), q_{m})$ , where ${(q_{m})}_{m}$ is a standard enumeration of the nonnegative rational numbers (notice that $B (α (n), q_{m}) = \emptyset$ when $q_{m} = 0$ ). We call these sets open basic balls. We denote the closed ball ${x \in X : d (α (n), x) ⩽ q_{m}}$ by $\overline{B} (α (n), q_{m})$ or ${\overline{B}}_{k}$ (notice that in general this is not the same as the closure $\overline{B (α (n), q_{m})} = \overline{B_{k}}$ of $B_{k}$ , although in $R^{n}$ they coincide).

Definition 2.2 (Closed set representations).

Let $(X, δ_{X})$ be a computable metric space.

By $A_{-} (X)$ we denote the hyperspace of closed subsets of X equipped with the negative information representation $ψ_{X}^{-} : N^{N} \to {A \subseteq X : A is closed in X}$ such that $\begin{matrix} ψ_{X}^{-} (p) = A ⟺ A = X ∖ ⋃_{i \in range (p)} B_{k_{i}} . \end{matrix}$

By $A_{+} (X)$ we denote the hyperspace of closed subsets of X equipped with the positive information representation $ψ_{X}^{+} : \subseteq N^{N} \to {A \subseteq X : A is closed in X}$ such that $\begin{matrix} ψ^{+} (p) = A ⟺ (\forall i) (i \in range (p) \leftrightarrow B_{k_{i}} \cap A \neq \emptyset) . \end{matrix}$

Finally, by $A (X)$ we denote the hyperspace of closed subsets of X equipped with the total information representation $ψ_{X} = ψ_{X}^{-} \land ψ_{X}^{+}$ , that is $\begin{matrix} ψ_{X} (⟨ p_{0}, p_{1} ⟩) = A ⟺ ψ_{X}^{-} (p_{0}) = ψ_{X}^{+} (p_{1}) = A . \end{matrix}$

It is clear from Definitions 2.1 and 2.2 that we can view A as an element of $A_{-} (X)$ if and only if we can semi-decide whether $x \notin A$ for every $x \in X$ . This means that to show that (a name for) some $A \in A_{-} (X)$ can be computed from some input z it suffices to give a definition of A by a $Π_{1}^{0}$ formula with parameter z.

It is well known that the operations $\cap, \cup : A_{-} (X) \times A_{-} (X) \to A_{-} (X)$ are computable, as well as $\cup : A {(X)}_{+} \times A {(X)}_{+} \to A_{+} (X)$ .

Closed sets with positive information are also known in the literature as overt sets (see [25] for a discussion of nomenclature).

Remark 2.3.
By [13, Theorems 3.7 and 3.8], in every complete computable metric space $(X, δ_{X})$ , the positive information representation for nonempty closed sets is equivalent to the representation which assigns to a name $p : = ⟨ p_{0}, p_{1}, p_{2}, \dots ⟩ \in dom {(δ_{X})}^{N}$ the set $\overline{{δ_{X} (p_{n}) : n \in N}}$ . See also [30, Lemma 5.1.10] for the case $X = R^{n}$ .

As for the negative information, in the Euclidean space this is equivalent to the representation encoding a closed $A \subseteq R^{n}$ by enumerating all k such that $A \cap {\overline{B}}_{k} = \emptyset$ ([30, Lemma 5.1.10]).

We are also interested in representing the space of the compact subsets of a fixed computable metric space.
Definition 2.4 (Compact set representations).

Let $(X, δ_{X})$ be a computable metric space. By $K_{-} (X)$ we denote the hyperspace of compact subsets of X equipped with the negative information representation $κ_{X}^{-} : \subseteq N^{N} \to {K \subseteq X : K is compact in X}$ such that: $\begin{matrix} κ_{X}^{-} (⟨ k_{0}, \dots, k_{j - 1} ⟩ p) = K ⟺ ψ_{X}^{-} (p) = K \land K \subseteq ⋃_{i < j} {\overline{B}}_{k_{i}} \land (\forall i < j) B_{k_{i}} \neq X . \end{matrix}$ Analogously, one defines the hyperspace $K_{+} (X)$ of compact subsets of X equipped with the positive information representation $κ_{X}^{+}$ , and the hyperspace $K (X)$ of compact subsets of X equipped with the total information representation $κ_{X}$ , by replacing $ψ_{X}^{-}$ with $ψ_{X}^{+}$ and $ψ_{X}$ , respectively.

Remark 2.5.
In the case of the Euclidean space $R^{n}$ , the balls $B_{k_{0}}, \dots, B_{k_{j - 1}}$ can be more simply replaced by a single ball $B (0, N)$ , for $N \in N$ , satisfying $K \subseteq \overline{B} (0, N)$ (in agreement with [30, Definition 5.2.1]).

Abstracting from the purely syntactic elements, representations often denote objects by enumerating sequences of objects. Therefore one is often allowed to skip the annoying linguistic aspects by describing the represented element directly through the corresponding sequence of objects. For instance, we see a point x in a metric space directly as $x = {lim}_{i \to \infty} x [i]$ , where, for all i, $x [i] = α (p (i)) \in X$ with respect to some given Cauchy-name p of x. Analogously, we can describe a closed set $A \in A_{-} (X)$ directly as $A : = X ∖ ⋃_{i \in N} B_{i}$ , by meaning that $B_{i}$ (which really should be $B_{k_{i}}$ ) is the i-th rational open ball enumerated by some $ψ_{X}^{-}$ -name of A.
2.2. Weihrauch reducibility

The original definition of Weihrauch reducibility between functions over represented spaces is due to Weihrauch in an unpublished report from 1992, and in the next decade the notion was explored in several thesis by some of Weihrauch’s students. The authors [16] extended Weihrauch reducibility to multi-valued functions. Let $f : \subseteq X ⇉ Y$ and $g : \subseteq Z ⇉ W$ be partial multi-valued functions between represented spaces. We say that f is Weihrauch reducible to g, and write $f ⩽_{W} g$ , if there are computable $H : \subseteq N^{N} \times N^{N} \to N$ and $K : \subseteq N^{N} \to N^{N}$ such that $H (id, G K) ⊢ f$ whenever $G ⊢ g$ (here $id : N^{N} \to N^{N}$ is the identity function on Baire space).

The intuition behind the definition is that $f ⩽_{W} g$ means that the problem of computing f can be computably and uniformly solved by using in each instance a single computation of g: K modifies (each name for) the input of f to feed it to g, while H, using also the original input, transforms (any name for) the output of g into (a name for) the correct output of f. Another characterization of Weihrauch reducibility is provided by the fact that $f ⩽_{W} g$ if and only if there is a Turing machine that computes f using g as an oracle exactly once during its infinite computation [29].

A direct consequence of the definition of Weihrauch reducibility is the following Invariance Principle: $f ⩽_{W} g$ implies that for any given $σ_{X}$ -name p of some $x \in dom (f)$ there is some $y \in f (x)$ with a $σ_{Y}$ -name q such that $q ⩽_{T} p \oplus G K (p)$ (here $⩽_{T}$ denotes the usual Turing reducibility). In other words, $G K (p)$ provides an upper bound for the computational complexity of (some element in) $f (x)$ .

The relation $⩽_{W}$ is reflexive and transitive and induces an equivalence relation denoted by $\equiv_{W}$ . The partial order on the sets of $\equiv_{W}$ -equivalence classes (called Weihrauch degrees) is a distributive bounded lattice [5,23] with several natural and useful algebraic operations [10]. As usual, we use $f <_{W} g$ to denote $f ⩽_{W} g$ and $g ≰_{W} f$ , and $f |_{W} g$ to denote $f ≰_{W} g$ and $g ≰_{W} f$ .

The Weihrauch lattice can be used as a tool for comparing multi-valued functions arising from theorems from different areas of mathematics, once the theorems are translated into mathematical problems on represented spaces. This line of research has blossomed in the last few years [1,2,5–10,14,16,23,24] and this paper contributes to it by classifying the projection operators.

In some cases, one can prove the reducibility of f to g by using a computable K that does not access to the original input, that is, we have $K G H ⊢ f$ whenever $G ⊢ g$ . In this case we say that f is strongly Weihrauch reducible to g and write $f ⩽_{sW} g$ . We then use $\equiv_{sW}$ for the induced equivalence relation.

We notice that $f ⩽_{sW} g ⟹ f ⩽_{W} g$ always hold, whereas $f ⩽_{W} g ⟹ f ⩽_{sW} g$ holds when g is a cylinder, that is $g \equiv_{sW} g \times id$ , where id is the identity function on the Baire space.

2.3. Some milestones in the Weihrauch lattice

Multi-valued functions $f : \subseteq X ⇉ Y$ can be seen as problems: given $x \in dom (f)$ , find a $y \in f (x)$ . The algebraic structure of the Weihrauch lattice can provide a useful tool to determine the computational complexity of fundamental mathematical problems which are not computable, at least in the standard TTE-model. A typical example is to find the derivative $f^{'}$ of a differentiable real function. Other paradigmatic problems are those provided by fundamental theorems of classical mathematics. The idea here is to see a statement of the form $(\forall x \in X) (φ (x) \to (\exists y \in Y) ψ (x, y))$ as defining the multi-valued function $f : \subseteq X ⇉ Y$ with domain ${x \in X : φ (x)}$ and $f (x) = {y \in Y : ψ (x, y)}$ . It turns out that the Weihrauch degree of many mathematical problems can be evaluated with the help of few operators. Relevant for our work are the following:

$LPO : N^{N} \to {0, 1}$ , the computational version of the limited principle of omniscience of constructive mathematics defined by $LPO (p) = 0$ if $p = 0^{N}$ and $LPO (p) = 1$ if $p \neq 0^{N}$ ;

$LLPO : \subseteq N^{N} \times N^{N} ⇉ {0, 1}$ , the computational version of the lesser limited principle of omniscience of constructive mathematics defined by $i \in LLPO (p_{0}, p_{1})$ iff $p_{i} = 0^{N}$ , where for at most one $j \in {0, 1}$ and one $n \in N$ it holds $p_{j} (n) \neq 0$ ;

$WKL : \subseteq Tr ⇉ 2^{N}, T \mapsto [T]$ , the Weak König’s Lemma operator, mapping each infinite binary tree to its infinite paths; here a tree $T \subseteq 2^{< N}$ is represented by its characteristic function $t \in 2^{N}$ , that is, $t (n) = 1$ iff $w_{n} \in T$ for a recursive enumeration $w_{0}, w_{1}, w_{2}, \dots$ of all finite binary words;

$C_{X} : \subseteq A_{-} (X) ⇉ X, A \mapsto A$ , the closed choice operators, selecting members from any given non-empty closed set (encoded by negative information) in a computable metric space X;

$K_{X} : \subseteq K_{-} (X) ⇉ X, K \mapsto K$ , the compact choice operators, selecting members from any given non-empty compact set (encoded by negative information) in a computable metric space X;

$lim : \subseteq {(N^{N})}^{N} \to N^{N}$ , ${(p_{n})}_{n} \to {lim}_{n \to \infty} p_{n}$ , for every convergent sequence ${(p_{n})}_{n}$ in the Baire space;

${BWT}_{X} : \subseteq X^{N} ⇉ X$ , the Bolzano–Weierstraß Theorem operators, that maps every sequence with compact range in a computable metric space X to its accumulation points.

For instance, the problem of finding the derivative $f^{'}$ of f is Weihrauch equivalent to lim. As for $C_{X}$ , $K_{X}$ , and ${BWT}_{X}$ , we obtain very important cases when we set $X = N$ or $X = R$ . For example, the (contrapositive of) the Baire Category Theorem is Weihrauch equivalent to $C_{N}$ . See [11] for a general overview of this program of classification of mathematical problems and for further references.

It is well known that $LLPO \equiv_{sW} C_{2}$ (where $2 = {0, 1}$ ) and $WKL \equiv_{sW} K_{R}$ .

A multi-valued function f is called non deterministically computable if $f ⩽_{W} WKL$ , computable with finitely many mind changes if $f ⩽_{W} C_{N}$ , and limit computable if $f ⩽ lim$ . This terminology arises from the non standard models of computation that make such f computable. For instance, f is computable with finitely many mind changes if it can be computed by a non standard TTE-machine that is allowed to revise the output with the restraint that only finitely many corrections can occur. See [11] for more details and further references.

Some degrees can be seen as the parallelization or composition of other degrees. The parallelization of $\hat{f} : \subseteq X^{N} ⇉ Y^{N}$ of $f : \subseteq X \to Y$ is defined as $\hat{f} ({(x)}_{n}) : = (f {(x)}_{n})$ . We have for example $WKL \equiv_{sW} \hat{LLPO}$ and $lim \equiv_{sW} \hat{LPO}$ . It is known that parallelization is a closure operator, that is $f ⩽_{W} \hat{f}$ , $f ⩽_{W} g \Rightarrow \hat{f} ⩽_{W} \hat{g}$ , and $\hat{\hat{f}} \equiv_{W} \hat{f}$ .

The composition of multi-valued functions is defined so that the range of the first function not necessarily has to be included in the domain of the second function. Intuitively, some computational transformation is allowed so that the two spaces can match. It is easier to define such compositional product as an operation on degrees2

²
The introduction of the compositional product as a specific function is more involved (see [12], [11, Definition 5.3]) and not relevant for this paper.

\begin{matrix} g * f : = max {g_{0} \circ f_{0} : g_{0} ⩽_{W} g, f_{0} ⩽_{W} f} . \end{matrix}

Here the leftmost occurrences of f and g must be understood as denoting the corresponding degrees, and the maximum as a degree defined by the partial order induced on the Weihrauch degrees by

⩽_{W}

. (Notice that the Weihrauch lattice is not complete, but the max above always exists by [12, Corollary 18], [11, Theorem 5.2].) It holds then

\begin{matrix} {BWT}_{R} \equiv_{W} {BWT}_{2^{N}} \equiv_{W} WKL * lim and C_{R} \equiv_{W} WKL * C_{N} \equiv_{W} C_{N} * WKL . \end{matrix}

These equivalences justify the following terminology:

f ⩽_{W} {BWT}_{R}

is said to be non deterministically limit computable and

f ⩽_{W} C_{R}

is said to be non deterministically computable with finitely many mind changes.

Finally, some degrees can be seen as jumps of others. Given a multi-valued function $f : \subseteq X ⇉ Y$ on represented spaces $(X, δ_{X})$ , $(Y, δ_{Y})$ , the jump $f^{'} : \subseteq X ⇉ Y$ of f coincides with f but the representation of X is weakened into the representation $δ_{X}^{'}$ , where $dom (δ_{X}^{'}) : = {⟨ p_{0}, p_{1}, p_{2}, \dots ⟩ \in N^{N} : {lim}_{i \to \infty} p_{i} ↓ \in dom (δ_{X})}$ and $δ_{X}^{'} (⟨ p_{0}, p_{1}, p_{2}, \dots ⟩) = x \in X$ iff $δ_{X} ({lim}_{i \to \infty} p_{i}) = x$ . It holds then ${BWT}_{2} \equiv_{sW} {LLPO}^{'}$ and ${BWT}_{R} \equiv_{sW} {WKL}^{'}$ .

Notice that lim is a cylinder, hence $f ⩽_{sW} lim ⟺ f ⩽_{W} lim$ , and the same holds for WKL and ${BWT}_{R}$ .

3. The functions Sort and

{min}_{ω + 1}^{-}

In [21] Neumann and Pauly introduced the function $Sort : 2^{N} \to 2^{N}$ defined as $\begin{matrix} Sort (p) : = \{\begin{matrix} 0^{n} 1^{N} & if p contains exactly n occurrences of 0 \\ 0^{N} & if p contains infinitely many occurrences of 0 \end{matrix} \end{matrix}$ Our results support the importance of this function, so that one might see it as a candidate for a new possible milestone in the Weihrauch lattice. To this end we first show that Sort is strongly Weihrauch equivalent to another natural function.

Consider the space $\begin{matrix} ω + 1 : = ⋃_{n \in N} {- 2^{- n}} \cup {0} . \end{matrix}$ This space is seen as a subspace of the represented space $R$ , hence its members are represented as real numbers via Cauchy sequences of elements of the dense set of rationals in $ω + 1$ , i.e., $ω + 1$ itself.

It is easy to see that this Cauchy representation $δ_{ω + 1}$ is computably equivalent to the representation $ρ_{ω + 1}$ with $dom (ρ_{ω + 1}) = {p \in N^{N} : (\exists^{⩽ 1} i) p (i) \neq 0}$ and $\begin{matrix} ρ_{ω + 1} (p) = \{\begin{matrix} - 2^{- n} & if p (n) \neq 0; \\ 0 & if (\forall i) p (i) = 0 . \end{matrix} \end{matrix}$ To see that $ρ_{ω + 1} ⩽_{c} δ_{ω + 1}$ , take any $ρ_{ω + 1}$ -name p of $x \in ω + 1$ and consider the Cauchy sequence ${(x_{n})}_{n}$ such that $x_{i} : = 2^{- i}$ if $p (j) = 0$ for all $j ⩽ i$ , and $x_{i} : = 2^{- j}$ if $p (j) \neq 0$ for a (unique) $j ⩽ i$ . For the opposite reduction, let ${(x [n])}_{n}$ converge effectively to x. To obtain a $ρ_{ω + 1}$ -name p of x just put $p (i) = 0$ if $x [i + 2] \neq 2^{- i}$ and $p (i) = 1$ otherwise. Intuitively, according to the representation $ρ_{ω + 1}$ a name of $x \in ω + 1$ is a (computable!) oracle that for every $i \in N$ replies “yes” or “no” to the question “is $x = - 2^{- i}$ ?”; if the answer is always “no” then $x = 0$ .

It is often more convenient to represent $ω + 1$ by $ρ_{ω + 1}$ . However, when representing the space of closed subsets of $ω + 1$ we will view $ω + 1$ as a computable metric space and use the standard enumeration of the basic open balls $B (a, q)$ , for $a \in ω + 1$ and q a nonnegative rational number, to obtain the representation $ψ_{ω + 1}^{-}$ of $A_{-} (ω + 1)$ .

As a subset of $R$ , $ω + 1$ is also well-ordered by the usual order <. The single valued function ${min}_{ω + 1}^{-} : \subseteq A_{-} (ω + 1) \to ω + 1$ mapping A to $min (A)$ is then defined for every $A \neq \emptyset$ .

Proposition 3.1.
$Sort \equiv_{sW} {min}_{ω + 1}^{-}$ .
Proof.
We first show that $Sort ⩽_{sW} {min}_{ω + 1}^{-}$ . Given $p \in 2^{N}$ we construct a set $A \in A_{-} (ω + 1)$ that will provide us with the necessary information to compute $Sort (p)$ . More precisely, we define $A : = (ω + 1) ∖ ⋃_{s \in N} B_{s}$ , where $B_{s} : = {- 2^{- m} : m < n}$ if $p (0)$ , $\dots$ , $p (s)$ contains exactly n occurrences of 0. Let now r be a $ρ_{ω + 1}$ -name of $min (A)$ . By construction, $r (n) \neq 0$ if 0 occurs exactly n times in p. We obtain then $q : = Sort (p)$ as follows. We inspect r and as long as $r (n) = 0$ , we let $q (n) = 0$ , so that $q = 0^{N}$ if $r (n) = 0$ for all $n \in N$ . As soon as we find an n such that $r (n) \neq 0$ , then we let $q (m) = 1$ for every $m ⩾ n$ , so that in the end $q = 0^{n} 1^{N}$ .

To prove ${min}_{ω + 1}^{-} ⩽_{sW} Sort$ argue as follows. Let $A : = (ω + 1) ∖ ⋃_{n \in N} B_{n} \in A_{-} (ω + 1)$ be given as input to ${min}_{ω + 1}^{-}$ . Our strategy consists simply in choosing at any stage s the smallest element of $ω + 1$ not contained in $B_{0}, \dots, B_{s}$ and we want to write an input $r \in N^{N}$ for Sort that reflects our choice. At stage 0 let then $x_{0}$ be the least element of $ω + 1$ not contained in $B_{0}$ . If this is 0, then we write $r (0) = 0$ . Otherwise, let it be $- 2^{- n_{0}}$ for some $n_{0}$ . Then we put $0^{n_{0}} 1$ as initial segment of the input r of Sort. At stage $k + 1$ we consider the sets $B_{0}, \dots, B_{k + 1}$ . Let $x_{k + 1}$ be the least element not contained in $⋃_{i ⩽ k + 1} B_{i}$ , and let w be the initial segment of r obtained at stage k. If $x_{k + 1} = 0$ , then we let $r (| w |) : = 0$ . Otherwise, if $x_{k - 1} = - 2^{- n_{k + 1}}$ for some $n_{k + 1}$ we extend w so to obtain a finite prefix $w w^{'} 1$ with $w w^{'}$ containing exactly $n_{k + 1}$ occurrences of 0 (possibly $| w^{'} | = 0$ ). In the end, by construction, r contains exactly n occurrences of 0 if $min (A) = - 2^{- n}$ for some $n \in N$ , and r contains infinitely many 0 if $min (A) = 0$ . We now inspect $Sort (r)$ to compute a $ρ_{ω + 1}$ -name q of $min (A)$ . Recall that $Sort (r) = 0^{N}$ if r contains infinitely many occurrences of 0, that is, $min (A) = 0$ , otherwise $Sort (r) = 0^{n} 1^{N}$ if r contains exactly n occurrences of 0, that is, $min (A) = - 2^{- n}$ . Therefore, to obtain a correct $ρ_{ω + 1}$ -name q, we let $q (n) : = Sort (r) (n)$ as long as $Sort (r) (n) = 0$ . If suddenly $Sort (r) (n) = 1$ , then we let $q (n) : = 1$ and $q (m) = 0$ for all $m > n$ . In this way we obtain exactly the $ρ_{ω + 1}$ -name of $min (A)$ . □

Using Proposition 3.1, we now study the degree of Sort in more detail. The following result is given already in Proposition 24 of [21] but we give here a more direct proof of the same result in terms of computability with finitely many mind changes using ${min}_{ω + 1}^{-}$ .
Proposition 3.2.
$C_{N} <_{W} Sort$ .
Proof.
By Proposition 3.1 we can substitute Sort with ${min}_{ω + 1}^{-}$ .

To prove $C_{N} ⩽_{W} {min}_{ω + 1}^{-}$ , consider the operator ${min}_{N}^{-} : \subseteq A_{-} (N) \to N$ , $A \mapsto min (A)$ , for $A \neq \emptyset$ , which is known to be Weihrauch equivalent to $C_{N}$ by [26, Lemma 2.3]. We obtain $C_{N} \equiv_{W} {min}_{N}^{-} ⩽_{sW} {min}_{ω + 1}^{-}$ (for the rightmost reduction observe that the map $A \mapsto {- 2^{- n} : n \in A} \cup {0}$ from $A_{-} (N)$ to $A_{-} (ω + 1)$ is clearly computable).

To prove that ${min}_{ω + 1}^{-} ≰_{W} C_{N}$ , we will show that ${min}_{ω + 1}^{-}$ is not computable with finitely many mind changes.

Let p indeed be a $ψ_{ω + 1}^{-}$ -name of a nonempty closed $A \subseteq ω + 1$ . The task is to output the minimal element in A. Suppose that p lists only open balls of the type ${- 2^{- i}}$ for various $i \in N$ . If the sequence encoded by p will in the end contain every open ball of the form ${- 2^{- i}}$ , the temporary choice of any element of the form $- 2^{- k}$ will sooner or later force us to select a larger candidate. In this case we obtain the name of the correct output 0 only after infinitely many mind changes.

We should therefore choose 0 as the eventual output at some stage s, when only a finite initial segment of p has been read. However, this output is incorrect if the sequence encoded by p never mentions a specific element ${- 2^{- m}}$ , which is possible on the basis of the finite initial segment of p read by the computation at sage s. □

The next result is also given in Proposition 24 of [21]:
Proposition 3.3.
$Sort <_{W} lim$ .
Proof.
It is easy to see that $Sort ⩽_{sW} lim$ . To prove that the opposite reduction does not hold, apply the Invariance Principle: Sort has only computable outputs, whereas lim maps some computable input to an incomputable output. □

For the following results, we need the Bolzano Weierstraß operators ${BWT}_{n}$ , with $n : = {0, \dots, n - 1}$ for $n ⩾ 1$ , and the operators ${UBWT}_{X} : \subseteq X^{N} \to X$ , which are the restrictions of the operators ${BWT}_{X}$ to the sequences with compact range for which the accumulation point is unique.
Proposition 3.4.
For every $n ⩾ 1$ , ${min}_{ω + 1}^{-} ≰_{W} {BWT}_{n}$ .
Proof.
${min}_{ω + 1}^{-} ⩽_{W} {BWT}_{n}$ would imply $C_{N} ⩽_{W} {BWT}_{n}$ by Proposition 3.2. Since $C_{N} \equiv_{W} {UBWT}_{N}$ by [10, Corollary 11.24] and obviously ${UBWT}_{n + 1} ⩽_{W} {UBWT}_{N}$ , this would in turn imply ${UBWT}_{n + 1} ⩽_{W} {BWT}_{n}$ , which is impossible by [10, Proposition 13.9]. □

We now show that Sort is not non deterministically computable with finitely many mind changes: Proposition 3.5.
$Sort |_{W} C_{R}$
Proof.
Recall that an operation f is non-uniformly computable, if $f (x)$ contains a computable solution for all computable x. A Weihrauch degree f is called low, if $lim * f ⩽_{W} lim$ . Both properties are preserved downwards under Weihrauch reduction.

Notice that Sort is non-uniformly computable as all solutions are computable. Moreover $LPO * Sort$ computes the characteristic function of the $Σ_{2}^{0}$ -complete set $\begin{matrix} {p \in N^{N} : p contains finitely many occurrences of 0} . \end{matrix}$ Therefore $LPO * Sort ≰_{W} lim$ . Since $LPO ⩽_{W} lim$ and ∗ is monotone, it follows that Sort is not low. On the other hand, $C_{R}$ is low by [2, Theorem 8.7], but not non-uniformly computable because $WKL ⩽_{W} C_{R}$ and there exist computable infinite binary trees without computable infinite branches. The incomparability of Sort and $C_{R}$ then follows immediately. □

4. Exact projections operators

We start with the formal definition of the exact projection operators.

Definition 4.1.
Given a metric space X, a point $x \in X$ and a nonempty set $A \subseteq X$ we say that $y \in A$ is a projection point of x onto A if $d (x, y) = d (x, A)$ (where, as usual, $d (x, A) = inf {d (x, y) : y \in A}$ ). In other words, the projection points of x onto A are the points of A with minimal distance from x.

Notice that if $x \in A$ then x itself is the unique projection point of x onto A. Obviously, projection points of x onto A exist if and only if the infimum in the definition of $d (x, A)$ is actually a minimum. We will be mostly interested in the case where $X = R^{n}$ is a Euclidean space and A is closed; in this situation projection points of any $x \in R^{n}$ onto A do exist.

If X is a computable metric space, projections points give rise to several multi-valued functions, depending on the representation of $A \subseteq X$ , which we will always assume to be at least closed.
Definition 4.2.
Given a computable metric space X the (exact) negative, positive and total closed projection operators on X are the partial multi-valued functions ${Proj}_{X}^{-}$ , ${Proj}_{X}^{+}$ and ${Proj}_{X}$ which associate to every $x \in X$ (with Cauchy representation) and every closed $A \neq \emptyset$ (with negative, positive and total representation, respectively) the set of the projection points of x onto A.

Thus ${Proj}_{X}^{-} : \subseteq X \times A_{-} (X) ⇉ X$ , ${Proj}_{X}^{+} : \subseteq X \times A_{+} (X) ⇉ X$ , and ${Proj}_{X} : \subseteq X \times A (X) ⇉ X$ .

The (exact) negative, positive and total projections operators for compact sets are defined by replacing $A_{-} (X)$ , $A_{+} (X)$ , and $A (X)$ with $K_{-} (X)$ , $K_{+} (X)$ , and $K (X)$ respectively. These are denoted $Proj K_{X}^{-}$ , $Proj K_{X}^{+}$ , and $Proj K_{X}$ .

The first obvious observation is that the negative projection operators compute the corresponding choice operators.
Fact 4.3.
$K_{X} ⩽_{sW} Proj K_{X}^{-}$ and $C_{X} ⩽_{sW} {Proj}_{X}^{-}$ for all computable metric spaces X.

Projections on compact sets are special cases of projections on closed sets.
Fact 4.4.
For all computable metric spaces X:
$Proj K_{X}^{-} ⩽_{sW} {Proj}_{X}^{-}$ ,

$Proj K_{X}^{+} ⩽_{sW} {Proj}_{X}^{+}$ ,

$Proj K_{X} ⩽_{sW} {Proj}_{X}$ .

Proof.
The proof follows immediately by the definition of the representations. □

In some important cases, the inverse reduction holds as well. In the next result, a computable metric space X is computably compact when it is computable as a member of $K_{-} (X)$ , that is, it has some computable $κ_{X}^{-}$ -name (or, equivalently, of $K (X)$ ).
Fact 4.5.
For all computably compact metric spaces X:
$Proj K_{X}^{-} \equiv_{sW} {Proj}_{X}^{-}$ ,

$Proj K_{X}^{+} \equiv_{sW} {Proj}_{X}^{+}$ ,

$Proj K_{X} \equiv_{sW} {Proj}_{X}$ .

Proof.
The inverse reductions of Fact 4.4 can be obtained by fixing a finite cover of X by basic balls and use it to show that $id : A_{-} (X) \to K_{-} (X)$ , $id : \subseteq A_{+} (X) \to K_{+} (X)$ , and $id : \subseteq A (X) \to K (X)$ are computable. □
Theorem 4.6.
For $n ⩾ 1$ :
$Proj K_{R^{n}}^{-} \equiv_{W} {Proj}_{R^{n}}^{-}$ ,

$Proj K_{R^{n}}^{+} \equiv_{sW} {Proj}_{R^{n}}^{+}$ ,

$Proj K_{R^{n}} \equiv_{sW} {Proj}_{R^{n}}$ .

Proof.
The inverse reductions of Fact 4.4 can be obtained as follows.

We first deal with the positive representation. According to Remark 2.3, let $A : = \overline{{a_{n} : n \in N}} \in A_{+} (R^{n})$ and $x \in X$ . By [30, Lemma 5.1.7] we can compute $d (x, A)$ as an element of $R_{>}$ , hence we can determine a (natural) $M > d (x, A)$ . Given x we can also determine an upper bound $N \in N$ for $d (0, x)$ . Let $K : = \overline{A \cap B (0, M + N)}$ . Using Remark 2.5, and since clearly $K \subseteq \overline{B} (0, M + N)$ , it suffices to compute a dense sequence in K. This is not difficult, starting from the positive information for A: we list all points in ${a_{n} : n \in N}$ with distance from 0 strictly less than $M + N$ . Notice that all projection points of x onto A belong to K. Obviously, these points also are projections points of x onto K, so that an application of $Proj K_{R^{n}}^{+}$ to this new set releases a correct result.

We now deal with the total representation. Let then $A \in A (R^{n})$ be given. We want to compute, as a suitable input for $Proj K_{R^{n}}$ , some compact L with total information such that the projections points of x onto L should be also projection points of x onto A. However, we cannot set $L : = K$ (with K the same of the previous case). This is because the possible elements in $A \cap \partial B (0, M + N)$ that are not accumulation points of the dense set enumerated in K do not belong to K, but they are inevitably preserved by the negative information on A and on $R^{n} ∖ \overline{B} (0, M + N)$ . Thus, the two descriptions needed to provide the total information of K can fail to be coherent. To obtain consistent information for both types of information, we add to K the whole set $\partial \overline{B} (0, M + N)$ . Therefore we define L to be $\begin{matrix} \overline{A \cap B (0, M + N)} \cup \partial B (0, M + N) = (A \cap \overline{B} (0, M + N)) \cup \partial B (0, M + N) . \end{matrix}$ The left hand term of the equation guarantees that a $ψ_{R^{n}}^{+}$ -name of L can be effectively obtained, while the right hand side guarantees the same with respect to a $ψ_{R^{n}}^{-}$ - name. Finally, use Remark 2.5 and the fact that $L \subseteq \overline{B} (0, M + N)$ to obtain a $κ_{R^{n}}$ -name of L as a member of $K (R^{n})$ .

We now consider the negative representation with the goal of showing that ${Proj}_{R^{n}}^{-} ⩽_{W} Proj K_{R^{n}}^{-}$ . We make use of the homeomorphism f between $R^{n}$ and the open ball $B (0, \frac{π}{2})$ defined by $\begin{matrix} f (t) = \{\begin{matrix} arctan (d (t, 0)) \frac{t}{d (t, 0)} & if t \neq 0; \\ 0 & if t = 0 . \end{matrix} \end{matrix}$ We claim that f is computable. The critical points are the vectors t close to 0, but we can handle them as follows: until the test $arctan (d (t, 0)) > 0$ fails and the parallel test $arctan (d (t, 0)) < 2^{- i}$ succeeds, we let $f (t) [i] = 0$ . Notice in fact, that for all $t \in R^{n}$ (including 0), $d (f (t), 0) = arctan (d (t, 0))$ . Analogously, one can prove that $f^{- 1}$ is also computable.

Now suppose we are given $(x, A) \in dom ({Proj}_{R^{n}}^{-})$ . We compute a compact set $H \in K_{-} (R^{n})$ as follows. The main idea is to use f to rescale A within the compact $\overline{B} (0, \frac{π}{2})$ . However, the function f produces unavoidable metric distortions, as f-images get closer to each other the more the original points are far from the origin. Hence, projections points of $f (x)$ onto $f (A)$ do not necessarily correspond to f-images of the projection points of x onto A. To solve this problem, we first translate the space so that x becomes the origin: in this way, the order relationships between distances from x are preserved by f. To take into account that possible “infinity points” of A get mapped to points on $\partial B (0, \frac{π}{2})$ we add the whole $\partial B (0, \frac{π}{2})$ to our compact set. Therefore we set $\begin{array}{l} H & : = f (A - x) \cup \partial B (0, \frac{π}{2}) \\ = {y \in R^{n} : d (y, 0) ⩽ \frac{π}{2} \land (d (y, 0) < \frac{π}{2} \Rightarrow f^{- 1} (y) + x \in A)} . \end{array}$ The second line provides a $Π_{1}^{0}$ definition of H with A and x as parameters, and hence (a name for) $H \in A_{-} (R^{n})$ is computed from (a name for) x and $A \in A_{-} (R^{n})$ . Since $H \subseteq \overline{B} (0, \frac{π}{2})$ , by Remark 2.5 we have $H \in K_{-} (R^{n})$ .

Since $d (t, x) = d (t - x, 0)$ and $d (f (t - x), 0) = arctan (d (t - x, 0))$ , the monotonicity of arctan implies that $d (f (t - x), 0) ⩽ d (f (t^{'} - x), 0)$ if and only if $d (t, x) ⩽ d (t^{'}, x)$ for all $t, t^{'} \in R^{n}$ . Thus the members of $Proj K_{R^{n}}^{-} (0, H)$ are exactly those of the form $f (t - x)$ for some $t \in {Proj}_{R^{n}}^{-} (x, A)$ . Therefore from $y \in Proj K_{R^{n}}^{-} (0, H)$ we can compute $f^{- 1} (y) + x \in {Proj}_{R^{n}}^{-} (x, A)$ . Notice that we are using x (which is part of the original input) in this final computation, so that we do not prove ${Proj}_{R^{n}}^{-} ⩽_{sW} Proj K_{R^{n}}^{-}$ . □

Since we are interested mainly in projections in Euclidean spaces, Theorem 4.6 allows us to concentrate on operators for closed sets.

The proof of the next theorem shows that we can obtain upper bounds for all three exact projection operators by using essentially the same argument. Theorem 4.7.

For $n ⩾ 1$ , ${Proj}_{R^{n}}^{-}$ and ${Proj}_{R^{n}}^{+}$ are non deterministically limit computable, that is ${Proj}_{R^{n}}^{-}$ , ${Proj}_{R^{n}}^{+} ⩽_{sW} {BWT}_{R}$ .

For $n ⩾ 1$ , ${Proj}_{R^{n}}$ is non deterministically computable, that is ${Proj}_{R^{n}} ⩽_{sW} WKL$ .

Proof.
We first show (2). Given $x \in R^{n}$ and $A \in A (R^{n})$ we can compute $d (x, A) \in R$ by [30, Lemma 5.1.7]. We use this distance to compute first $C : = \partial B (x, d (x, A))$ as an element in $A_{-} (R^{n})$ , and then $A \cap C \in A_{-} (R^{n})$ . This set obviously consists precisely of all projection points of x onto A.

We use then an upper bound N of $d (x, 0)$ and an upper bound M of $d (x, A)$ to translate $A \cap C$ into an element of $K_{-} (R^{n})$ : it holds in fact that $A \cap C \subseteq C \subseteq \overline{B} (0, N + M)$ .

Finally, to determine a projection point of x onto A, it suffices to select a point from this compact set. This is the only non computable step in the construction, but it is non deterministically computable by [6, Theorem 2.10]. This shows ${Proj}_{R^{n}} ⩽_{W} WKL$ , and ${Proj}_{R^{n}} ⩽_{sW} WKL$ follows because WKL is a cylinder.

When A is not provided with total information, we can initially use lim to obtain the total information about A. For the input $A \in A_{+} (R^{n})$ , this follows by [4, Proposition 4.2]. For the input $A \in A_{-} (R^{n})$ this follows by [4, Proposition 4.5] (since $R^{n}$ is effectively locally compact). The remainder of the process remains unaltered. Therefore, the negative and the positive projection operators can be simulated by composing a limit computable procedure with a non deterministically computable one, i.e., they are non deterministically limit computable.

By [10, Corollary 11.19] this means that ${Proj}_{R^{n}}^{-}$ , ${Proj}_{R^{n}}^{+} ⩽_{W} {BWT}_{R}$ and again, since ${BWT}_{R}$ is a cylinder (see [10, Corollary 11.13]), we obtain ${Proj}_{R^{n}}^{-}$ , ${Proj}_{R^{n}}^{+} ⩽_{sW} {BWT}_{R}$ . □

4.1. Exact negative projection operators

In the previous section we have seen that ${Proj}_{R^{n}}^{-} ⩽_{sW} {BWT}_{R}$ . But is this reduction in fact an equivalence? This is indeed the case for $n ⩾ 2$ as the following result shows:

Theorem 4.8.
${BWT}_{R} ⩽_{sW} {Proj}_{R^{n}}^{-}$ for $n ⩾ 2$ .
Proof.
Recall that by [10, Corollary 11.7], ${BWT}_{R} \equiv_{sW} {WKL}^{'}$ . Hence we can substitute in the proof ${BWT}_{R}$ by ${WKL}^{'}$ . Moreover, it suffices to work with $n = 2$ because the results for $n > 2$ follow by transitivity of $⩽_{sW}$ as ${Proj}_{R^{2}}^{-} ⩽_{sW} {Proj}_{R^{n}}^{-}$ .

Fix the usual (and computable, by [7, Lemma 7.1]) embedding $ι : 2^{N} \to [0, 1]$ . Moreover, let $h : N^{< N} \to [1, 2]$ be computable and such that $w <_{l e x} w^{'}$ iff $h (w) < h (w^{'})$ for every $w, w^{'} \in N^{< N}$ .

Throughout this proof it is convenient to represent points of $R^{2}$ in polar coordinates (which we will write $(r, α)$ ). This does not cause any problem, because we use only points with radial coordinate not smaller than 1 and angular coordinate in the interval $[0, 1]$ : for such points both directions of the conversion between Cartesian and polar coordinates are computable.

Without loss of generality, we are given as input a sequence of trees ${(T_{n})}_{n}$ converging to an infinite binary tree T and we want to find, using ${Proj}_{R^{2}}^{-}$ , an infinite path in T. To achieve this goal we compute a closed subset B of $A = {(r, α) : 1 ⩽ r ⩽ 2 \land α \in ι (2^{N})} \in A^{-} (R^{2})$ such that if $(r, α) \in {Proj}_{R^{n}}^{-} (0, B)$ , then $ι^{- 1} (α)$ is an infinite path in T. B is defined as the intersection of closed sets $B_{s}$ .

To describe the $B_{s}$ , for each $w \in 2^{< N}$ and $r_{0} ⩾ 1$ , let us denote by $B_{w, r_{0}}$ the closed set $A ∖ {(r, α) : r < r_{0} \land w ≺ ι^{- 1} (α)} \in A^{-} (R^{2})$ (here, as usual, $w ≺ p$ denotes that the finite binary string w is an initial segment of $p \in 2^{N}$ ). In words, $B_{w, r_{0}}$ is obtained by removing from A the inner slice up to $r_{0}$ in the w-direction.

At stage s, for every $k ⩽ s$ we let $t_{k} (s)$ be the cardinality of the set $\begin{matrix} {n < s : T_{n} \cap 2^{k} \neq T_{n + 1} \cap 2^{k}} . \end{matrix}$ We then define, for every $k ⩽ s$ , $\begin{array}{l} r_{k} (s) = h (⟨ t_{0} (s), \dots, t_{k - 1} (s), t_{k} (s) ⟩), and \\ r_{k}^{+} (s) = h (⟨ t_{0} (s), \dots, t_{k - 1} (s), t_{k} (s) + 1 ⟩) . \end{array}$ Eventually, we let $\begin{matrix} B_{s} = ⋂_{k ⩽ s} (⋃_{w \in 2^{k} \cap T_{s}} B_{w, r_{k} (s)} \cup ⋃_{w \in 2^{k} ∖ T_{s}} B_{w, r_{k}^{+} (s)}) . \end{matrix}$

In this way we compute $B = ⋂_{s} B_{s} \in A^{-} (R^{2})$ and we need to show that if $(r, α) \in {Proj}_{R^{2}}^{-} (0, B)$ then $ι^{- 1} (α)$ is a path in T.

Since ${(T_{n})}_{n}$ converges, for every k the sequence ${(t_{k} (s))}_{s}$ is non-decreasing and eventually takes a constant value $t_{k}$ . Therefore the sequences ${(r_{k} (s))}_{s}$ and ${(r_{k}^{+} (s))}_{s}$ stabilize at $r_{k} = h (⟨ t_{0}, \dots, t_{k - 1}, t_{k} ⟩)$ and $r_{k}^{+} = h (⟨ t_{0}, \dots, t_{k - 1}, t_{k} + 1 ⟩)$ respectively.

If $p \in [T]$ then the ray starting at 0 and moving in direction $ι (p)$ meets B at distance $sup {r_{k} : k \in N}$ from 0. To see this notice first that if $t_{k} (s^{'}) > t_{k} (s)$ then $r_{k} (s^{'}) = h (⟨ t_{0} (s^{'}), \dots, t_{k - 1} (s^{'}), t_{k} (s^{'}) ⟩) ⩾ h (⟨ t_{0} (s), \dots, t_{k - 1} (s), t_{k} (s) + 1 ⟩) = r_{k}^{+} (s)$ . Thus, even when for some $s ⩾ k$ with $p ↾ k \notin T_{s}$ we deleted the ray in direction $ι (p)$ up to $r_{k}^{+} (s)$ , at some later stage $s^{'}$ (such that $p ↾ k \in T_{s^{'}}$ and so $t_{k} (s^{'}) > t_{k} (s)$ ) the deletion up to $r_{k} (s^{'}) ⩽ r_{k}$ superseded it.

If instead $p \notin [T]$ and ℓ is least such that $p ↾ ℓ \notin T$ then the ray starting at 0 and moving in direction $ι (p)$ meets B at distance $⩾ r_{ℓ}^{+}$ from 0 (because at a stage s such that $T_{s} \cap 2^{⩽ ℓ} = T \cap 2^{⩽ ℓ}$ we delete the ray up to distance $r_{ℓ}^{+}$ ).

It thus suffices to check that $sup {r_{k} : k \in N} < r_{ℓ}^{+}$ for every ℓ. Indeed we have $\begin{matrix} sup {r_{k} : k \in N} = sup {h (⟨ t_{0}, \dots, t_{k} ⟩) : k \in N} ⩽ h (⟨ t_{0}, \dots, t_{ℓ}, t_{ℓ + 1} + 1 ⟩) < h (⟨ t_{0}, \dots, t_{ℓ} + 1 ⟩) = r_{ℓ}^{+} . \end{matrix}$ Thus every point in ${Proj}_{R^{2}}^{-} (0, B)$ is in direction $ι (p)$ for some $p \in [T]$ , as required. □
Corollary 4.9.
${Proj}_{R^{n}}^{-} \equiv_{sW} {BWT}_{R}$ for $n ⩾ 2$ .
Proof.
By Theorem 4.7.(1) and Theorem 4.8. □

For case $n = 1$ we do not obtain the full power of ${BWT}_{R}$ . We can prove however that a characterization for the one dimensional case can be found in terms of ${BWT}_{2}$ . As a preliminary result, we prove:
Proposition 4.10.
${Proj}_{R}^{-} ⩽_{W} LLPO * lim$ .
Proof.
Analogously to the treatment of negative information in the proof of Theorem 4.6, given $x \in R$ and $A \in A_{-} (R)$ we can compute the set $\begin{matrix} B : = arctan (A - x) \cup {- \frac{π}{2}} \cup {\frac{π}{2}} \in A_{-} (R) . \end{matrix}$ Notice that for such a set both $\begin{matrix} ℓ : = max {y \in B : y ⩽ 0} and r : = min {y \in B : y ⩾ 0} \end{matrix}$ always exist, which would not hold true in general for our original A. Moreover ${Proj}_{R}^{-} (0, B) \subseteq {ℓ, r}$ . Since $A \neq \emptyset$ , $| y | < \frac{π}{2}$ for all $y \in {Proj}_{R}^{-} (0, B)$ . More precisely, as in the proof of Theorem 4.6, the members of ${Proj}_{R}^{-} (0, B)$ are exactly those of the form $arctan (t - x)$ for some $t \in {Proj}_{R}^{-} (x, A)$ . Recalling that $B \in A_{-} (R)$ we can determine ℓ as an element of $R_{>}$ and r as an element of $R_{<}$ . We then use $lim \times lim \equiv_{sW} lim$ to obtain $ℓ, r \in R$ . Let now denote as $f_{0}$ the function mapping any given $B \in A_{-} (R)$ for which the elements ℓ, r defined as above exist to the pair $(ℓ, r) \in R^{2}$ . We have then just proved that $f_{0} ⩽_{sW} lim$ .

Consider now the function $g_{0} : R^{2} \to R$ such that $g_{0} (z_{0}, z_{1}) \in {z_{0}, z_{1}}$ and $| g_{0} (z_{0}, z_{1}) | = min {| z_{0} |, | z_{1} |}$ . It is easy to see that $g_{0} ⩽_{W} LLPO$ (an application of LLPO finds $i < 2$ such that $| z_{i} | ⩽ | z_{1 - i} |$ , then we use the input $(z_{0}, z_{1})$ of $g_{0}$ , which is still available by definition of $⩽_{W}$ , to recover the value of $z_{i}$ ).

Let now $y : = g_{0} (ℓ, r)$ . Then, in virtue of what observed above, $tan (y) + x \in {Proj}_{R}^{-} (x, A)$ .

This shows that ${Proj}_{R}^{-} ⩽_{W} g_{0} \circ f_{0}$ (the transformation $(x, A) \mapsto B$ was indeed computable uniformly in $(x, A)$ and notice also that, by definition of $⩽_{W}$ , the original $x \in R$ is still available after the application of $g_{0} \circ f_{0}$ , hence it can be used to compute $tan (y) + x$ ).

By definition of compositional product, $g_{0} \circ f_{0} ⩽_{W} LLPO * lim$ for every $g_{0} ⩽_{W} LLPO$ and $f_{0} ⩽_{W} lim$ . Therefore ${Proj}_{R}^{-} ⩽_{W} LLPO * lim$ . □

For the next result we need to use the Sierpinski space and its ordinary admissible representation:
Definition 4.11 (Sierpinski space).

The Sierpinski space is given by the topology $S : = {{1}, {0, 1}}$ on the set $2 : = {0, 1}$ .

As a represented space, the Sierpinski space is equipped with the representation $δ_{S} (0^{N}) = 0$ and $δ_{S} (p) = 1$ for $p \neq 0^{N}$ .

In other words, LPO can be seen as the identity function ${id}_{S, 2} : S \to {0, 1}$ , $i \mapsto i$ , where the codomain is equipped with the discrete topology.

Lemma 4.12.
${BWT}_{2} \times lim ⩽_{sW} {Proj}_{R}^{-}$ .
Proof.
Consider the space $S^{N}$ . As ${id}_{S, 2} \equiv_{sW} LPO$ , for the identity function ${id}_{S^{N}, 2^{N}} : S^{N} \to 2^{N}$ we find that ${id}_{S^{N}, 2^{N}} \equiv_{sW} lim$ , as obviously ${id}_{S^{N}, 2^{N}} \equiv_{sW} \hat{{id}_{S, 2}}$ and moreover $lim \equiv_{sW} \hat{LPO}$ ([5, Lemma 6.3], [11, Theorem 6.7]). In the statement we can thus replace lim with ${id}_{S^{N}, 2^{N}}$ .

Notice now that the computable embedding $ι : 2^{N} \to [0, 1]$ we already used in the proof of Theorem 4.8 gives naturally rise to a corresponding computable embedding $ι_{S} : S^{N} \to R_{<}$ . Recall that ι preserves the order on binary sequences, hence $ι_{S}$ does the same.

Finally, observe that ${Sort}_{S} : 2^{N} \to S^{N}$ , the lifted version of Sort such that ${Sort}_{S} (p) \in S^{N}$ coincides with $Sort (p) \in 2^{N}$ , is computable.

In the following, by notational abuse, we identify $S^{N}$ with $dom (δ_{S^{N}}) = N^{N}$ , that is, we will not distinguish a binary sequence $(i_{0}, i_{1}, i_{2}, \dots) \in S^{N}$ from any $⟨ p_{0}, p_{1}, p_{2}, \dots ⟩ \in N^{N}$ such that $δ_{S^{N}} (⟨ p_{0}, p_{1}, p_{2}, \dots ⟩) = (δ_{S} (p_{0}), δ_{S} (p_{1}), δ_{S} (p_{2}), \dots) = (i_{0}, i_{1}, i_{2}, \dots)$ . This produces no ambiguity for ${id}_{S^{N}, 2^{N}}$ and $ι_{S}$ that still remain single-valued, whereas the single-valuedness of ${Sort}_{S}$ can be preserved by its replacement with a computable realizer. For instance, we will see $ι_{S}$ as defined by $ι_{S} (⟨ p_{0}, p_{1}, p_{2}, \dots ⟩) : = ι (δ_{S} (p_{0}), δ_{S} (p_{1}), δ_{S} (p_{2}), \dots)$ , and ${Sort}_{S} (p)$ as being of the form $⟨ p_{0}, p_{1}, p_{2}, \dots ⟩$ with $Sort (p) = (δ_{S} (p_{0}), δ_{S} (p_{1}), δ_{S} (p_{2}), \dots)$ .

Now, given inputs $(p, q) \in {BWT}_{2} \times {id}_{S^{N}, 2^{N}}$ , we compute $ℓ : = - ι_{S} (⟨ {Sort}_{S} (p), q ⟩) \in R_{>}$ and $r : = ι_{S} (⟨ {Sort}_{S} (1 - p), q ⟩) \in R_{<}$ , where $\begin{matrix} ⟨ {Sort}_{S} (p), q ⟩ : = ⟨ p_{0}, q_{0}, p_{1}, q_{1}, p_{2}, q_{2}, \dots ⟩ \end{matrix}$ for ${Sort}_{S} (p) : = ⟨ p_{0}, p_{1}, p_{2}, \dots ⟩$ and $q : = ⟨ q_{0}, q_{1}, q_{2}, \dots ⟩$ . Since $ι_{S} ({Sort}_{S} (s))$ coincides with $ι (Sort (s))$ for all $s \in N^{N}$ , we notice that $| ℓ | ⩽ | r |$ if and only if only if p contains infinitely many 0 (in this case indeed $Sort (p) = 0^{N}$ ), and $| ℓ | ⩾ | r |$ if and only if p contains infinitely many 1 (in this case indeed $Sort (1 - p) = 0^{N}$ ).

Given now $ℓ \in R_{>}$ and $r \in R_{<}$ , we can compute $\begin{matrix} A : = {x \in R : x ⩽ ℓ - 1 \lor x ⩾ r + 1} \in A_{-} (R) . \end{matrix}$ From $y \in {Proj}_{R}^{-} (0, A) \subseteq {ℓ - 1, r + 1}$ we can use $ι^{- 1} : \subseteq R \to 2^{N}$ to compute $⟨ {Sort}_{S} (p), q ⟩$ and then $q \in 2^{N}$ . Moreover, the sign of y yields a valid answer to ${BWT}_{2} (p)$ (notice that the sign of $ℓ - 1$ , $r - 1$ is always decidable, as they are necessarily different from 0, which is not necessarily the case for ℓ and r). □

Through the notion of jump that we recalled in Section 2.3 we are now able to characterize ${Proj}_{R}^{-}$ in terms of ${BWT}_{2}$ : Corollary 4.13.
${Proj}_{R}^{-} \equiv_{W} {BWT}_{2} \times lim$ .
Proof.
This follows by Proposition 4.10 and Lemma 4.12, since ${BWT}_{2} \equiv_{sW} {LLPO}^{'}$ ([10, Corollary 11.11]) and since for generic multi-valued functions f it holds $f * lim \equiv_{W} f^{'} \times lim$ . □

4.2. Exact positive projection operators

Quite surprisingly, for the projections with positive information for closed sets we obtain the same characterizations obtained for the case of negative information. We start with the dimensions $n ⩾ 2$ for which we are still able to prove the equivalence with ${BWT}_{R}$ :

Proposition 4.14.
${BWT}_{R} ⩽_{sW} {Proj}_{R^{n}}^{+}$ for $n ⩾ 2$ .
Proof.
We prove the statement for $n = 2$ . As before, the results for $n > 2$ follow by transitivity of $⩽_{sW}$ as ${Proj}_{R^{2}}^{+} ⩽_{sW} {Proj}_{R^{n}}^{+}$ . As in the proof of Theorem 4.8, also here it is convenient to represent points of $R^{2}$ in polar coordinates. In this case we use only points with radial coordinate not smaller than 1 and angular coordinate in the interval $[- \frac{π}{2}, \frac{π}{2}]$ , so that again for our purposes both directions of the conversion between Cartesian and polar coordinates are computable.

Let ${(a_{n})}_{n} \in dom ({BWT}_{R})$ be given as input. We want to find a cluster point of this sequence. We consider the points $b_{n} = (1 + 2^{- n}, arctan (a_{n}))$ . Let now $A : = \overline{{b_{n} : n \in N}} \in A_{+} (R^{2})$ . Notice that $(1, \pm \frac{π}{2}) \notin A$ because ${(a_{n})}_{n}$ is bounded, while $(1, α) \in {Proj}_{R^{2}}^{+} (0, A)$ if and only if $tan (α)$ is a cluster point of ${(a_{n})}_{n}$ . Thus if $(r, α) \in {Proj}_{R^{2}}^{+} (0, A)$ then $r = 1$ and $tan (α) \in {BWT}_{R} ({(a_{n})}_{n})$ . □
Corollary 4.15.
${Proj}_{R^{n}}^{+} \equiv_{sW} {BWT}_{R}$ for $n ⩾ 2$ .
Proof.
By Theorem 4.7.(1) and Proposition 4.14. □

For $n = 1$ , by reasoning analogously to the case of negative information, we obtain the same characterization in terms of ${BWT}_{2}$ . We start with the following result, which is an analoguous of Proposition 4.10: Proposition 4.16.
${Proj}_{R}^{+} ⩽_{W} LLPO * lim$ .
Proof.
Let $A : = {x_{n} : n \in N} \in A_{+} (R)$ and $x \in R$ be given. We can now compute $\begin{matrix} B : = A \cup {x - d (x, x_{0}) - 1} \cup {x + d (x, x_{0}) + 1} \in A_{+} (R) . \end{matrix}$ Notice that both $ℓ : = max {y \in B : y ⩽ x}$ and $r : = min {y \in B : y ⩾ x}$ always exist, which would not hold true in general for our original A. Moreover ${Proj}_{R}^{+} (x, B) = {Proj}_{R}^{+} (x, A)$ . Recalling that $B \in A_{+} (R)$ we can determine ℓ as an element of $R_{<}$ and r as an element of $R_{>}$ . Analogously to the proof of Proposition 4.10, we can then use $lim \times lim \equiv_{sW} lim$ to obtain $ℓ, r \in R$ and consequently LLPO to determine $y \in {ℓ, r}$ such that $d (y, x) = min {d (ℓ, x), d (r, x)}$ . As observed, this gives a member of ${Proj}_{R^{n}}^{+} (x, A)$ . □
Lemma 4.17.
${BWT}_{2} \times lim ⩽_{sW} {Proj}_{R}^{+}$ .
Proof.
The proof is almost the same of that of Lemma 4.12. But the replacement of the negative representation for closed sets with its dual requires to switch the positions of ℓ and r with respect to 0. We compute then the new set $A : = {x \in R : x ⩽ r - 2 \lor x ⩾ ℓ + 2} \in A_{+} (R)$ . From $y \in {Proj}^{+} (0, B)$ we can then extract q. Moreover, given the sign of y, we will select 0 or 1 as accumulation point of the input sequence by making the dual choice with respect to that of the proof of Lemma 4.12. □
Corollary 4.18.
${Proj}_{R}^{+} \equiv_{W} {BWT}_{2} \times lim$ .
Proof.
This follows by Proposition 4.16 and Lemma 4.17, analogously to the proof of Corollary 4.13. □

4.3. Exact total projection operators

For the case of total information we can fully characterize the Weihrauch degree of ${Proj}_{R^{n}}$ already for $n = 1$ . We start by determining the following upper bound:

Proposition 4.19.
${Proj}_{R} ⩽_{W} LLPO$ .
Proof.
Let the input $(x, A)$ be given with $A \in A (R)$ . It holds obviously that $0 < | {Proj}_{R} (x, A) | ⩽ 2$ , and in fact ${Proj}_{R} (x, A) = {x - r, x + r} \cap A$ for $r : = d (x, A)$ . By using the total information on A we can compute the exact value of r via approximations that become at every stage more reliable. We produce then a valid input $⟨ p_{0}, p_{1} ⟩$ for LLPO in the following way. At stage s, by considering the initial segment of the negative information on A that we have read so far, if both points $x - r$ and $x + r$ still are plausible candidates as members of A we let $p_{0} (s) : = 0 = : p_{1} (s)$ . Otherwise, suppose that we realize that one of the two points, say $x - r$ , is not in A. Then we put $p_{0} (s) : = 1 \neq 0 = : p_{1} (s)$ . We then let $p_{0} (s + m) : = 0 = : p_{1} (s + m)$ for all $m > 0$ . If instead we realize that $x + r \notin A$ then we switch the roles of $p_{0}$ and $p_{1}$ .

Given now $i \in LLPO (⟨ p, q ⟩)$ we compute (again) $x - r$ or $x + r$ , depending on whether $i = 0$ or $i = 1$ , finding an element of ${Proj}_{R} (A, x)$ . □

Notice that in the above proof the use of the original input after the application of LLPO is essential: ${Proj}_{R} ⩽_{sW} LLPO$ cannot hold for mere cardinality reasons. But the opposite reduction even holds for the strong version of Weihrauch reducibility:
Proposition 4.20.
$LLPO ⩽_{sW} {Proj}_{R}$ .
Proof.
Let $⟨ p_{0}, p_{1} ⟩ \in dom (LLPO)$ . We construct then a valid input $(x, A)$ for ${Proj}_{R}$ according to the following idea: if a point of ${Proj}_{R} (0, A)$ is negative, then $p_{0} = 0^{N}$ , and if a point of ${Proj}_{R} (0, A)$ is positive, then $p_{1} = 0^{N}$ . If we do this then by checking the sign of an element of ${Proj}_{R} (0, A)$ we determine an element of $LLPO (⟨ p_{0}, p_{1} ⟩)$ .

The construction of A proceeds as follows. We immediately remove from A the intervals $] - 1, 1 [$ , $] - \infty, - 2 [$ and $] 2, \infty [$ . Then we activate the following inductive procedure. Suppose that at stage $s ⩾ 0$ it holds $p_{0} (m) = 0 = p_{1} (m)$ for all $m ⩽ s$ . We add then to A the points $x_{0, s} : = - 1 - 2^{- s}$ and $x_{1, s} : = 1 + 2^{- s}$ . At the same time we remove from A the intervals $] x_{0, s - 1}, x_{0, s} [$ and $] x_{1, s}, x_{1, s - 1} [$ . Otherwise, let s be the first stage in which a digit different from 0 appears in $⟨ p_{0}, p_{1} ⟩$ , say, $p_{0} (s) \neq 0$ . We want then the closest point of A to 0 to be positive. To this aim, we add to A the point $x_{1, s} : = 1 + 2^{- s}$ alone. Moreover, we remove from A the intervals $] x_{0, s - 1}, 0 [$ , $] 0, x_{1, s} [$ (notice that 0 was removed from A already before the start of the inductive procedure), and $] x_{1, s}, x_{1, s - 1} [$ . In this case the description of A is complete after stage s. The case $p_{1} (s) \neq 0$ is analogous. □
Corollary 4.21.
${Proj}_{R} \equiv_{W} LLPO$ .
Proof.
By Propositions 4.19 and 4.20. □

For $n ⩾ 2$ we see instead that a precise characterisation is given by WKL.
Theorem 4.22.
$WKL ⩽_{sW} {Proj}_{R^{n}}$ for $n ⩾ 2$ .
Proof.
We prove the statement for $n = 2$ by replacing WKL through its well known strongly Weihrauch equivalent version $C_{[0, 1]}$ (see [2, Corollary 4.6]). The cases $n > 2$ are then as usual proved by transitivity of $⩽_{sW}$ .

Let then $A \in A_{-} ([0, 1])$ be given, which means that we are provided with a sequence of rational open intervals ${(I_{n})}_{n}$ such that $[0, 1] ∖ A = ⋃_{n \in N} I_{n}$ . We now construct the new closed set $K \in A (R^{2})$ as the set of all points (with polar coordinates, as in the proofs of Theorem 4.8 and Proposition 4.14) $(r, α)$ satisfying the following three conditions:
$1 ⩽ r ⩽ 2$ ,

$0 ⩽ α ⩽ 1$ ,

$(\forall n) (α \in I_{n} \Rightarrow 1 + 2^{- n + 1} ⩽ r)$ .
Intuitively, we draw in $R^{2}$ part of the circular crown between the circles of radius 1 and 2 centered at the origin. We then remove around a point $(1, α)$ a little open portion of the crown as soon as we know that $α \notin A$ (see Fig. 1).
Figure 1.
The construction of the set $K \subseteq R^{2}$ in the proof of Theorem 4.22: Here $I_{0}, I_{3} \subseteq [0, 1] ∖ A$ overlap.

It is immediate to see that if $(r, α) \in {Proj}_{R^{2}} (0, K)$ then $r = 1$ and $α \in A$ . Hence it remains to prove that we can compute a name of $K \in A (R^{2})$ .

To see that (a name for) K as an element of $A_{-} (R^{2})$ is computable from (the given name for) A, observe that all the conditions (1)–(3) are $Π_{1}^{0}$ in ${(I_{n})}_{n}$ .

To see that also (a name for) K as an element of $A_{+} (R^{2})$ is computable from (the given name for) A, observe that K is the closure of the set $\begin{matrix} C : = {(r, α) \in Q \times Q : (r, α) \in K \land r > 1} . \end{matrix}$ We claim that we can enumerate, and even decide, this subset of $Q \times Q$ effectively from ${(I_{n})}_{n}$ . The conditions $1 < r ⩽ 2$ and $0 ⩽ α ⩽ 1$ are immediately decidable for rational numbers. Hence, to determine whether $(r, α) \in K$ it remains only to analyze the condition (3) in the definition of K. To this aim, for $1 < r ⩽ 2$ , let then $m \in N$ be minimal such that $1 + 2^{- m + 1} ⩽ r$ . Then, for $1 ⩽ α ⩽ 2$ condition (3) is equivalent to $α \notin ⋃_{n < m} I_{n}$ . Since r and α are rational numbers, we can find effectively such m and then decide whether $α \in ⋃_{n < m} I_{n}$ .

Therefore the set C is decidable and we can enumerate its members (as pairs of real numbers) for the positive information on K. □
Corollary 4.23.
${Proj}_{R^{n}} \equiv_{sW} WKL$ for $n ⩾ 2$ .
Proof.
By Theorem 4.7.(2) and Theorem 4.22 □
5. Approximate projections

Since, as we have seen, the (exact) projection operators are computationally quite hard, it might be reasonable to consider some approximate versions of them. In many practical circumstances, we may indeed be content of finding points that lie at a distance comparable with the smallest one.

Definition 5.1.
Given a metric space X, $ε > 0$ , a point $x \in X$ and a nonempty set $A \subseteq X$ we say that $y \in A$ is a ε-projection point of x onto A if $d (x, y) ⩽ (1 + ε) d (x, A)$ . In other words, the ε-projection points of x onto A are the points of A which are at minimal distance from x up to an error of ε times the distance itself.

Notice that if $x \in A$ then for any ε, x is the unique ε-projection point of x onto A. In general, for any ε, ε-projection points of x onto A exist unless $x \in \bar{A} ∖ A$ . As when dealing with exact projections, we will be interested in the case where A is closed; in this situation ε-projection points of any $x \in X$ onto A do exist for any ε. If X is a computable metric space, the multi-valued functions arising from ε-projections points and depending on the representation of $A \subseteq X$ are defined similarly to their exact counterparts.
Definition 5.2.
Given a computable metric space X and $ε > 0$ the ε-approximate negative, positive and total closed projection operators on X are the partial multi-valued functions $ε - {Proj}_{X}^{-}$ , $ε - {Proj}_{X}^{+}$ and $ε - {Proj}_{X}$ which associate to every $x \in X$ (with Cauchy representation) and every closed $A \neq \emptyset$ (with negative, positive and total representation, respectively) the set of the ε-projection points of x onto A.

Thus $ε - {Proj}_{X}^{-} : \subseteq X \times A_{-} (X) ⇉ X$ , $ε - {Proj}_{X}^{+} : \subseteq X \times A_{+} (X) ⇉ X$ , and $ε - {Proj}_{X} : \subseteq X \times A (X) ⇉ X$ .

The ε-approximate negative, positive and total projections operators for compact sets are defined by replacing $A_{-} (X)$ , $A_{+} (X)$ , and $A (X)$ with $K_{-} (X)$ , $K_{+} (X)$ , and $K (X)$ respectively. These are denoted $ε - Proj K_{X}^{-}$ , $ε - Proj K_{X}^{+}$ , and $ε - Proj K_{X}$ .

The first observations about the approximated operators partly mimic the ones we made for the exact operators.
Fact 5.3.
Let X be a computable metric space and $ε > 0$ .
If $0 < ε^{'} < ε$ then $ε - P ⩽_{sW} ε^{'} - P ⩽_{sW} P$ where P is any of $Proj K_{X}^{-}$ , ${Proj}_{X}^{-}$ , $Proj K_{X}^{+}$ , ${Proj}_{X}^{+}$ , $Proj K_{X}$ , ${Proj}_{X}$ .

$K_{X} ⩽_{sW} ε - Proj K_{X}^{-}$ and $C_{X} ⩽_{sW} ε - {Proj}_{X}^{-}$ .

$ε - Proj K_{X}^{-} ⩽_{sW} ε - {Proj}_{X}^{-}$ , $ε - Proj K_{X}^{+} ⩽_{sW} ε - {Proj}_{X}^{+}$ , $ε - Proj K_{X} ⩽_{sW} ε - {Proj}_{X}$ .

If X is computably compact $ε - Proj K_{X}^{-} \equiv_{sW} ε - {Proj}_{X}^{-}$ , $ε - Proj K_{X}^{+} \equiv_{sW} ε - {Proj}_{X}^{+}$ , $ε - Proj K_{X} \equiv_{sW} ε - {Proj}_{X}$ .

$ε - Proj K_{R^{n}}^{+} \equiv_{sW} ε - {Proj}_{R^{n}}^{+}$ , $ε - Proj K_{R^{n}} \equiv_{sW} ε - {Proj}_{R^{n}}$ for $n ⩾ 1$ .

Proof.
(1) and (2) are obvious.

(3) and (4) can be proved exactly as Facts 4.4 and 4.5 respectively: indeed those proofs consist of transformations of the input and do not use any specific feature of the functions involved.

(5) follows from the proofs of the analogous results in Theorem 4.6, since the ε-projection points of x onto the compact sets K and L constructed there are also ε-projection points of x onto the original closed set A. □

Notice that in (5) above $ε - Proj K_{R^{n}}^{-} \equiv_{sW} ε - {Proj}_{R^{n}}^{-}$ is missing – we show below in Proposition 5.5 that this does not hold. The proof of the analogous result in Theorem 4.6 cannot be translated to the approximate setting. Indeed if we repeat that construction then to obtain the ε-projection points of x onto A we need to have a $ε^{'}$ -projection point of x onto H for $\begin{matrix} ε^{'} ⩽ \frac{arctan (d (x, A) (1 + ε))}{arctan (d (x, A))} - 1 . \end{matrix}$ Hence no specific $ε^{'}$ will work for all x and A. Even viewing ε as part of the input we do not solve the problem: from the negative information on A we obtain only lower bounds for $d (x, A)$ .
5.1. Approximated negative projection operators

The following results characterizes the computational complexity of negative approximated projection operators on $R^{n}$ for all $n ⩾ 1$ .

Theorem 5.4.
For every $ε > 0$ and $n ⩾ 1$ , $ε - {Proj}_{R^{n}}^{-} \equiv_{sW} C_{R}$ .
Proof.
For the right-to-left direction, observe that $C_{R} ⩽_{sW} C_{R^{n}} ⩽_{sW} ε - {Proj}_{R^{n}}^{-}$ by Fact 5.3.(2).

For the other direction, consider an input $(x, A) \in dom (ε - {Proj}_{R^{n}}^{-})$ . Since we can compute $d (x, A) \in R_{<}$ , we denote by $r_{s}^{'} \in Q$ the strict lower bound for $d (x, A)$ computed at stage s, so that ${lim}_{s \to \infty} r_{s}^{'} = d (x, A)$ . We set $r_{s} = max {r_{s}^{'}, 0}$ .

We now define the negative closed set $\begin{matrix} B : = {(y, s) : y \in A \land s \in N \land d (x, y) ⩽ (1 + ε) r_{s}} \subseteq R^{n + 1} . \end{matrix}$ To see that we can compute a $ψ_{R^{n}}^{-}$ -name of B observe that B is defined by a $Π_{1}^{0}$ -formula with A as a parameter.

Intuitively, B is constituted by “copies” of different subsets of $A \subseteq R^{n}$ translated onto different levels of the space $R^{n + 1}$ , so that (i) each copy lies at distance 1 from the adjacent copies, (ii) on the s-th level we remove the points of A that are “too far” from x according to the approximation of $(1 + ε) d (x, A)$ that we know at that stage. Notice that the s-th level of B is nonempty if and only if $r_{s} ⩾ \frac{d (x, A)}{1 + ε}$ , and this happens for some s (for all s when $d (x, A) = 0$ ) because $sup {r_{s} : s \in N} = d (x, A)$ . Therefore $B \neq \emptyset$ is a valid input for $C_{R^{n + 1}}$ .

If $(y, s) \in C_{R^{n + 1}} (B)$ , then $y \in ε - {Proj}^{-} (x, A)$ because $d (x, y) ⩽ (1 + ε) r_{s} ⩽ (1 + ε) d (x, A)$ . We have shown $ε - {Proj}_{R^{n}}^{-} ⩽_{sW} C_{R^{n + 1}}$ . Finally $C_{R^{n + 1}} ⩽_{sW} C_{R}$ by [2, Corollary 4.9]. □

For $ε - Proj K_{R^{n}}^{-}$ we only state the bounds given in the following proposition. We recall the use of the finite-parallelization operator that maps any given multi-valued $f : \subseteq X ⇉ Y$ to $f^{} : \subseteq X^{} ⇉ Y^{}$ defined as $f^{} (n, x_{1}, . ., x_{n}) : = {n} \times f (x_{1}) \times \dots \times f (x_{n})$ for all $n \in N$ .
Proposition 5.5.
For every $ε > 0$ and $n ⩾ 1$ , $\begin{matrix} WKL ⩽_{sW} ε - Proj K_{R^{n}}^{-} ⩽_{W} WKL * {LPO}^{} LPO <_{W} C_{R} . \end{matrix}$
Proof.
The first inequality follows from Fact 5.3.(2) and the fact that $WKL \equiv_{sW} K_{R^{n}}$ by [5, Theorem 8.5].

We proceed to show that $ε - Proj K_{R^{n}}^{-} ⩽_{W} WKL * {LPO}^{} LPO$ :

Given an input $(x, K) \in dom (ε - Proj K_{R^{n}}^{-})$ , we can use LPO to decide whether or not $x \in K$ . If yes, we can output x. If no, we can compute a lower bound $2^{- k} < d (x, K)$ . Since we know K as a compact set, we can subsequently compute some $L \in N$ such that $K \subseteq B (x, 2^{- k} {(1 + ε)}^{L + 1})$ . Consider the slices $D_{ℓ} : = {y \in R^{n} ∣ 2^{- k} {(1 + ε)}^{ℓ} ⩽ d (x, y) ⩽ 2^{- k} {(1 + ε)}^{ℓ + 1}}$ , which we can effectively compute as closed sets. We can use ${LPO}^{L}$ to decide for each $ℓ < L$ whether $D_{ℓ} \cap K = \emptyset$ (as we have K, and thus also $D_{ℓ} \cap K$ as a compact set). Let $ℓ_{0}$ be the least positive answer (if it exists), or L otherwise. Then $D_{ℓ_{0}} \cap K$ is available as a non-empty compact set, and each of its elements (chosen by $K_{R^{n}} \equiv_{W} WKL$ ) is a valid output for $ε - Proj K_{R^{n}}^{-} (x, K)$ .

That $WKL * {LPO}^{} LPO ⩽_{W} C_{R}$ is straightforward, e.g. via the independent choice theorem implying the closure under compositional product of the class of non deterministic functions with finitely many mind changes ([2, Theorem 7.6]). To see that this is strict, we observe that $C_{N} ≰_{W} WKL * {LPO}^{} LPO$ . Since the degree of $C_{N}$ admits a single-valued representative (for example unique choice [2]), the closed choice elimination theorem (as stated in [19, Theorem 2.1]) implies that if $C_{N} ⩽_{W} WKL * {LPO}^{} LPO$ , then $C_{N} ⩽_{W} {LPO}^{} LPO$ . That this is impossible can be seen using Hertling’s level [18], which is an ordinal invariant of Weihrauch degrees defined as follows: Given a function f, let $D_{0} = dom (f)$ , let $D_{α + 1}$ be the closure of the set of discontinuity points of $f |_{D_{α}}$ , and for limit ordinal γ, let $D_{γ} = ⋂_{β < α} D_{β}$ . The level of f is the least α such that $D_{α} = \emptyset$ (if this ever happens). The level of $C_{N}$ does not exist [22], whereas ${LPO}^{} LPO$ has level at most $ω \cdot 2$ . □

Notice that our proof shows in fact that $\begin{matrix} ε - Proj K_{X}^{-} ⩽_{W} WKL * {LPO}^{} LPO, \end{matrix}$ and hence $ε - Proj K_{X}^{-} <_{W} C_{R}$ , for every computable metric space X.
5.2. Approximated positive projection operators

Theorem 5.6.
For every $ε > 0$ and $n ⩾ 1$ , $ε - {Proj}_{R^{n}}^{+} ⩽_{W} Sort$ .
Proof.
By Proposition 3.1 it suffices to show that $ε - {Proj}_{R^{n}}^{+} ⩽_{W} {min}_{ω + 1}^{-}$ and by Fact 5.3.1 we can assume that ε is computable. Given $(x, {\overline{{x_{n}}}}_{n}) \in dom (ε - {Proj}_{R^{n}}^{+})$ let $\begin{matrix} A : = {- 2^{- i} : (\forall j) d (x, x_{i}) ⩽ (1 + ε) d (x, x_{j})} \cup {0} . \end{matrix}$ This is a $Π_{1}^{0}$ -condition, hence A is computable from $(x, {\overline{{x_{n}}}}_{n})$ as a nonempty member of $A_{-} (ω + 1)$ .

Let now $z : = {min}_{ω + 1}^{-} (A)$ and notice that:
if $z = - 2^{- i}$ then by the definition of A we have $x_{i} \in ε - {Proj}_{R^{n}}^{+} (x, {\overline{{x_{n}}}}_{n})$ ;

if $z = 0$ then $(\forall i) (\exists j) d (x, x_{j}) < \frac{d (x, x_{i})}{1 + ε}$ and inductively we can prove that for every k there exists n such that $d (x, x_{n}) < \frac{d (x, x_{0})}{{(1 + ε)}^{k}}$ which implies $x \in {\overline{{x_{n}}}}_{n}$ ; hence $ε - {Proj}_{R^{n}}^{+} (x, {\overline{{x_{n}}}}_{n}) = {x}$ .

We need to show that from z and the original input $(x, {\overline{{x_{n}}}}_{n})$ we can compute an effective Cauchy sequence ${(y [s])}_{s}$ converging to a point $y \in ε - {Proj}_{R^{n}}^{+} (x, {\overline{{x_{n}}}}_{n})$ . To compute $y [s]$ set $j_{0} = 0$ and start a recursive procedure which will stop after finitely many steps. Given $j_{k}$ use (the name of) z to check whether there exists $i ⩽ j_{k}$ such that $z = - 2^{- i}$ ; in this case we stop the recursion. If instead $z \neq - 2^{- i}$ for every $i ⩽ j_{k}$ it follows that $- 2^{- j_{k}} \notin A$ and hence there exists $j_{k + 1}$ such that $d (x, x_{j_{k + 1}}) < \frac{d (x, x_{j_{k}})}{1 + ε}$ . Since this is a $Σ_{1}^{0}$ property, we can search for such a $j_{k + 1}$ until we find one. The recursion will stop when either we find $i ⩽ j_{k}$ such that $z = - 2^{- i}$ or we see that $d (x, x_{j_{k}}) < \frac{2^{- s - 3}}{1 + ε}$ (if the first alternative never occurs, such a k exists since ${lim}_{k \to \infty} d (x, x_{j_{k}}) = 0$ because $d (x, x_{j_{k}}) ⩽ \frac{d (x, x_{0})}{{(1 + ε)}^{k}}$ ). In the first case let $y [s] : = x_{i} [s + 3]$ , while in the second case let $y [s] : = x_{j_{k}} [s + 3]$ .

It is clear from the construction that if $z = - 2^{- i}$ and $y [s] = x_{i} [s + 3]$ we have $y [s^{'}] = x_{i} [s^{'} + 3]$ for every $s^{'} ⩾ s$ . This implies that if for some s we have $y [s] = x_{i} [s + 3]$ with $z = - 2^{- i}$ then the sequence ${(y [s])}_{s}$ converges to $x_{i}$ , which belongs to $ε - {Proj}_{R^{n}}^{+} (x, {\overline{{x_{n}}}}_{n})$ by (1) above. If instead for every s the first possibility never occurs it means that $z = 0$ , so that by (2) $ε - {Proj}_{R^{n}}^{+} (x, {\overline{{x_{n}}}}_{n}) = {x}$ , and indeed ${(y [s])}_{s}$ converges to x.

However, the convergence of ${(y [s])}_{s}$ does not suffice, and we need to check that we actually defined an effective Cauchy sequence. For this it suffices to show that $d (y [s], y [s + 1]) < 2^{- s - 1}$ for every s. This is obvious if $z = - 2^{- i}$ , $y [s] = x_{i} [s + 3]$ and $y [s + 1] = x_{i} [s + 4]$ . Now assume that neither $y [s]$ nor $y [s + 1]$ have been defined using $z = - 2^{- i}$ . In other words, $y [s] = x_{j_{k}} [s + 3]$ and $y [s + 1] = x_{j_{h}} [s + 4]$ where $d (x, x_{j_{k}}) < \frac{2^{- s - 3}}{1 + ε}$ and $d (x, x_{j_{h}}) < \frac{2^{- s - 4}}{1 + ε}$ . Then $\begin{array}{l} d (y [s], y [s + 1]) & ⩽ d (x_{j_{k}} [s + 3], x_{j_{k}}) + d (x_{j_{k}}, x) + d (x, x_{j_{h}}) + d (x_{j_{h}}, x_{j_{h}} [s + 4]) \\ < 2^{- s - 3} + \frac{2^{- s - 3}}{1 + ε} + \frac{2^{- s - 4}}{1 + ε} + 2^{- s - 4} < 2^{- s - 1} . \end{array}$ The last possibility (by the observation above) is that $y [s] = x_{j_{k}} [s + 3]$ with $d (x, x_{j_{k}}) < \frac{2^{- s - 3}}{1 + ε}$ and $y [s + 1] = x_{i} [s + 4]$ with $z = - 2^{- i}$ . In this case notice that, since $- 2^{- i} \in A$ , we have $d (x, x_{i}) ⩽ (1 + ε) d (x, x_{j_{k}}) < 2^{- s - 3}$ . Then $\begin{array}{l} d (y [s], y [s + 1]) & ⩽ d (x_{j_{k}} [s + 3], x_{j_{k}}) + d (x_{j_{k}}, x) + d (x, x_{i}) + d (x_{i}, x_{i} [s + 4]) \\ < 2^{- s - 3} + \frac{2^{- s - 3}}{1 + ε} + 2^{- s - 3} + 2^{- s - 4} < 2^{- s - 1} . \end{array}$ □
Theorem 5.7.
For every $ε > 0$ and $n ⩾ 1$ , $Sort ⩽_{sW} ε - {Proj}_{R^{n}}^{+}$ .
Proof.
By Proposition 3.1 it suffices to show that ${min}_{ω + 1}^{-} ⩽_{sW} ε - {Proj}_{R^{n}}^{+}$ .

As usual, it suffices to show the reduction for $n = 1$ . Fix $b \in N$ such that $1 + ε < b$ and notice that $b ⩾ 2$ . Given $A : = (ω + 1) ∖ ⋃_{i \in N} B_{i}$ closed and nonempty in $ω + 1$ , with $B_{0}, B_{1}, B_{2}, \dots$ rational open balls in $ω + 1$ , we compute a sequence ${(x_{n})}_{n}$ in $R$ by setting $x_{n} : = - b^{- k - 1}$ for the least k such that $- 2^{- k} \notin ⋃_{i ⩽ n} B_{i}$ if such a k exists, and otherwise setting $x_{n} : = 0$ .

If $min (A) = 0$ , then $- 2^{- k} \notin A$ for every $k \in N$ , which implies $0 \in {\overline{{x_{n}}}}_{n}$ . Hence $ε - {Proj}_{R}^{+} (0, {\overline{{x_{n}}}}_{n}) = {0}$ .

If instead $min (A) = - 2^{- k}$ then $k \in N$ is the least natural number such that $- 2^{- k} \in A$ and ${\overline{{x_{n}}}}_{n} = {x_{n}}_{n}$ is a discrete subset of the closed interval $[- \frac{1}{b}, - b^{- k - 1}]$ . In fact, for all n, $x_{n} = - b^{- i - 1}$ for some $i ⩽ k$ and, for n sufficiently large, $x_{n} = - b^{- k - 1}$ . This implies that $d (0, {\overline{{x_{n}}}}_{n}) = b^{- k - 1}$ . Moreover, if $x_{n} \neq - b^{- k - 1}$ then $x_{n} = - b^{- i - 1}$ for some $i < k$ and hence $\begin{matrix} (1 + ε) d (0, {\overline{{x_{n}}}}_{n}) < b \cdot d (0, {\overline{{x_{n}}}}_{n}) = b^{- k} ⩽ b^{- i - 1} = d (0, x_{n}) \end{matrix}$ and thus $x_{n} \notin ε - {Proj}_{R}^{+} (0, \overline{{x_{n}}})$ . We thus showed that $ε - {Proj}_{R}^{+} (0, {\overline{{x_{n}}}}_{n}) = {- b^{- k}}$ .

We have proved that $ε - {Proj}_{R}^{+} (0, {\overline{{x_{n}}}}_{n})$ is a singleton and we now show that its unique element y can be used to compute ${min}_{ω + 1}^{-} (A)$ . Given then such $y \in R$ , we produce the $ρ_{ω + 1}$ -name q of ${min}_{ω + 1}^{-} (A)$ in the following way. For each s we check whether $y = - b^{- s - 1}$ or not. Notice that this test is decidable because y belongs to ${- b^{- n - 1} : n \in N} \cup {0} \subseteq R$ and $- b^{- s - 1}$ is not an accumulation point of this set. If the answer is positive, we put $q (s) = 1$ , otherwise $q (s) = 0$ . □
Corollary 5.8.
For every $ε > 0$ and $n ⩾ 1$ , $ε - {Proj}_{R^{n}}^{+} \equiv_{W} Sort$ .
Proof.
By Theorem 5.6 and Theorem 5.7. □
Corollary 5.9.
For every $ε > 0$ and $n ⩾ 1$ , $ε - {Proj}_{R^{n}}^{+} |_{W} ε - {Proj}_{R^{n}}^{-}$ .
Proof.
By Proposition 3.5, Theorem 5.4 and Corollary 5.8. □
5.3. Total approximated projection operators

Our classification of projection operators ends finally with a computable version of projection, that can be therefore used in concrete applications.

Theorem 5.10.
For every $ε > 0$ and $n ⩾ 1$ , $ε - {Proj}_{R^{n}}$ is computable.
Proof.
By Fact 5.3.1 we can assume that ε is computable. We give an algorithm to determine some $y \in ε - {Proj}_{R^{n}} (x, A)$ for every $(x, A) \in R^{n} \times A (R^{n})$ with $A \neq \emptyset$ .

We know already that total information on A allows us to compute $d (x, A)$ , and then $(1 + ε) d (x, A)$ . We construct by induction an approximate projection point of x onto A as follows.

At stage $s ⩾ 0$ we check whether $\begin{matrix} (i) (1 + ε) d (x, A) < 2^{- s - 3} or (ii) d (x, A) > 0 . \end{matrix}$ Notice that at least one of these two conditions holds, and we stop when we verify one of them. If (i) is verified before (ii), we let $y [s] : = x [s + 3]$ , and move to step $s + 1$ . If instead (ii) is verified before (i), we inspect the dense sequence in A searching for some z such that $d (x, z) < (1 + ε) d (x, A)$ (a suitable z always exists in this case) and then let $y [t] = z [t + 1]$ for all $t ⩾ s$ .

We now show that the algorithm works. First we need to check that ${(y [i])}_{i}$ is an effective Cauchy sequence converging to some y, and to this end it suffices to check that $d (y [s], y [s + 1]) ⩽ 2^{- s - 1}$ for all s. This is trivial if at stage s and as well at stage $s + 1$ the condition (i) is satisfied first, or alternatively if (ii) has been verified at some stage $t ⩽ s$ . The interesting case is therefore when (ii) is verified for the first time at stage $s + 1$ . Then $\begin{array}{l} d (y [s], y [s + 1]) & = d (x [s + 3], z [s + 2]) < d (x [s + 3], x) + d (x, z) + d (z, z [s + 2]) \\ < 2^{- s - 3} + (1 + ε) d (x, A) + 2^{- s - 2} < 2^{- s - 1} . \end{array}$

We then need to check that $y \in ε - {Proj}_{R^{n}} (x, A)$ . If (i) has always been verified, then $(1 + ε) d (x, A) = 0 = d (x, y)$ , since $y = x$ . If at stage s (ii) is verified, then $y = z$ where z was picked so that $d (x, z) < (1 + ε) d (x, A)$ . □

6. An application: The Whitney extension theorem

Projection points are often used in mathematics. An example is the Whitney Extension Theorem, originally proved in [31], and dealing with differentiable functions in $R^{n}$ . This theorem considers a real-valued continuous function f defined on a closed $A \subseteq R^{N}$ . Since A is closed, we cannot even attempt to compute the partial derivatives of f at many boundary points of A. However we can have also a set of continuous functions (the pseudo-derivatives of f) defined also on A which satisfy Taylor’s formulas and hence behave like the partial derivatives of degree $⩽ k$ of f (f and this set of functions are collectively called a jet). The Whitney Extension Theorem asserts that under these hypotheses f can be extended to some $g \in C^{k} (R^{n})$ , so that g and its partial derivatives extend the elements of the jet.

A classical proof of the Whitney Extension Theorem is contained in [28, Chapter VI], and we follow Stein’s proof to provide a computable version. Starting with the closed set A, Stein defines a family $F$ of cubes tiling the complement of A and a partition of unity ${(φ_{Q}^{*})}_{Q \in F}$ consisting of smooth functions. For each $Q \in F$ let $P_{Q}$ be a projection point of the center of Q onto A. We then define the $C^{k}$ extension of f by $\begin{matrix} g (x) : = \{\begin{matrix} f (x) & if x \in A; \\ \sum_{Q \in F} f (P_{Q}) φ_{Q}^{*} (x) & if x \notin A . \end{matrix} \end{matrix}$ (Notice that, for a given A and after we fix $F$ , ${(φ_{Q}^{*})}_{Q \in F}$ and ${(P_{Q})}_{Q \in F}$ , in fact we obtain a linear operator from the space of jets to $C^{k} (R^{n})$ .)

If A is given with total information, variations of $F$ and ${(φ_{Q}^{*})}_{Q \in F}$ can be computed. Thus at first sight the only essentially non-computable step (by Proposition 4.20 and Theorem 4.22) in Stein’s proof is the choice of ${(P_{Q})}_{Q \in F}$ . To overcome this obstacle $P_{Q}$ can be replaced with some other point of A which is close enough to Q, and “close enough” depends only from the size of Q. This suggests that the multi-valued functions naturally associated to the Whitney Extension Theorem are actually computable without resorting to any projections. However there is another, subtler, point that needs to be taken into account. In fact, in the definition by cases of g given above the case distinction is not computable. Thus we need to provide an effective way, given x and A, to compute $g (x)$ without knowing whether $x \in A$ . Here the projection operators, which are defined over $R^{n}$ , come back into the picture and appear to be essential: when we do not know positively that $x \notin A$ they are used to compute $g (x)$ in a way that is compatible with both cases. Only by showing that approximate projections are indeed sufficient it is possible to find a computable version of the Whitney Extension Theorem.

Summing up, assuming A is represented with total information and using Theorem 5.10, we show that the multi-valued function associated to the Whitney Extension Theorem is computable. As mentioned in the introduction, full details of this result will be included in a forthcoming paper [17].

Footnotes

Acknowledgements

Marcone’s research partially supported by PRIN 2012 Grant “Logica, Modelli e Insiemi” and by the departmental PRID funding “HiWei – The higher levels of the Weihrauch hierarchy”.

References

E.P.

Astor,

D.D.

Dzhafarov,

Solomon and

Suggs, The uniform content of partial and linear orders, Ann. Pure Appl. Logic168(6) (2017), 1153–1171. doi:10.1016/j.apal.2016.11.010.

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

Dillhage, Computability of finite-dimensional linear subspaces and best approximation, Ann. Pure Appl. Logic162(3) (2010), 182–193. doi:10.1016/j.apal.2010.09.011.

Brattka and

Gherardi, Borel complexity of topological operations on computable metric spaces, Jour. Log. and Comp.19(1) (2009), 45–76. doi:10.1093/logcom/exn027.

Brattka and

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

Brattka and

Gherardi, Effective choice and boundedness principles in computable analysis, Bull. Symbolic Logic17(1) (2011), 73–117. doi:10.2178/bsl/1294186663.

Brattka,

Gherardi and

Hölzl, Probabilistic computability and choice, Inform. and Comput.242 (2015), 249–286. doi:10.1016/j.ic.2015.03.005.

Brattka,

Gherardi and

Hölzl, Las Vegas computability and algorithmic randomness, in: 32nd International Symposium on Theoretical Aspects of Computer Science, LIPIcs. Leibniz Int. Proc. Inform., Vol. 30, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2015, pp. 130–142+1 unnumbered page.

Brattka,

Gherardi,

Hölzl and

Pauly, The Vitali covering theorem in the Weihrauch lattice, in: Computability and Complexity: Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday,

Day,

Fellows,

Greenberg,

Khoussainov,

Melnikov and

Rosamond, eds, Springer International Publishing, Cham, 2017, pp. 188–200, https://doi.org/10.1007/978-3-319-50062-1_14 . ISBN 978-3-319-50062-1. doi:10.1007/978-3-319-50062-1_14.

10.

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.

11.

Brattka,

Gherardi and

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

Brattka and

Hertling, eds, Springer International Publishing, To appear. arXiv:1707.03202.

12.

Brattka and

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

13.

Brattka and

Presser, Computability on subsets of metric spaces, Theoret. Comput. Sci.305(1–3) (2003), 43–76, Topology in computer science (Schloß Dagstuhl, 2000). doi:10.1016/S0304-3975(02)00693-X.

14.

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.

15.

Fefferman, Whitney’s extension problems and interpolation of data, Bull. Amer. Math. Soc. (N.S.)46(2) (2009), 207–220. doi:10.1090/S0273-0979-08-01240-8.

16.

Gherardi and

Marcone, How incomputable is the separable Hahn–Banach theorem?, Notre Dame J. Form. Log.50(4) (2009), 393–425(2010). doi:10.1215/00294527-2009-018.

17.

Gherardi and

Marcone, The Whitney Extension Theorem is computable, In preparation.

18.

Hertling, Unstetigkeitsgrade von Funktionen in der effektiven Analysis, PhD thesis, Fernuniversität, Gesamthochschule in Hagen, 1996.

19.

Le Roux and

Pauly, Finite choice, convex choice and finding roots, Log. Meth. Comp. Sci.11(4:6) (2015), 1–30, https://lmcs.episciences.org/1607 . doi:10.2168/LMCS-11(4:6)2015.

20.

Neumann, Computational problems in metric fixed point theory and their Weihrauch degrees, Log. Methods Comput. Sci.11(4) (2015), 4:20, 44. doi:10.2168/LMCS-11(4:20)2015.

21.

Neumann and

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

22.

Pauly, Methoden zum Vergleich der Unstetigkeit von Funktionen, Masters Thesis, FernUniversität Hagen, 2007.

23.

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

24.

Pauly, How incomputable is finding Nash equilibria?, J.UCS16(18) (2010), 2686–2710.

25.

Pauly, On the topological aspects of the theory of represented spaces, Computab.5(2) (2016), 159–180, https://content.iospress.com/articles/computability/com049 . doi:10.3233/COM-150049.

26.

Pauly,

Fouché and

Davie, Weihrauch-completeness for layerwise computability, Logical Methods in Computer Science14 (2018). doi:10.23638/LMCS-14(2:11)2018.

27.

Schröder, Admissible Representations for Continuous Computations, Informatik Berichte, Vol. 299, FernUniversität Hagen, 2003.

28.

E.M.

Stein, Singular Integrals and Differentiability Properties of Functions, Princeton Mathematical Series, No. 30, Princeton University Press, Princeton, N.J., 1970, xiv+290.

29.

N.R.

Tavana and

Weihrauch, Turing machines on represented sets, a model of computation for analysis, Log. Methods Comput. Sci.7(2) (2011), 2:19, 21. doi:10.2168/LMCS-7(2:19)2011.

30.

Weihrauch, Computable Analysis, Texts in Theoretical Computer Science. An EATCS Series, Springer-Verlag, Berlin, 2000, x+285. ISBN 3-540-66817-9. doi:10.1007/978-3-642-56999-9.

31.

Whitney, Analytic extensions of differentiable functions defined in closed sets, Trans. Amer. Math. Soc.36(1) (1934), 63–89. doi:10.2307/1989708.

Projection operators in the Weihrauch lattice

Abstract

Keywords

1. Introduction

2.1. Representations

Definition 2.1 (Computable metric spaces).

Definition 2.2 (Closed set representations).

2.3. Some milestones in the Weihrauch lattice

2 The introduction of the compositional product as a specific function is more involved (see [12], [11, Definition 5.3]) and not relevant for this paper.

Footnotes

Acknowledgements

References

²
The introduction of the compositional product as a specific function is more involved (see [12], [11, Definition 5.3]) and not relevant for this paper.