Three topological reducibilities for discontinuous functions

Abstract

We define a family of three related reducibilities, $\leq _{\mathbf{T}}$, $\leq _{\mathbf{tt}}$ and $\leq _{\mathbf{m}}$, for arbitrary functions $f,g:X\rightarrow \mathbb{R}$, where $X$ is a compact separable metric space. The $\equiv _{\mathbf{T}}$-equivalence classes mostly coincide with the proper Baire classes. We show that certain $\alpha$-jump functions $j_\alpha :2^\omega \rightarrow \mathbb{R}$ are $\leq _{\mathbf{m}}$-minimal in their Baire class. Within the Baire 1 functions, we completely characterize the degree structure associated to $\leq _{\mathbf{tt}}$ and $\leq _{\mathbf{m}}$, finding an exact match to the $\alpha$ hierarchy introduced by Bourgain [Bull. Soc. Math. Belg. Sér. B 32 (1980), pp. 235–249] and analyzed in Kechris & Louveau [Trans. Amer. Math. Soc. 318 (1990), pp. 209–236].

1. Introduction

1.1. Reducibilities

Computability theory seeks to understand the effective content of mathematics. Ever since its beginnings in the work of Gödel, Turing, Post, Kleene, Church and others, the idea of a reduction has been a central notion in this area. Turing Tur39 formalized what we now call Turing reducibility which can be viewed as the most general way of allowing computation of one set of natural numbers from another using oracle queries.

In the last 60 years, we have seen the introduction of a large number of reducibilities $A\le B$. These different reducibilities reflect different oracle access mechanisms for the computation of $A$ from $B$. Different oracle access mechanisms give different equivalence classes calibrating computation. The measure of the efficacy of such reductions is the extent to which

(i)

they give insight into computation, and

(ii)

they are useful in mathematics.

Examples of (ii) above include the use of polynomial time reductions to enable the theory of $NP$-completeness, but also include the use of $\Pi _1^1$-completeness to demonstrate that classical isomorphism problems like the classification of countable abelian groups cannot have reasonable invariants (Downey-Montalbán DM08), Ziegler reducibility to classify algebraic closures of finitely presented groups (see e.g. Higman-Scott HS88), truth-table reducibility to analyze algorithmic randomness for continuous measures (Reimann-Slaman RS), and enumeration reducibility for the relativized Higman embedding theorem (see HS88). There are many other examples.

1.2. Reducibilities in type II computation

The narrative above really only refers to notions of relative computability for infinite bit sequences (or objects, such as real numbers, which can be coded by such sequences). That is, the objects whose information content is being compared have function type $A:\omega \rightarrow \omega$ or similar.

What if instead we wanted to compare the information content of functions $f:[0,1]\rightarrow \mathbb{R}$? The collection $\mathcal{F}([0,1])$ of all such functions has cardinality greater than the continuum, so it is not possible to use infinite bit sequences to code all these objects. In Section 2 we will say a bit more about some approaches to the problem of relative computability for higher type objects, the most prominent of which is the Weihrauch computable reducibility framework.

In this paper, we introduce and analyze three notions of reduction for $\mathcal{F}(X)$, where $X$ is a compact Polish space. Two of our notions are completely new and one has had little previous attention. We argue that that they meet the criteria (i) and (ii) above, and provide computational insight into the hierarchies previously introduced in classical analysis for the classification of the Baire classes of functions.⁠¹

¹

We define these terms in Section 3.

✖

We first concentrate upon what we define to be $f\le _{\mathbf{T}} g$. This reduction is interpreted to mean that $f$ is continuously Weihrauch reducible to the parallelization of $g$. In Section 2, we define what we mean by this, and argue that this is the most natural (continuous) analog of Turing reducibility for higher type objects. We introduce the new notions of $f\leq _{\mathbf{tt}} g$ and $f\leq _{\mathbf{m}} g$ by restricting the oracle use of the functionals in the Weihrauch reduction in an appropriate way described in Section 5.

It seems to be folklore that the $\leq _{\mathbf{T}}$ degrees of the Baire functions are linearly ordered, and these degrees correspond to the proper Baire classes. Our main results concern the $\leq _{\mathbf{m}}$ and $\leq _{\mathbf{tt}}$ degrees. We show that the $\alpha$th jump operator⁠² $j_\alpha$ is $\leq _{\mathbf{m}}$-minimal in its Baire class.

²

