key: cord-0046127-a0xr7e5e
authors: Downey, Rodney G.; Melnikov, Alexander G.
title: Computable Analysis and Classification Problems
date: 2020-06-24
journal: Beyond the Horizon of Computability
DOI: 10.1007/978-3-030-51466-2_9
sha: 1dd218c416f18b2da28138cb8201b85af63718f4
doc_id: 46127
cord_uid: a0xr7e5e

Suppose we are given a collection of mathematical objects such as the class of connected compact Polish groups or the set of all real numbers which are normal to some base.

Suppose we are given a collection of mathematical objects such as the class of connected compact Polish groups or the set of all real numbers which are normal to some base. Is there a reasonable classification of these objects (e.g. by invariants)? One nice property expected from a useful classification is that it makes the classified objects easier to handle algorithmically. Even if the general classification of a class of objects is impossible, sometimes there is a useful hierarchy of objects in this class, e.g., the Cantor-Bendixson rank of a scattered Polish space, the Ulm type of a reduced abelian p-group, etc. We would expect that the algorithmic, algebraic, or topological complexity of objects increase from lower to higher levels of a hierarchy. Can you make this intuition formal? Is it possible to formally measure the algorithmic complexity of a given classification or a hierarchy, or perhaps show that there is no reasonable classification at all? Can algorithmic tools help us to define useful hierarchies?

In the present article we discuss several recent works in computable analysis which are related to classification. The main underlying theme here is applying computability theory to a classification problem or a hierarchy; neither the problem nor the hierarchy has to be computability-theoretic. The discussed results can be informally split into three categories: I. Local effective classifications. Given some classical metric or Banach space we ask which elements of the space satisfy a certain property. For example: Which real numbers are normal? Which continuous functions are regular? And so on. II. Global effective classifications. How hard is it to classify, say, compact Polish groups? What about compact Polish spaces? To answer these questions formally we extend methods of computable structure theory to computable separable spaces. III. Applications of computability to hierarchies. Usually elements of higher levels of a given hierarchy are expected to be more complex. Computability theory can be used to make this intuition formal. Such results are clearly related to (I), but there are also explicit connections with Weihrauch reducibility and with theme II.

These three themes above are closely related and no firm line can be drawn between any two of them. We begin our discussion with the second global scheme (II) and a certain related hierarchy. Then we discuss the local theme (I) and finish with more on local hierarchies (III).

There has been a lot of applications of computability theoretic techniques to classification problems in countable algebra; see [19, 31] . A few years ago Melnikov [26] proposed that methods of computable structure theory can be extended to computable separable spaces. We will see that some of these methods can be used to measure the classification problems for classes of separable spaces. We first look at the simpler case of Polish metric spaces, and then we discuss Banach spaces and Polish groups.

To apply methods of computable structure theory we need to make the standard notion of a computable Polish space [5, 34, 37] look more familiar to a computable algebraist. A structure on a Polish space

The open diagram D + (α) of a structure α : ω → M is the collection of Gödel numbers of all elementary facts of the form d(α(i), α(j)) < r and d(α(i), α(j)) > q which hold on M, where i, j range over ω and q, r over Q. We say that α is computable if D + (α) is a computably enumerable set 1 . We return to classification. Fix some class K of Polish spaces. First, suppose our task is to classify computable members of K. Fix a uniformly computable list of all partially computable structures on Polish spaces: α 0 , α 1 , α 2 , . . . , where each computable structure α i is identified with its c.e. open diagram D + (α i ).

The complexity of the classification problem for computable members of K is measured using the following two index sets:

1. The characterisation problem for computable members of K:

2. The isomorphism problem for computable members of K:

where ∼ = stands for isometric isomorphism. Computable members of a class K of Polish metric spaces admit an effective classification (up to isometric isomorphim) if both I(K) and E(K) are hyperarithmetic.

Remark 2. Note that ∼ = does not stand for computable isometric isomorphism. Of course, if we wish to classify our spaces up to homeomorphism or quasi-isometry (etc.) then we should adjust the interpretation of ∼ = accordingly. Definition 1 is an adaptation of a similar method proposed in [19] for countable discrete computable structures. Cenzer and Remmel [10] used index sets to measure the complexity of various properties of Π 0 1 -classes. Although there is not much in common between their results and the theorems discussed in the present article, it is important that index sets had been used in computable analysis long before us.

