# Three topological reducibilities for discontinuous functions

## Abstract

We define a family of three related reducibilities, , and for arbitrary functions , where , is a compact separable metric space. The classes mostly coincide with the proper Baire classes. We show that certain -equivalence functions -jump are in their Baire class. Within the Baire 1 functions, we completely characterize the degree structure associated to -minimal and finding an exact match to the , 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 Reference 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 These different reducibilities reflect different oracle access mechanisms for the computation of . from 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 but also include the use of -completeness, to demonstrate that classical isomorphism problems like the classification of countable abelian groups cannot have reasonable invariants (Downey-Montalbán -completenessReference DM08), Ziegler reducibility to classify algebraic closures of finitely presented groups (see e.g. Higman-Scott Reference HS88), truth-table reducibility to analyze algorithmic randomness for continuous measures (Reimann-Slaman Reference RS), and enumeration reducibility for the relativized Higman embedding theorem (see Reference 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 or similar.

What if instead we wanted to compare the information content of functions The collection ? 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 where , 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.Footnote^{1}

We first concentrate upon what we define to be This reduction is interpreted to mean that . is continuously Weihrauch reducible to the *parallelization* of 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 and 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 degrees of the Baire functions are linearly ordered, and these degrees correspond to the proper Baire classes. Our main results concern the and degrees. We show that the jump operator thFootnote^{2} is in its Baire class. -minimal

Then we restrict attention to the Baire 1 functions. In Reference KL90, Kechris and Louveau consider three ranking functions , and which take Baire 1 functions to countable ordinals. These ranks are especially robust at levels of the form , Letting . denote the least such that in our main theorem we characterize the , and degrees of the Baire 1 functions as follows.

The smallest are recognizable classes: constant functions, continuous functions, upper semi-continuous functions, and lower semi-continuous functions. See Figure -degrees2.

### 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 if and only if for some continuous These reducibilities are applied in various combinations to the problem of discontinuous functions, for example in .Reference Her96bReference Bra05Reference Myl06Reference Pau10Reference Car13. What all these reducibilities have in common is that the outputs of the functions and 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 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 Reference 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 Reference 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 Reference 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 Reference EKV16, which was not known to the authors at the time this work was done. They defined a generalization of the , and ranks of Reference KL90 into the higher Baire classes. Interestingly, they were able to apply their extension of the 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 stages -trueReference Mon14 which produced continuous functions of the type required by our 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 Reference Kih15 for a list). They used the relativized stages technique as one of several key ingredients -trueReference DM19.

Around the same time, the authors realized that the stages could be replaced with an appeal to a result made famous by Louveau and Saint-Raymond -trueReference LSR87Reference LSR88, 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 Reference LSR87Reference LSR88 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 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 -true6.4. Indeed, in 2021 the first author, with collaborators Greenberg, Harrison-Trainor, and Turetsky, announced success in this endeavor Reference 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

### 2.1. Weihrauch/computable reducibility

Suppose we want to define for functions and with the meaning that , can compute The search for a natural notion of . leads directly to Weihrauch reducibility. For it is clear what it means to “know” , An algorithm or oracle knows . if, given input it outputs , Accordingly, a computation of . from is an algorithm which can answer these questions about when given query access to an oracle for So, what kinds of questions should we be able to answer if we claim to “know” . At a minimum, an oracle for ? ought to be able to produce when given input We take this ability as the defining feature of an oracle for . .

Now, what should it mean for an algorithm to have query access to an oracle for Clearly, given input ? the algorithm should be able to pass it through and query , If . were the only permitted query, the algorithm could not really be said to have access to an oracle for all of so we should allow some other queries as well. For example, one would hope for a theory in which the functions , and always compute each other, where is a computable real. Generalizing this idea, an algorithm with query access to should be able to ask about for any Therefore, the notion of Weihrauch reducibility is a natural starting candidate for a notion of . Roughly speaking, . is Weihrauch reducible to ( if ) can be computed by a machine with oracle access to where , 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 Reference BG11, whereas earlier Weihrauch had called it computable reducibility. Brattka Reference 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 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 oracle.

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

^{3}

Imagine for the purposes of this hypothetical that is an operator on so that a joining operation , 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 should do. Instead of querying with an input we query with a pair , where , Instead of returning the entire . the oracle returns some , with Now an algorithm which on input . has made finitely many queries to has only acquired a finite amount of new information, so its future queries are still restricted to those with This breaks the cycle above. In order to get more and more precision on . such an algorithm may query , for many different values of But there are at most countably many queries to . associated to the computation of a single Therefore, we can naturally express the kind of reducibility described above in the Weihrauch framework: . could mean where , is the *parallelization* of defined by applying , componentwise.

### 2.3. What is a single bit of information about ?

Accepting parallelized Weihrauch reducibility as a higher-type notion of what should , and be? It is particularly informative to consider In classical computability theory, . means that there is an algorithm which, on input outputs , such that 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 to within seems unfair, ruling out ”) between functions of disjoint ranges that are otherwise computationally identical. (Notions of -computations without point (2) have been considered however, for example by Hertling -reducibilityReference Her96b, Pauly Reference Pau10 and Carroy Reference 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 notion equivalent to parallelized Weihrauch reducibility. An oracle for accepts as input a triple with , and and , answers the question “is -approximately The exact version of this question would be too precise for a computable procedure, so we accept any answer as correct if ”? Now that each query to the oracle yields exactly one bit of information, we can define . and 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 we usually allow integer parameters in computation procedures. Therefore, for reductions between objects of type , 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 to mean and make similar topological definitions for , and 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 denote a canonical pairing function identifying with The expression . refers to an string of -length Concatenation of finite or infinite strings ’s. and is denoted by which may be shortened to , in cases where it would cause no confusion. If is a string with a single entry we also denote concatenation by , or The . column of an element is denoted .

The composition of two functions and is denoted If multiplication is intended, the notation . is used. We usually use and to denote compact separable metric spaces, to denote elements of or , to denote subsets of and , to denote subsets of Usually . and , are arbitrary functions from to (the ones whose complexity we seek to categorize), while and are typically continuous functions from to .

### 3.2. Computability and descriptive set theory

We assume the reader is familiar with Kleene’s (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 Reference Sac90. The jump of a set th is denoted For any . if , then let denote and if , is infinite then let denote If . with we will often simply write , instead of Thus an expression like . 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 if it is open, if it is the complement of a set, and if it is of the form where each is for some Then a set . is if and only if there is a parameter and an index such that for all ,

(and if no parameter is needed, we say is ).

Still, at least once we will want to refer to the sets where , is a limit ordinal. In this case, we write to denote .

### 3.3. Representations

Although our results were motivated by considering they are also applicable in a wider context. If the domain of , is any compact separable metric space,Footnote^{4} 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 Reference Wei00, and a more up-to-date survey is Reference BGP17.

^{4}

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 Reference 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 or For example, an element of . could be coded by a rapidly Cauchy sequence of rational numbers (which is itself coded by an element of using some fixed computable bijection 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 is a partial function so that elements , have -names (strictly a set Note that ). can have many names and not every element of , is a name. Then if and are represented spaces and we say , is *computable* if there is a computable function such that whenever is a name for then , is a name for We say that . *realizes* Because . and 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 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 is *admissible* if is continuous and for every other continuous there is a continuous function , such that for all we have , That is, . transforms to -names Observe that it is possible to continuously transform a base 10 name for -names. into a Cauchy name for but not vice versa. Some definition chasing shows that the Cauchy name representation for , is admissible. Restricting attention to admissible representations allows continuity properties of to be reflected in its realizers.

All of the pain and suffering involving representations is rewarded when we want to compare functions and in topologically incompatible areas, like Cantor space and When comparing . and we can do so ,*via their representations in .* Given two represented spaces and a ,*Weihrauch problem* is a multivalued partial function The . indicated that this definition concerns multivalued partial functions. We will restrict attention to single-valued functions 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 then we say that , is *Weihrauch reducible* to written , if and only there are computable functions , such that for all if , then , We say . is *strongly Weihrauch reducible* to written , if , can be replaced by above. The notions of *continuous Weihrauch reducibility* and *continuous strong Weihrauch reducibility*, denoted and respectively, are obtained by allowing and to be merely continuous rather than computable.

Let be represented spaces with representations and and suppose , One can then compare . with other functions using Weihrauch reducibility by composing it with the given representations. So in particular can be identified with the multivalued function defined so that if and only if and Of course, different choice of representations may in general result in different Weihrauch complexity of the function . so some care is needed in the most general case. However, if , and 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.)

The parallelization is the function that applies countably many times simultaneously: .

In this paper, we will be dealing for the most part with situations where the coding is clear, and hence suppress the notation whenever possible. In particular, unless otherwise specified, if then , 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; with each continuous. More generally, let be a compact separable metric space. By we mean the continuous functions , The Baire hierarchy of functions on . is defined as follows. Let For each . let , be the set of functions which are pointwise limits of sequences of functions from The functions in . are also referred to as the Baire functions when is clear.

It is well-known that a function on a separable metrizable space is Baire if and only if the inverse image of each open set under is Reference Kec95, Theorems 24.10 & 24.3. When the Baire , functions can also be characterized via the jump.

### 3.5. Ranks on Baire 1 functions

In Reference KL90, Kechris and Louveau defined three ranks , and 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 the following derivation process is used to define the , rank. Given rational numbers with and a closed set let ,

For a fixed pair define an , sequence -length as follows. Let , and , if is a limit ordinal. Since is separable, it has a countable basis, so the sequence must stabilize below Let . be the least such that one can show that such ; exists if and only if is Baire 1.

Finally, the rank is defined by The . and ranks are also defined by different transfinite derivation processes. Kechris and Louveau show that the levels of the form are especially robust in the following sense.

## 4. Topological Turing reducibility on

First we define the topological Turing reducibility as mentioned in Section 1. First we give the definition for the special case where .

Equivalently, if and only if there is a countable sequence of continuous functions and a continuous function such that whenever are Cauchy names for , is a Cauchy name for Observe that all continuous functions are equivalent under . .

The restriction of the domain to is not essential, but helps keep the notation manageable. If is a compact separable metrizable space and then in order to compare , with other functions, we may replace with where , is any total admissible representation. It is well-known that every compact metric space 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 whose domain is a subset of , and which maps an input string , to an open ball as follows. Let , Given that . has been defined, let be a large enough number and let be a finite sequence of points of such that the balls cover the topological closure of Then define, for each . , Now, given . it is clear that if , and then ,