We will define $j_\alpha$ later, but for example $j_1:2^\omega \rightarrow \mathbb{R}$ is $j_1(X) \coloneq \sum _{i \in X'} 2^{-(i+1)}$.

✖

Theorem 1.1.

If a Baire function $f$ is not Baire $\alpha$, then $f \geq _{\mathbf{m}} j_{\alpha +1}$ or $f \geq _{\mathbf{m}} -j_{\alpha +1}$.

Then we restrict attention to the Baire 1 functions. In KL90, Kechris and Louveau consider three ranking functions $\alpha$, $\beta$ and $\gamma$, which take Baire 1 functions to countable ordinals. These ranks are especially robust at levels of the form $\omega ^\xi$. Letting $\xi (f)$ denote the least $\xi$ such that $\alpha (f) \leq \omega ^\xi$, in our main theorem we characterize the $\leq _{\mathbf{m}}$ and $\leq _{\mathbf{tt}}$ degrees of the Baire 1 functions as follows.

Theorem 1.2.

For $f$ and $g$ discontinuous Baire 1 functions,

(1)

$f\leq _{\mathbf{tt}} g$ if and only if $\xi (f) \leq \xi (g)$.

(2)

If $|f|_\alpha < |g|_\alpha$, then $f\leq _{\mathbf{m}} g$.

(3)

If $\nu$ is a limit ordinal, $\{f: |f|_\alpha = \nu \}$ is an $\leq _{\mathbf{m}}$-degree.

(4)

If $\nu$ is a successor, $\{f: |f|_\alpha = \nu \}$ contains exactly four $\leq _{\mathbf{m}}$-degrees arranged as in Figure 1.

The smallest $\leq _{\mathbf{m}}$-degrees are recognizable classes: constant functions, continuous functions, upper semi-continuous functions, and lower semi-continuous functions. See Figure 2.

1.3. History and subsequent related work

Several authors have previously considered various notions of reducibility to compare discontinuous functions. The most commonly considered are continuous Weihrauch reducibility, strong continuous Weihrauch reducibility, and a rigid form of Wadge reducibility defined by $f \leq _w g$ if and only if $f = g\circ h$ for some continuous $h$. These reducibilities are applied in various combinations to the problem of discontinuous functions, for example in Her96bBra05Myl06Pau10Car13. What all these reducibilities have in common is that the outputs of the functions $f$ and $g$ are considered as indivisible packets of information. By contrast, in this paper, we make rigorous the notion of one “bit” of information about the output of such a function, and this choice is what makes possible the correspondence with the $\alpha$ rank.

As there has been some gap between the time this work was done and the present time, we include a short note about how it developed over time and some work which followed it. Almost all results of this paper were obtained by the authors in 2015 and 2016 while the third author was a postdoctoral fellow at the University of Victoria Wellington. The first major presentation of these results was made by the third author at the February 2017 Dagstuhl Workshop on Computability Theory. At that time, Takayuki Kihara and Arno Pauly each suggested some equivalent definitions; we have included them, with credit as appropriate, and included proofs of their equivalence.

As communicated in multiple correspondences beginning in the summer of 2017, Kihara took some of the main results of the paper and generalized them in various ways. The generalizations, under the additional assumption of AD, extended Theorem 1.2 (about Baire 1 functions) and the folklore Proposition 4.10 (about Baire functions) to apply to all real-valued functions on Polish spaces. The generalization goes in two directions, extending both the complexity of the functions considered and the class of domains considered. (Following KL90, the present paper only considered compact Polish spaces as the domains of the functions.) In order to do the more substantial generalization to make these results apply to all functions regardless of complexity, Kihara incorporated diverse techniques including his recent analysis with Montalbán of the Wadge degrees of bqo-valued functions KM19, as well as older theory surrounding the uniform Martin’s conjecture. We will note these extensions as appropriate, and refer the reader to Kihara’s forthcoming paper Kih for details.

In the same paper, Kihara also clarifies the relationship between the results of this paper and the work of Elekes, Kiss and Vidnyánszky EKV16, which was not known to the authors at the time this work was done. They defined a generalization of the $\alpha$, $\beta$ and $\gamma$ ranks of KL90 into the higher Baire classes. Interestingly, they were able to apply their extension of the $\beta$ rank to solve an open problem in cardinal characteristics.

The original proof of Theorem 1.1 was done by a relativization of Montalbán’s theory of $\alpha$-true stages Mon14 which produced continuous functions of the type required by our $\leq _{\mathbf{m}}$ reductions. In early 2019, the first author presented a sketch of the argument at UCLA, prompting a collaboration with Andrew Marks. In summer 2019 they announced a resolution, conditional on some mild determinacy, to the longstanding Decomposability Conjecture (which was conjectured by several authors—see Kih15 for a list). They used the relativized $\alpha$-true stages technique as one of several key ingredients DM19.

Around the same time, the authors realized that the $\alpha$-true stages could be replaced with an appeal to a result made famous by Louveau and Saint-Raymond LSR87LSR88, which is Proposition 6.4 in this paper. Proposition 6.4 itself is a straightforward consequence of Borel determinacy, but the work of Louveau and Saint-Raymond revealed that this result actually holds in second-order arithmetic. An important consequence is that Borel Wadge determinacy also holds in second-order arithmetic. The arguments of LSR87LSR88 were notorious for being impenetrable, but something like Proposition 6.4 had essentially been achieved in the original version of this paper via the relativized $\alpha$-true stages technique, a technique which can be carried out in second-order arithmetic. The question then naturally arose whether this technique could give a more understandable second-order arithmetic proof of Proposition 6.4. Indeed, in 2021 the first author, with collaborators Greenberg, Harrison-Trainor, and Turetsky, announced success in this endeavor DGHTT21.

Because the method of the original proof played a role in these developments, we have included it in Appendix A. To cut down on space and improve readability, only the finite case is included.

2. Motivations in defining $\le _{\mathbf{T}}$

2.1. Weihrauch/computable reducibility

Suppose we want to define $f\le g$ for functions $f$ and $g$, with the meaning that $g$ can compute $f$. The search for a natural notion of $f\le g$ leads directly to Weihrauch reducibility. For $A,B \in 2^\omega$, it is clear what it means to “know” $A$. An algorithm or oracle knows $A$ if, given input $n$, it outputs $A(n)$. Accordingly, a computation of $A$ from $B$ is an algorithm which can answer these questions about $A$ when given query access to an oracle for $B$. So, what kinds of questions should we be able to answer if we claim to “know” $f:[0,1]\rightarrow \mathbb{R}$? At a minimum, an oracle for $f$ ought to be able to produce $f(x)$ when given input $x$. We take this ability as the defining feature of an oracle for $f$.

Now, what should it mean for an algorithm to have query access to an oracle for $g$? Clearly, given input $x$, the algorithm should be able to pass it through and query $g(x)$. If $g(x)$ were the only permitted query, the algorithm could not really be said to have access to an oracle for all of $g$, so we should allow some other queries as well. For example, one would hope for a theory in which the functions $x\mapsto f(x)$ and $x\mapsto f(x+c)$ always compute each other, where $c$ is a computable real. Generalizing this idea, an algorithm with query access to $g$ should be able to ask about $g(y)$ for any $y\leq _T x$. Therefore, the notion of Weihrauch reducibility is a natural starting candidate for a notion of $f \le g$. Roughly speaking, $f$ is Weihrauch reducible to $g$ ($f\leq _W g$) if $f(x)$ can be computed by a machine with oracle access to $g(\Delta (x))$, where $\Delta$ is some fixed computable operation. We refer the reader to Section 3.3 for the full definition.

The name “Weihrauch reducibility” was coined by Brattka and Gherardi BG11, whereas earlier Weihrauch had called it computable reducibility. Brattka Bra05 proved effective versions of classical theorems linking the Borel and Baire hierarchies using this reducibility.

2.2. Parallelized Weihrauch reducibility

The above account seems to miss the feature of ordinary $\leq _T$ computation in which the algorithm may use the oracle repeatedly and interactively. We would not like to limit the reduction algorithm to a single use of the $g$ oracle.

However, if the algorithm had access to all of $g(x)$ based on its first query, it would be able to feed this back into the $g$ oracle, obtaining $g(g(x))$ and in general the sequence of $g^{(n)}(x)$. And if we accept some algorithm is uniformly producing the sequence $g^{(n)}(x)$, it could be simultaneously engaged in writing down a summarizing output $g^{(\omega )}(x)$, where $g^{(\omega )}(x)$ is for example defined as $\bigoplus _n g^{(n)}(x)$.⁠³ So we are led to accept $g^{(\omega )} \le g$. If we accept this, and also wish our notion to be transitive, we must accept $g^{(\omega +1)} \le g$, otherwise transitivity will be violated in the sequence $g^{(\omega +1)} \le (g^{(\omega )} \oplus g) \le g$. In the end, we are forced to say $g$ computes all its iterates up to $\omega _1^{ck}$. The notion just described, complete with all the transfinite iteration, was studied by Kleene Kle59. However, this reducibility is coarser than we want (for example, we would not want the jump operator on $2^\omega$ to be able to compute the double-jump operator) and so we choose to go by another route.

³

Imagine for the purposes of this hypothetical that $g$ is an operator on $2^\omega$, so that a joining operation $\oplus$ is available to us; a similar situation could be concocted for operators on the unit interval.

✖

Suppose instead we make the following seemingly minor adjustment to our concept of what an oracle for $g$ should do. Instead of querying $g$ with an input $\Delta (x)$, we query with a pair $(\Delta (x),\varepsilon )$, where $\varepsilon \in \mathbb{Q}^+$. Instead of returning the entire $g(\Delta (x))$, the oracle returns some $p \in \mathbb{Q}$ with $|g(\Delta (x)) -p|<\varepsilon$. Now an algorithm which on input $x$ has made finitely many queries to $g$ has only acquired a finite amount of new information, so its future queries are still restricted to those $y$ with $y \leq _T x$. This breaks the cycle above. In order to get more and more precision on $f(x)$, such an algorithm may query $g(y)$ for many different values of $y$. But there are at most countably many queries to $g$ associated to the computation of a single $f(x)$. Therefore, we can naturally express the kind of reducibility described above in the Weihrauch framework: $f \le g$ could mean $f \leq _{W} \hat{g}$, where $\hat{g}:X^\omega \rightarrow Y^\omega$ is the parallelization of $g$, defined by applying $g$ componentwise.

2.3. What is a single bit of information about $f$?

Accepting parallelized Weihrauch reducibility as a higher-type notion of $\leq _T$, what should $\leq _{tt}$ and $\leq _m$ be? It is particularly informative to consider $\leq _m$. In classical computability theory, $A\leq _m B$ means that there is an algorithm which, on input $n$, outputs $m$ such that $A(n) = B(m)$. For us the important features are:

(1)

The oracle’s response is accepted unchanged as the output, and

(2)

The question is a yes/no question.

Allowing a more demanding question (such as “approximate $f(x)$ to within $\varepsilon$”) seems unfair, ruling out $m$-computations between functions of disjoint ranges that are otherwise computationally identical. (Notions of $m$-reducibility without point (2) have been considered however, for example by Hertling Her96b, Pauly Pau10 and Carroy Car13.)

Our previous decision on how to finitize the oracle was, upon reflection, rather arbitrary. We could restrict ourselves to yes/no questions with the following convention about oracles, and still end up with a $\leq _T$ notion equivalent to parallelized Weihrauch reducibility. An oracle for $f$ accepts as input a triple $(x,p,\varepsilon )$, with $p \in \mathbb{Q}$ and $\varepsilon \in \mathbb{Q}^+$, and $\varepsilon$-approximately answers the question “is $f(x) < p$”? The exact version of this question would be too precise for a computable procedure, so we accept any answer as correct if $|f(x) - p| < \varepsilon$. Now that each query to the oracle yields exactly one bit of information, we can define $\leq _m$ and $\leq _{tt}$ for the higher type objects by placing corresponding restrictions on the oracle use. We give the formal definitions in Section 5.

2.4. Parameters

Another natural question we might ask ourselves is “what parameters would be reasonable for such reductions”? For reductions between objects of type $A:\omega \rightarrow \omega$, we usually allow integer parameters in computation procedures. Therefore, for reductions between objects of type $f:[0,1]\rightarrow \mathbb{R}$, perhaps we should allow real parameters. We take this approach, which has a substantial simplifying effect. Every continuous function is computable relative to a real parameter, so Weihrauch computability relative to a real parameter is the same as continuous Weihrauch reducibility, the formal definition of which can be found in Section 3. Therefore, our reducibilities have a topological rather than computational character. In particular, we shall define $f \leq _{\mathbf{T}} g$ to mean $f \leq _W^c \hat{g}$, and make similar topological definitions for $\leq _{\mathbf{tt}}$ and $\leq _{\mathbf{m}}$ in Section 5. We plan to address the question of the lightface theory in future work.

3. Preliminaries

3.1. Notation

We use standard computability-theoretic notation. Brackets $\langle m, n \rangle$ denote a canonical pairing function identifying $\omega \times \omega$ with $\omega$. The expression $0^\omega$ refers to an $\omega$-length string of $0$’s. Concatenation of finite or infinite strings $\sigma$ and $\tau$ is denoted by $\sigma ^{\frown }\tau$, which may be shortened to $\sigma \tau$ in cases where it would cause no confusion. If $\tau$ is a string with a single entry $n$, we also denote concatenation by $n^{\frown } \sigma$ or $\sigma ^{\frown } n$. The $n$ column of an element $X \in \omega ^\omega$ is denoted $X^{[n]}$.

The composition of two functions $f$ and $g$ is denoted $fg$. If multiplication is intended, the notation $f \cdot g$ is used. We usually use $X$ and $Y$ to denote compact separable metric spaces, $A,B,Z,W$ to denote elements of $2^\omega$ or $\omega ^\omega$, $C,D,P,Q$ to denote subsets of $2^\omega$, and $\mathcal{C}, \mathcal{D}$ to denote subsets of $\mathcal{P}(X)$. Usually $f,g$, and $j$ are arbitrary functions from $X$ to $\mathbb{R}$ (the ones whose complexity we seek to categorize), while $h,k,u,v,H$ and $K$ are typically continuous functions from $\omega ^\omega$ to $\omega ^\omega$.

3.2. Computability and descriptive set theory

We assume the reader is familiar with Kleene’s $\mathcal{O}$ (but without it, one could still understand the results at the finite levels of each of the hierarchies). The standard reference on this subject is Sacks Sac90. The $n$th jump of a set $A \in \omega ^\omega$ is denoted $A^{(n)}$. For any $a \in \mathcal{O}^A$, if $|a| = n$ then let $A_{(a)}$ denote $A^{(n)}$, and if $|a|$ is infinite then let $A_{(a)}$ denote $H_{2^a}^A$. If $a \in \mathcal{O}$ with $|a| = \alpha$, we will often simply write $\alpha$ instead of $a$. Thus an expression like $A_{(\alpha )}$ is technically ambiguous, but since all the sets which it could refer to are one-equivalent, no problems will arise.

The reason for numbering the jumps in this lower-subscript way is to make them align correctly with the Borel hierarchy. Recall that a set is $\mathbf{\Sigma }^0_1$ if it is open, $\mathbf{\Pi }^0_\alpha$ if it is the complement of a $\mathbf{\Sigma }^0_\alpha$ set, and $\mathbf{\Sigma }^0_{\alpha }$ if it is of the form $\cup _{n \in \omega } C_n$ where each $C_n$ is $\mathbf{\Pi }^0_{\beta _n}$ for some $\beta _n < \alpha$. Then a set $C \subseteq \omega ^\omega$ is $\mathbf{\Sigma }^0_\alpha$ if and only if there is a parameter $Z \in \omega ^\omega$ and an index $i$ such that for all $A \in \omega ^\omega$,

$$\begin{equation*} A \in C \iff i \in (A \oplus Z)_{(\alpha )} \end{equation*}$$

(and if no parameter is needed, we say $C$ is $\Sigma ^0_\alpha$).

Still, at least once we will want to refer to the sets $H_a^A$, where $|a|$ is a limit ordinal. In this case, we write $A^{(a)}$ to denote $H_a^A$.

3.3. Representations

Although our results were motivated by considering $f:[0,1]\to {\mathbb{R}}$, they are also applicable in a wider context. If the domain of $f$ is any compact separable metric space,⁠⁴ then computations using this domain can be carried out through the theory of represented spaces. Hence, for completeness, we will briefly give an account of such spaces. A standard reference is Weihrauch Wei00, and a more up-to-date survey is BGP17.

⁴

The setting of compact separable metric spaces is surely not the most general domain which could be considered. We thank the anonymous referee for pointing out that one could consider Polish spaces, Quasi-Polish spaces, or even drop the condition of separability. Although we do not consider those generalizations here, we refer the reader to Kih for the generalizations of many of the results of this paper to Baire space and general Polish spaces.

✖

In order for a machine to interact with a mathematical object, the object must be coded in a format a machine can read, such an element of $2^\omega$ or $\omega ^\omega$. For example, an element of $\mathbb{R}$ could be coded by a rapidly Cauchy sequence of rational numbers (which is itself coded by an element of $\omega ^\omega$ using some fixed computable bijection $\omega \leftrightarrow \mathbb{Q}$). It is not too hard to see that a similar method will also work for any computable metric space, where the role of the rationals is taken by (codes for) a computable dense subset.

A representation of a space $X$ is a partial function $\delta :\subseteq \omega ^\omega \to X$, so that elements $x\in X$ have $\delta$-names $A_x$ (strictly a set $\{A_x\mid \delta (A_x)=x\}$). Note that $x$ can have many names $A_x$, and not every element of $\omega ^\omega$ is a name. Then if $X$ and $Y$ are represented spaces and $f:X\rightarrow Y$, we say $f$ is computable if there is a computable function $F:\omega ^\omega \rightarrow \omega ^\omega$ such that whenever $A_x$ is a name for $x$, then $F(A_x)$ is a name for $f(x)$. We say that $F$ realizes $f$. Because $x$ and $f(x)$ each have many names, in general realizers are not unique.

Not all representations are created equal. For example, the base 10 representation for reals is a valid representation according to the above definition, but the function $f(x)=3x$ is not computable with respect the base 10 representation on both sides (what digit should the algorithm output first when seeing input .33333…?). However, it is computable with respect to the Cauchy name representation on both sides. This difference is captured in the following definition: a representation $\delta :\subseteq \omega ^\omega \rightarrow X$ is admissible if $\delta$ is continuous and for every other continuous $\delta ':\subseteq \omega ^\omega \rightarrow X$, there is a continuous function $G:\subseteq \omega ^\omega \rightarrow \omega ^\omega$ such that for all $A \in \operatorname {dom} \delta '$, we have $\delta (A) = \delta '(G(A))$. That is, $G$ transforms $\delta '$-names to $\delta$-names. Observe that it is possible to continuously transform a base 10 name for $x$ into a Cauchy name for $x$, but not vice versa. Some definition chasing shows that the Cauchy name representation for $\mathbb{R}$ is admissible. Restricting attention to admissible representations allows continuity properties of $f$ to be reflected in its realizers.

Theorem 3.1 (Kreitz and Weihrauch KW85, Schröder Sch02).

If $X$ and $Y$ are admissibly represented separable $T_0$ spaces, then a partial function $f:\subseteq X\to Y$ has a continuous realizer if and only if $f$ is continuous.

All of the pain and suffering involving representations is rewarded when we want to compare functions $f$ and $g$ in topologically incompatible areas, like Cantor space and ${\mathbb{R}}$. When comparing $f:X\to Y$ and $g:U\to V$, we can do so via their representations in $\omega ^\omega$. Given two represented spaces $X$ and $Y$, a Weihrauch problem is a multivalued partial function $f: X \rightrightarrows Y$. The $\rightrightarrows$ indicated that this definition concerns multivalued partial functions. We will restrict attention to single-valued functions $f:X\rightarrow \mathbb{R}$. Note, however, that each real number has many names.

We conclude this section with the precise definition of Weihrauch reducibility on represented spaces. First, if $f,g\subseteq \omega ^\omega \rightrightarrows \omega ^\omega$, then we say that $f$ is Weihrauch reducible to $g$, written $f \leq _W g$, if and only there are computable functions $\Delta , \Psi :\subseteq \omega ^\omega \rightarrow \omega ^\omega$ such that for all $A \in \operatorname {dom}(f)$, if $B \in g(\Delta (A))$, then $\Psi (A,B) \in f(A)$. We say $f$ is strongly Weihrauch reducible to $g$, written $f \leq _{sW} g$, if $\Psi (A,B)$ can be replaced by $\Psi (B)$ above. The notions of continuous Weihrauch reducibility and continuous strong Weihrauch reducibility, denoted $\leq _{W}^c$ and $\leq _{sW}^c$ respectively, are obtained by allowing $\Delta$ and $\Psi$ to be merely continuous rather than computable.

Let $X,Y$ be represented spaces with representations $\delta _X$ and $\delta _Y$, and suppose $f:\subseteq X \rightrightarrows Y$. One can then compare $f$ with other functions using Weihrauch reducibility by composing it with the given representations. So in particular $f$ can be identified with the multivalued function $F:\subseteq \omega ^\omega \rightrightarrows \omega ^\omega$ defined so that $B \in F(A)$ if and only if $\delta _X(A) \in \operatorname {dom}(f)$ and $\delta _Y(B) \in f(\delta _X(A))$. Of course, different choice of representations may in general result in different Weihrauch complexity of the function $F$, so some care is needed in the most general case. However, if $\delta _X$ and $\delta _Y$ are admissible representations, which representation is chosen does not matter, as the following well-known proposition shows. (We show it only for the continuous Weihrauch reducibility, as that is what is used in this paper, but similar statements could be made for Weihrauch reducibility and computably admissible representations.)

Proposition 3.2.

Suppose $X$ and $Y$ are represented spaces and $f:\subseteq X \rightrightarrows Y$. If $\delta _X, \delta _X'$ are admissible representations for $X$ and $\delta _Y,\delta _Y'$ are admissible representations for $Y$, then $F \equiv _{sW}^c F'$, where $B \in F(A)$ if and only if $\delta _X(A) \in \operatorname {dom}(f)$ and $\delta _Y(B) \in f(\delta _X(A))$, and similarly for $F'$ but using $\delta _X', \delta _Y'$.

Proof.

By symmetry it suffices to show that $F \leq _{sW}^c F'$. By admissibility, let $\Delta$ be such that $\delta _X'\circ \Delta = \delta _X$, and let $\Psi$ be such that $\delta _Y \circ \Psi = \delta _Y'$.

■

The parallelization $\hat{g}:Z^\omega \rightarrow W^\omega$ is the function that applies $g$ countably many times simultaneously: $\hat{g}( (z_i)_{i\in \omega }) = (g(z_i))_{i\in \omega }$.

In this paper, we will be dealing for the most part with situations where the coding is clear, and hence suppress the $\delta _X$ notation whenever possible. In particular, unless otherwise specified, if $X \subseteq \mathbb{R}$, then $\delta _X$ is the Cauchy representation discussed in the previous subsection.

3.4. Baire functions

Baire functions are the most tractable functions we might consider after continuous ones. Baire 1 functions are those which are defined as pointwise limits of a countable collection of continuous functions; $f(x)=\lim _s f_s(x)$ with each $f_s$ continuous. More generally, let $X$ be a compact separable metric space. By $\mathcal{C}(X)$, we mean the continuous functions $f:X\rightarrow \mathbb{R}$. The Baire hierarchy of functions on $X$ is defined as follows. Let $\mathcal{B}_0(X) = \mathcal{C}(X)$. For each $\alpha >0$, let $\mathcal{B}_{\alpha }(X)$ be the set of functions which are pointwise limits of sequences of functions from $\cup _{\beta <\alpha } \mathcal{B}_\beta (X)$. The functions in $\mathcal{B}_\alpha (X)$ are also referred to as the Baire $\alpha$ functions when $X$ is clear.

It is well-known that a function $f$ on a separable metrizable space $X$ is Baire $\alpha$ if and only if the inverse image of each open set under $f$ is $\mathbf{\Sigma }^0_{\alpha +1}$ Kec95, Theorems 24.10 & 24.3. When $X =2^\omega$, the Baire $\alpha$ functions can also be characterized via the jump.

Proposition 3.3 (Folklore).

For each ordinal $\alpha$ and $f:2^\omega \rightarrow \mathbb{R}$, $f \in \mathcal{B}_\alpha (2^\omega )$ if and only if there is a Turing functional $\Gamma$ and $B \in 2^\omega$ such that

$$\begin{equation*} f(A) = \delta _{\mathbb{R}}\Gamma ((A\oplus B)_{(\alpha )}). \end{equation*}$$

Proof.

When such $\Gamma$ and $B$ exist, one can readily check that the inverse images of open sets are $\mathbf{\Sigma }^0_{\alpha +1}$. Conversely, if $f$ is Baire $\alpha$, then the sets $f^{-1}((p,q))$ for $p,q \in \mathbb{Q}$ can each be written as

$$\begin{equation*} f^{-1}((p,q)) = \{A: i_{p,q} \in (A \oplus B_{p,q})_{(\alpha +1)}\}. \end{equation*}$$

Therefore, if $B$ is an oracle containing each $B_{p,q}$ and $i_{p,q}$ in a uniformly accessible manner, one can use an $(A\oplus B)_{(\alpha )}$ oracle to enumerate the rational intervals $(p,q)$ containing $f(A)$, which is enough to make a Cauchy name for $f(A)$.

■

3.5. Ranks on Baire 1 functions

In KL90, Kechris and Louveau defined three ranks $\alpha$, $\beta$ and $\gamma$ on the Baire 1 functions. These ranks had been used either explicitly or implicitly in the literature analyzing this class of functions. Given a Baire 1 function $f:X\rightarrow \mathbb{R}$, the following derivation process is used to define the $\alpha$ rank. Given rational numbers $p,q$ with $p<q$ and a closed set $P \subseteq X$, let

$$\begin{equation*} P'_{p,q} = P \setminus \cup \{U \subseteq X: U \text{ is open and } f(U) \subseteq (p, \infty ) \text{ or } f(U) \subseteq (-\infty ,q)\}. \end{equation*}$$

For a fixed pair $p,q$, define an $\omega _1$-length sequence $\{P_\nu \}_{\nu < \omega _1}$ as follows. Let $P_0 = X$, $P_{\nu + 1} = (P_\nu )'_{p,q}$, and $P_{\nu } = \cap _{\mu < \nu } P_\mu$ if $\nu$ is a limit ordinal. Since $X$ is separable, it has a countable basis, so the sequence must stabilize below $\omega _1$. Let $\alpha (f,p,q)$ be the least $\nu$ such that $P_\nu = \emptyset$; one can show that such $\nu$ exists if and only if $f$ is Baire 1.

Finally, the $\alpha$ rank is defined by $\alpha (f) = \sup _{p<q} \alpha (f,p,q)$. The $\beta$ and $\gamma$ ranks are also defined by different transfinite derivation processes. Kechris and Louveau show that the levels of the form $\omega ^\nu$ are especially robust in the following sense.

Theorem 3.4 (KL90).

For any countable $\xi$ and any bounded Baire 1 function $f$,

$$\begin{equation*} \alpha (f) \leq \omega ^\xi \iff \beta (f) \leq \omega ^\xi \iff \gamma (f) \leq \omega ^\xi . \end{equation*}$$

4. Topological Turing reducibility on $2^\omega$

First we define the topological Turing reducibility as mentioned in Section 1. First we give the definition for the special case where $X = 2^\omega$.

Definition 4.1.

For $f,g: 2^\omega \rightarrow \mathbb{R}$, let $f \leq _{\mathbf{T}} g$ if $f \leq _{W}^c \hat{g}$.

Equivalently, $f \leq _{\mathbf{T}} g$ if and only if there is a countable sequence of continuous functions $k_i:2^\omega \rightarrow 2^\omega$ and a continuous function $h:\subseteq 2^\omega \rightarrow 2^\omega$ such that whenever $\{B_i\}_{i<\omega }$ are Cauchy names for $\{g(k_i(A))\}_{i<\omega }$, $h(A \oplus \bigoplus _{i<\omega } B_i)$ is a Cauchy name for $f(A)$. Observe that all continuous functions are equivalent under $\leq _{\mathbf{T}}$.

The restriction of the domain to $2^\omega$ is not essential, but helps keep the notation manageable. If $X$ is a compact separable metrizable space and $f:X\rightarrow \mathbb{R}$, then in order to compare $f$ with other functions, we may replace $f$ with $f\delta _X: 2^\omega \rightarrow \mathbb{R}$, where $\delta _X:2^\omega \rightarrow X$ is any total admissible representation. It is well-known that every compact metric space $X$ has a total admissible representation. We give one standard and simple example. This example will also come in handy later.

We recursively define a function $L$, whose domain is a subset of $2^\omega$, and which maps an input string $\sigma$ to an open ball $L(\sigma ) = B(x_\sigma , \varepsilon _\sigma ) \subseteq X$, as follows. Let $L(\langle \rangle ) = X$. Given that $L(\sigma )$ has been defined, let $r$ be a large enough number and let $\langle x_{\sigma \tau } \rangle _{\tau \in 2^r}$ be a finite sequence of points of $L(\sigma )$ such that the balls $B(x_{\sigma \tau }, 2^{-|\sigma |})$ cover the topological closure of $L(\sigma )$. Then define, for each $\tau \in 2^r$, $L(\sigma \tau ) = B(x_{\sigma \tau }, 2^{-|\sigma |})$. Now, given $A \in 2^\omega$, it is clear that if $\sigma _1 \prec \sigma _2 \prec A$ and $\sigma _1,\sigma _2 \in \operatorname {dom}(L)$, then