To extend these methods beyond computable Polish spaces we use relativisation. A structure α : ω → M is computable relative to X if D + (α) is computably enumerable relative to X. Using structures computable relative to an oracle X, relativise the definitions of I(K) and E(K) to X; the resulting sets will be denoted I X (K) and E X (K). Usually, when we establish that, say, I(K) ∈ Σ 0 n , we can apply relativisation to show I X (K) ∈ Σ X n , and similarly for E X (K). Recall this means that, for some recursive scheme R, we have

where X is a set-parameter. It follows that the number of alternations of quantifiers in (∃x 1 ) . . . (Q n x n )R(X; x 1 , . . . , x n , i) is an invariant of the whole class. This motivates the following: Definition 3. We say that that K admits an effective classification if, for every oracle X, both I X (K) and E X (K) belong to a some (fixed) level of the hyperarithmetical hierarchy relativised to X.

The First Results. Perhaps, the first non-trivial illustration of the proposed approach to classification in the literature is the theorem below. [29] ). The class K comp of compact Polish metric spaces admits an effective classification.

The proof of Theorem 4 relies on ideas of of Gromov [21] and L ω1ωdefinability. The most important step of the proof is establishing that every computable compact Polish metric space is Δ 0 3 -categorical ; the categoricity hierarchy will be discussed in the next subsection. Theorem 4 contrasts with: [33] ). The characterisation problem for computable locally compact Polish metric spaces is Π 1 1 -complete.

It follows that for a given Polish space M, deciding if it is locally compact is as hard as just checking the Π 1 1 definition of local compactness. Thus, the class of locally compact Polish metric spaces does not admit an effective classification. The result formally confirms our intuition that locally compact spaces are very hard to classify.

The Categoricity Hierarchy. We use the standard notion of a computable map between computable Polish spaces; see, e.g., [26] . The definition below extends the classical notion of computable categoricity [1] to Polish spaces.

A Polish space M is computably categorical if for any two computable structures α and β on M there is an isometric isomorphism between cl(α) and cl(β) computable with respect to α and β 2 .

Examples of computably categorical spaces include [26]: every Polish space associated to a separable Hilbert space, Cantor space with the usual ultrametric, and the Urysohn space. If we generalise Definition 6 by allowing the isomorphism to be Δ 0 α , the resulting notion of a Δ 0 α -categorical space is a direct adaptation of the classical notion of Δ 0 α -categoricity from computable algebra [1] . How is this technical notion related to classification? If every member of K is Δ 0 α -categorical and I(K) is hyperarithmetical then E(K) is hyperarithmetical too 3 . Our results tend to be easily relativizable to any oracle X, and thus both I X (K) and E X (K) will usually be hyperarithmetical relative to X as well. This approach was used by Melnikov and Nies [29] to prove Theorem 4. Clearly, Δ 0 α -categoricity induces a hierarchy, and using a transformation from graphs to Polish spaces [20] it is not hard to show that the hierarchy is proper in general.

We will return to discussing Δ 0 α -categorcity later. First we discuss another natural relativisation of Definition 6. It reveals a connection between first-order definability and computable categoricity of spaces, in the spirit of [1] . We say that a computable Polish space M = cl(α i ) i∈ω is relatively computably categorical if any (not necessarily computable) structure (β i ) i∈ω computes an isometry from cl(β i ) i∈ω onto cl(α i ) i∈ω . Greenberg, Knight, Melnikov, and Turetsky [20] showed: Problem 8. Extend Theorem 7 to relative Δ 0 α -categoricity. For that, an adequate formal definition of relative Δ 0 α -categoricity must be designed.

Banach spaces. All Banach spaces in this section are separable. What is the most natural general approach to computability on Banach spaces? Pour El and Richards [34] restrict themselves only to computable structures which also compute the standard vector space operations. The well-known result of Mazur and Ulam (can be found in [35] ) implies that there is only one way to define the operations consistently with a given norm so that we get a complete normed space. Does the result of Mazur and Ulam hold computably? If the answer was "yes" then the definition from Pour El and Richards [34] would be an overkill. Interestingly, Melnikov and Ng [30] showed that the effective version of Mazur-Ulam fails for the space of continuous functions on the unit interval.

Problem 9. Give an optimal effective analysis of Mazur-Ulam.

In the context of the present article, the above-mentioned result of Melnikov and Ng justifies the use of the definition below which is of course equivalent to the approach in Pour-El and Richards [34] .

A separable Banach space B is computable if the associated metric space admits a computable structure which computes the vector space operations on B.

In the case of Banach spaces (over R) we modify Definitions 1 and 3 using the natural enumeration of all (partially) computable countable normed spaces B 0 , B 1 , . . .. The relativisation principle still applies to this approach. To save space we omit the definition; see [6] . Now to the results.

Lebesgue Spaces. Suppose we are given a computable Banach space B. How hard is it to determine whether B is a Lebesgue space? In other words, what is the complexity of the characterisation problem (Definition 1) for Lebesgue spaces? The crude upper bound involves searching for a (separable) measure space Ω and a real p which makes the space look like L p (Ω). The well-known Kakutani-Bohnenblus characterisation of Lebesgue spaces in terms of Banach lattices [4, 22] does not seem to be of much help either. Brown, McNicholl and Melnikov [6] have proven the following rather surprising result: Theorem 11 (Brown et al. [6] ). The characterisation problem for Lebesgue spaces is Π 0 3 .

How to reduce the unclassifiable brute-force complexity down to Π 0 3 ? Using a non-trivial and novel technique, McNicholl [24] proved that for a computable real p, p is Δ 0 2 -categorical 5 . The proof of Theorem 11 extends these techniques to arbitrary Lebesgue spaces and combines them with new ideas. We see that Δ 0 α -categoricity helps again, though indirectly.

Question 12 ([6] ). Is the bound Π 0 3 from Theorem 11 tight?

The main obstacle in simplifying the upper bound is related to: A Computable Characterisation of C[0,1]. Suppose we are given a description of a (separable) Banach space B. How hard is it to determine whether it is isomorphic to some fixed Banach space C? Within the proposed framework, we can set K = {C} and measure the complexity of the effective characterisation problem {e : cl(B e ) ∼ = C}. For example, the separable Hilbert space 2 admits a low level arithmetical characterisation: use the parallelogram law and compute a basis [34] . Also, various natural Lebesgue spaces such as 3 admit arithmetical characterisations, with some index sets complete at proper difference levels such as d-Σ 0 2 [6] . [19] . Nonetheless, such estimates seem to be more common in computable analysis. For example, suppose p ≥ 1 is a computable real other than 2. Then the isomorphism problem for the class of L p spaces is co-3-Σ 0 3 -complete [6] .

Recall that C[0, 1] is universal among all separable Banach spaces. Building on the earlier work in [30] and [7] , Franklin et al. [17] have recently announced the following unexpected result:

Again, the result can be relativised to any oracle, but here it is not that important since C[0, 1] is computable. The main technical lemma in the proof states that C[0, 1] is Δ 0 5 -categorical.

Calculate optimal bounds for the characterisation problem and Δ 0 ncategoricity of C[0, 1]. 6 Currently, the best known uniform upper bound is Δ 0 2 [6] . McNicholl [25] has recently announced a partial positive solution for the case when p > 2, but he also announced that the uniformity of computing p fails. Thus, we conjecture that the upper bound in Theorem 11 is tight. 7 Such examples exist for Polish spaces, as follows from [20] . Polish Groups. Following Melnikov and Montalbàn [28] , we say that a (metrized) Polish group is computable if it admits a computable structure that computes the standard · and −1 on the group 8 . Fix a uniform enumeration (G e ) e∈ω of all partially computable Polish groups. The definitions of the characterisation problem and the isomorphism problem (Definition 1) should be adjusted accordingly. We note however that this approach seems best suited for compact groups. This is because compactness and totality of a (potential) group operation are both low-level arithmetical properties [27] . Thus, in the compact case the index sets I(K) and E(K) will reflect the complexity of K rather than some pathologies of coding.

Recall that compact Polish spaces admit an effective classification (Theorem 4). How hard is it to classify compact Polish groups? Every compact Polish group G contains the largest connected subgroup H which makes G/H profinite. Thus, the classes of connected and profinite groups are central to the general theory of Polish groups. [27] ).

connected compact abelian groups are both Σ 1 1 -complete.

As usual, the result can be relativised to any oracle. It follows that recognising whether a given group is profinite or connected compact is not that hard (Π 0 2and Π 0 3 -complete, resp.), but the isomorphism problem is too hard even in the abelian case. In contrast with the previous results, the main tool in the proof of Thm 20 is not Δ 0 α -categoricity 9 . Instead, Melnikov proves a computable version of the celebrated Pontryagin duality which is then used to apply effective algebraic results [14, 16] to topological groups. Provably, the duality is effective only when passing from discrete to compact groups [27] , but this half-effectivity was sufficinent. What is the complexity of the Pontryagin dual of a computable compact connected abelian group? (The profinite case is known.) 8 Computability of the metric is obviously not enough. Unlike the Banach space case, there is nothing like the Mazur-Ulam theorem for topological groups. For example, every separable profinite group is homeomorphic to the computable Cantor space, but obviously not every profinite group is computable. Perhaps, computability of −1 can be dropped at least in some cases, but this has not yet been explored. 9 But there is again a tight connection with categoricity. Melnikov [27] showed that the characterisation problem for computably categorical recursive profinite abelian groups Π 0 4 -complete; see [27] for the definitions.

A Local Approach to Global Classification. We must emphasise that the subdivision of the discussed results into local and global is somewhat subjective. For instance, Melnikov and Montalbán [28] have suggested an intermediate approach.

Recall that a transformation space is a Polish space together with a smooth action of a Polish group on the space. The key observation is that the standard S ∞ -transformation space of countable structures in a given finite language is actually computable [28] . Thus, the global classification problem for countable structures becomes a local classification problem for points in a transformation space. The use of topological groups sometimes makes proofs easier. For instance, a technical result of Montalbán [32] characterises uniformly computably categorical structures (categorical relative to all oracles) in terms of infinitary Scott sentences. Using transformation groups and the old result of Effros [15] , the rather tricky argument from [32] can be simplified and generalised at the same time:

Theorem 22. Let (X, G, a) be a (not necessarily computable) transformation group, and x ∈ X. The following are equivalent:

1.

x is uniformly computably categorical on a cone; 2. the orbit of x is Π 0 2 . The theorem above is an explicit link between Polish groups, the Borel hierarchy, the categoricity hierarchy, and classification problems. 

Suppose M is a computable Polish space, such as C[0, 1] or the reals 11 . Fix some property P of points in M, and consider the index set I(P ) = {e : x e satisfies P } of P , where (x e ) e∈ω is an effective enumeration of all (partially) computable points in M. If the complexity of I(P ) is no simpler than the naive bruteforce upper bound derived from the definition of P , then we can conjecture that members of the space having property P do not admit any reasonable classification. Such results are usually relativisable to any oracle. For example, Becher, Heiber, and Slaman [3] showed that the index set of all computable real numbers normal to base 2 is Π 0 3 -complete 12 . Their proof is relativizable, and thus implies the earlier result of Ki and Linton [23] who showed that the set of reals normal to base 2 is Π 0 3 -complete. Becher and Slaman [9] later extended their techniques to show that the index set of numbers computable to some base is Σ 0 4 -complete, and again the result can be fully relativised to any oracle.

Westrick [38] gives a detailed index set analysis of Kechris and Woodin's differentiability hierarchy for continuous functions in C [0, 1] . She showed that the index set of rank ≤ α computable functions in C[0, 1] is Π 0 2α+1 -complete, where α is any computable ordinal.

The index set I(P ) does not have to use the enumeration of all computable members in a class. For example, we could instead start with a uniform enumeration of all polynomial time computable points (l e ) e∈ω of the space; if we can still prove a completeness result restricted to (l e ) e∈ω then this means that the property "x is polynomial time computable" does not help to characterise when P holds on x. We illustrate this approach by a non-trivial example. Following [11] , we call f ∈ C[0, 1] regular to base 2 if the graph of f coded as a pair of binary strings is recognised by a Büchi automation. Regular continuous functions are Lipschitz and also map rationals to rationals in linear time. Using quantifier elimination one can express "f is regular" as a Σ 0 2 -statement about f . Franklin et al. [17] have recently announced:

Remark 25. Working independently, Gorman et al. [18] have announced that every continuous regular function has to be affine outside a measure 0 nowhere dense set. This property can be added to the list of properties in the theorem above too.

It follows that none of the properties of regular functions known to date helps to reduce the complexity of the definition of regularity.

So far our "local" results were restricted to continuous functions. If we want to extend the ideas beyond continuity, we need more ideas. We might have some hope for reasonable classes of functions such as the Baire classes. Recall that f is Baire class 0 iff it is continuous, and f is called Baire n + 1 iff there is a collection {f i | i ∈ N} of Baire class n functions such that f (x) = lim n f n (x), and this extends to limit ordinals in the obvious way. Baire 1 functions are precisely the derivatives of differentiable functions. Baire functions are all Lebesgue measureable, and any Lebesgue measureable function is the same as a Baire 2 function except on a set of measure 0. Can we say more? In the below, we will concentrate on classification for the Baire class functions.

Recall that Weihrauch reducibility [2] is defined as f ≤ W g to mean there are computable h, k such that f (x) = h(x, g(k(x))). A more general version of this is called parallel Weihrauch reducibility. The idea is that to compute f (x) to within 2 −n we might explore g(y), yet for f (x) to within 2 −m perhaps g(y ). For this new reduction we will write f ≤ T g.

Remark 26. This is motivated as follows. It is not reasonable to expect that for a general reduction we should have a uniform map like ≤W which takes arguments of f pointwise to arguments of g determining the reduction. Turing reduction on sets, A ≤T B, can use many queries to B to determine A(n). In the case of continuous functions this can be viewed as as the "parallelisation" of g; replace g with ω many copies of g. See [13] for a clarification.

Example 27. Consider the α-th jump function, j α (x)(i) = x (α) (i), where x (α) (i) is 0 if Φ x i (i) does not halt and 1 otherwise. Then it is possible to show that j 1 (x) ≤ T S 0 where S 0 is the step function which is 0 below 0 and 1 above.

In [13] Day, Downey and Westrick instigated an analysis of the classification of Baire functions using ≤ T . In that paper, they allowed real parameters, the boldface version ≤ T . It is easy to show that f is Baire α iff f ≤ T j α . Using recursion-theoretic techniques, Day, Downey and Westrick [13] have proved: Theorem 28. If α is a constructive ordinal and a Baire function f is not Baire α then j α+1 ≤ T f , and if f is limit, and f is not Baire β for β < α, either f ≡ T j α , or j α < T f .

In [13] , Day, Downey and Westrick refined ≤ T to look at analogs of mand tt-reductions; we omit the definitions 13 .The idea being that Post's Theorem (for example) puts Σ 0 m complete sets above the other Σ 0 m sets via an m-reduction. We state the following satisfying classification result These new reductions had reflections in results from classical analysis to give computable "explanations" for classical results. In [13] Day et al. showed (classical) Baire and Bourgain hierarchies of functions intertwine with the degree structures above. Kihara (to appear) has recently extended the results above.

As we see the boldface version gives real insight into classical investigations, but it might be argued that a finer classification could be obtained using no parameters. This is still an open challenge. Lots of open problems remain, particularly what would be the correct notion for lightface versions.

Computable Structures and the Hyperarithmetical Hierarchy

Borel complexity of topological operations on computable metric spaces

Normal numbers and the Borel hierarchy

An axiomatic characterization of Lp-spaces

A tutorial on computable analysis

On the complexity of classifying lebesgue spaces

Computable Structure Theory on Banach Spaces. ProQuest LLC

Analytic computable structure theory and L p spacespart 2 Archive for Mathematical Logic

On the normality of numbers to different bases

Index sets in computable analysis

Regular real analysis

Analytic computable structure theory and L p spaces

Three topological reducibilities for discontinuous functions

The isomorphism problem for torsion-free abelian groups is analytic complete

Transformation groups and C * -algebras

Constructive Models. Siberian School of Algebra and Logic

Continuous functions and effective classification

Continuous regular functions. Preprint

Computable structure and antistructure theorems

Uniform procedures in uncountable structures

Metric structures for Riemannian and non-Riemannian spaces. Modern Birkhäuser Classics

Concrete representation of abstract L-spaces and the mean ergodic theorem

Normal numbers and subsets of N with given densities

Computable copies of p

Computing the exponent of a Lebesgue space

Computable topological groups and Pontryagin duality

Computable Polish group actions

The classification problem for compact computable metric spaces

Computable structures and operations on the space of continuous functions

Computability theoretic classifications for classes of structures

A robuster Scott rank

Local compactness for computable polish metric spaces is π 1 1 -complete

Computability in Analysis and Physics. Perspectives in Mathematical Logic

General topology. Mathematical Expositions

Endliche Automaten und Zufallsfolgen

Computable Analysis

A lightface analysis of the differentiability rank