Using tools from computable analysis, we develop a notion of effectiveness for general dynamical systems as those group actions on arbitrary spaces that contain a computable representative in their topological conjugacy class. Most natural systems one can think of are effective in this sense, including some group rotations, affine actions on the torus and finitely presented algebraic actions. We show that for finitely generated and recursively presented groups, every effective dynamical system is the topological factor of a computable action on an effectively closed subset of the Cantor space. We then apply this result to extend the simulation results available in the literature beyond zero-dimensional spaces. In particular, we show that for a large class of groups, many of these natural actions are topological factors of subshifts of finite type.

In this thesis, we study the complexity of some mathematical problems: in particular, those arising in computable analysis and algorithmic learning theory for algebraic structures. Our study is not limited to these two areas: indeed, in both cases, the results we obtain are tightly connected to ideas and tools coming from different areas of mathematical logic, including for example descriptive set theory and reverse mathematics.

After giving the necessary preliminaries, we first study the uniform computational strength of the Cantor–Bendixson theorem in the Weihrauch lattice. This work falls into the program connecting reverse mathematics and computable analysis via the framework of Weihrauch reducibility. We concentrate on problems related to perfect subsets of Polish spaces, studying the perfect set theorem, the Cantor–Bendixson theorem, and various problems arising from them. As far as we know, this is the first systematic study of problems at the level of $\mathbf {\Pi }^1_1\mathsf {-CA}_0$ in the Weihrauch lattice. We show that the strength of some of the problems we study depends on the topological properties of the Polish space under consideration, while others have the same strength once the space is rich enough.

We continue considering problems related to (induced) subgraphs. We provide results on the (effective) Wadge complexity of sets of graphs, that are also used to determine the Weihrauch degree of certain decision problems. The decision problems we consider are defined for a fixed graph G, and they take as input a graph H, answering whether G is an (induced) subgraph of H: we also consider the opposite problem (i.e., answering whether H is an induced subgraph of G). We conclude this part on (induced) subgraphs considering the Weihrauch degree of “search problems.”These problems are defined for a fixed graph G, and they take as input a graph H such that G is an (induced) subgraph H: the output is a copy of G in H. In both cases, we highlight differences and analogies between the subgraph and the induced subgraph relation.

We then move our attention to algorithmic learning theory, and we present the framework we use to study the learnability of families of algebraic structures: here, given a countable family of pairwise nonisomorphic structures $\mathfrak {K}$, a learner receives larger and larger pieces of an arbitrary copy of a structure in $\mathfrak {K}$ and, at each stage, is required to output a conjecture about the isomorphism type of such a structure. We say that $\mathfrak {K}$ is learnable if there exists a learner which eventually stabilizes to a correct guess. The framework was lacking a method for comparing the complexity of nonlearnable families, and so we propose a solution to this problem using tools coming from invariant descriptive set theory. To do so, we first prove that a family of structures is learnable if and only if its learning domain is continuously reducible to the relation $E_0$ of eventual agreement on infinite binary sequences and then, replacing $E_0$ with Borel equivalence relations of higher complexity, we obtain a new hierarchy of learning problems. This leads to the notion of E-learnability, where a family of structures $\mathfrak {K}$ is E-learnable, for a Borel equivalence relation E, if there is a continuous reduction from the isomorphism relation associated with $\mathfrak {K}$ to E. It is then natural to ask how the notion of E-learnability interacts with “classical” learning paradigms.

Finally, we study the number of mind changes that a learner needs to learn a given family, both from a topological and a combinatorial point of view, and we consider how the complexity of a learner (in terms of Turing reducibility) affects the number of mind changes for learning a given family.

Abstract prepared by Vittorio Cipriani.

E-mail: [email protected].

URL: https://air.uniud.it/handle/11390/1252226.

We call an $\alpha \in \mathbb {R}$ regainingly approximable if there exists a computable nondecreasing sequence $(a_n)_n$ of rational numbers converging to $\alpha $ with $\alpha - a_n < 2^{-n}$ for infinitely many ${n \in \mathbb {N}}$. We also call a set $A\subseteq \mathbb {N}$ regainingly approximable if it is c.e. and the strongly left-computable number $2^{-A}$ is regainingly approximable. We show that the set of regainingly approximable sets is neither closed under union nor intersection and that every c.e. Turing degree contains such a set. Furthermore, the regainingly approximable numbers lie properly between the computable and the left-computable numbers and are not closed under addition. While regainingly approximable numbers are easily seen to be i.o. K-trivial, we construct such an $\alpha $ such that ${K(\alpha \restriction n)>n}$ for infinitely many n. Similarly, there exist regainingly approximable sets whose initial segment complexity infinitely often reaches the maximum possible for c.e. sets. Finally, there is a uniform algorithm splitting regular real numbers into two regainingly approximable numbers that are still regular.

Computability theoretic aspects of Polish metric spaces are studied by adapting notions and methods of computable structure theory. In this dissertation, we mainly investigate index sets and classification problems for computably presentable Polish metric spaces. We find the complexity of a number of index sets, isomorphism problems, and embedding problems for computably presentable metric spaces. We also provide several computable structure theory results related to some classical Polish metric spaces such as the Urysohn space $\mathbb {U}$, the Cantor space $2^{\mathbb {N}}$, the Baire space $\mathbb {N}^{\mathbb {N}}$, and spaces of continuous functions.

Abstract prepared by Teerawat Thewmorakot.

E-mail: [email protected]

We give a systematic technical exposition of the foundations of the theory of computably compact metric spaces. We discover several new characterizations of computable compactness and apply these characterizations to prove new results in computable analysis and effective topology. We also apply the technique of computable compactness to give new and less combinatorially involved proofs of known results from the literature. Some of these results do not have computable compactness or compact spaces in their statements, and thus these applications are not necessarily direct or expected.

We initiate the study of computable presentations of real and complex C*-algebras under the program of effective metric structure theory. With the group situation as a model, we develop corresponding notions of recursive presentations and word problems for C*-algebras, and show some analogous results hold in this setting. Famously, every finitely generated group with a computable presentation is computably categorical, but we provide a counterexample in the case of C*-algebras. On the other hand, we show every finite-dimensional C*-algebra is computably categorical.

Computable analysis provides ways of representing points in a topological space, and therefore of defining a notion of computable points of the space. In this article, we investigate when two topologies on the same space induce different sets of computable points. We first study a purely topological version of the problem, which is to understand when two topologies are not $\sigma $-homeomorphic. We obtain a characterization leading to an effective version, and we prove that two topologies satisfying this condition induce different sets of computable points. Along the way, we propose an effective version of the Baire category theorem which captures the construction technique, and enables one to build points satisfying properties that are co-meager with respect to a topology, and are computable with respect to another topology. Finally, we generalize the result to three topologies and give an application to prove that certain sets do not have computable type, which means that they have a homeomorphic copy that is semicomputable but not computable.

This thesis is devoted to the exploration of the complexity of some mathematical problems using the framework of computable analysis and (effective) descriptive set theory. We will especially focus on Weihrauch reducibility as a means to compare the uniform computational strength of problems. After a short introduction of the relevant background notions, we investigate the uniform computational content of problems arising from theorems that lie at the higher levels of the reverse mathematics hierarchy.

We first analyze the strength of the open and clopen Ramsey theorems. Since there is not a canonical way to phrase these theorems as multi-valued functions, we identify eight different multi-valued functions (five corresponding to the open Ramsey theorem and three corresponding to the clopen Ramsey theorem) and study their degree from the point of view of Weihrauch, strong Weihrauch, and arithmetic Weihrauch reducibility.

We then discuss some new operators on multi-valued functions and study their algebraic properties and the relations with other previously studied operators on problems. In particular, we study the first-order part and the deterministic part of a problem f, capturing the Weihrauch degree of the strongest multi-valued problem that is reducible to f and that, respectively, has codomain $\mathbb {N}$ or is single-valued.

These notions proved to be extremely useful when exploring the Weihrauch degree of the problem $\mathsf {DS}$ of computing descending sequences in ill-founded linear orders. They allow us to show that $\mathsf {DS}$ , and the Weihrauch equivalent problem $\mathsf {BS}$ of finding bad sequences through non-well quasi-orders, while being very “hard” to solve, are rather weak in terms of uniform computational strength. We then generalize $\mathsf {DS}$ and $\mathsf {BS}$ by considering $\boldsymbol {\Gamma }$ -presented orders, where $\boldsymbol {\Gamma }$ is a Borel pointclass or $\boldsymbol {\Delta }^1_1$ , $\boldsymbol {\Sigma }^1_1$ , $\boldsymbol {\Pi }^1_1$ . We study the obtained $\mathsf {DS}$ -hierarchy and $\mathsf {BS}$ -hierarchy of problems in comparison with the (effective) Baire hierarchy and show that they do not collapse at any finite level.

Finally, we work in the context of geometric measure theory and we focus on the characterization, from the point of view of descriptive set theory, of some conditions involving the notions of Hausdorff/Fourier dimension and Salem sets. We first work in the hyperspace $\mathbf {K}([0,1])$ of compact subsets of $[0,1]$ and show that the closed Salem sets form a $\boldsymbol {\Pi }^0_3$ -complete family. This is done by characterizing the complexity of the family of sets having sufficiently large Hausdorff or Fourier dimension. We also show that the complexity does not change if we increase the dimension of the ambient space and work in $\mathbf {K}([0,1]^d)$ . We also generalize the results by relaxing the compactness of the ambient space and show that the closed Salem sets are still $\boldsymbol {\Pi }^0_3$ -complete when we endow $\mathbf {F}(\mathbb {R}^d)$ with the Fell topology. A similar result holds also for the Vietoris topology.

We conclude by analyzing the same notions from the point of view of effective descriptive set theory and Type-2 Theory of Effectivity, and show that the complexities remain the same also in the lightface case. In particular, we show that the family of all the closed Salem sets is $\Pi ^0_3$ -complete. We furthermore characterize the Weihrauch degree of the functions computing Hausdorff and Fourier dimension of closed sets.

Abstract prepared by Manlio Valenti.

E-mail:[email protected]

We introduce the point degree spectrum of a represented space as a substructure of the Medvedev degrees, which integrates the notion of Turing degrees, enumeration degrees, continuous degrees and so on. The notion of point degree spectrum creates a connection among various areas of mathematics, including computability theory, descriptive set theory, infinite-dimensional topology and Banach space theory. Through this new connection, for instance, we construct a family of continuum many infinite-dimensional Cantor manifolds with property C whose Borel structures at an arbitrary finite rank are mutually nonisomorphic. This resolves a long-standing question by Jayne and strengthens various theorems in infinite-dimensional topology such as Pol’s solution to Alexandrov’s old problem.

Matthias Schröder has asked the question whether there is a weakest discontinuous problem in the topological version of the Weihrauch lattice. Such a problem can be considered as the weakest unsolvable problem. We introduce the discontinuity problem, and we show that it is reducible exactly to the effectively discontinuous problems, defined in a suitable way. However, in which sense this answers Schröder’s question sensitively depends on the axiomatic framework that is chosen, and it is a positive answer if we work in Zermelo–Fraenkel set theory with dependent choice and the axiom of determinacy $\mathsf {AD}$. On the other hand, using the full axiom of choice, one can construct problems which are discontinuous, but not effectively so. Hence, the exact situation at the bottom of the Weihrauch lattice sensitively depends on the axiomatic setting that we choose. We prove our result using a variant of Wadge games for mathematical problems. While the existence of a winning strategy for Player II characterizes continuity of the problem (as already shown by Nobrega and Pauly), the existence of a winning strategy for Player I characterizes effective discontinuity of the problem. By Weihrauch determinacy we understand the condition that every problem is either continuous or effectively discontinuous. This notion of determinacy is a fairly strong notion, as it is not only implied by the axiom of determinacy $\mathsf {AD}$, but it also implies Wadge determinacy. We close with a brief discussion of generalized notions of productivity.

The Jordan decomposition theorem states that every function $f \colon \, [0,1] \to \mathbb {R}$ of bounded variation can be written as the difference of two non-decreasing functions. Combining this fact with a result of Lebesgue, every function of bounded variation is differentiable almost everywhere in the sense of Lebesgue measure. We analyze the strength of these theorems in the setting of reverse mathematics. Over $\mathsf {RCA}_{0}$ , a stronger version of Jordan’s result where all functions are continuous is equivalent to $\mathsf {ACA}_0$ , while the version stated is equivalent to ${\textsf {WKL}}_{0}$ . The result that every function on $[0,1]$ of bounded variation is almost everywhere differentiable is equivalent to ${\textsf {WWKL}}_{0}$ . To state this equivalence in a meaningful way, we develop a theory of Martin–Löf randomness over $\mathsf {RCA}_0$ .

In this work we investigate the Weihrauch degree of the problem Decreasing Sequence ( $\mathsf {DS}$ ) of finding an infinite descending sequence through a given ill-founded linear order, which is shared by the problem Bad Sequence ( $\mathsf {BS}$ ) of finding a bad sequence through a given non-well quasi-order. We show that $\mathsf {DS}$ , despite being hard to solve (it has computable inputs with no hyperarithmetic solution), is rather weak in terms of uniform computational strength. To make the latter precise, we introduce the notion of the deterministic part of a Weihrauch degree. We then generalize $\mathsf {DS}$ and $\mathsf {BS}$ by considering $\boldsymbol {\Gamma }$ -presented orders, where $\boldsymbol {\Gamma }$ is a Borel pointclass or $\boldsymbol {\Delta }^1_1$ , $\boldsymbol {\Sigma }^1_1$ , $\boldsymbol {\Pi }^1_1$ . We study the obtained $\mathsf {DS}$ -hierarchy and $\mathsf {BS}$ -hierarchy of problems in comparison with the (effective) Baire hierarchy and show that they do not collapse at any finite level.

We investigate the uniform computational content of the open and clopen Ramsey theorems in the Weihrauch lattice. While they are known to be equivalent to $\mathrm {ATR_0}$ from the point of view of reverse mathematics, there is not a canonical way to phrase them as multivalued functions. We identify eight different multivalued functions (five corresponding to the open Ramsey theorem and three corresponding to the clopen Ramsey theorem) and study their degree from the point of view of Weihrauch, strong Weihrauch, and arithmetic Weihrauch reducibility. In particular one of our functions turns out to be strictly stronger than any previously studied multivalued functions arising from statements around $\mathrm {ATR}_0$ .

We prove that the Weihrauch lattice can be transformed into a Brouwer algebra by the consecutive application of two closure operators in the appropriate order: first completion and then parallelization. The closure operator of completion is a new closure operator that we introduce. It transforms any problem into a total problem on the completion of the respective types, where we allow any value outside of the original domain of the problem. This closure operator is of interest by itself, as it generates a total version of Weihrauch reducibility that is defined like the usual version of Weihrauch reducibility, but in terms of total realizers. From a logical perspective completion can be seen as a way to make problems independent of their premises. Alongside with the completion operator and total Weihrauch reducibility we need to study precomplete representations that are required to describe these concepts. In order to show that the parallelized total Weihrauch lattice forms a Brouwer algebra, we introduce a new multiplicative version of an implication. While the parallelized total Weihrauch lattice forms a Brouwer algebra with this implication, the total Weihrauch lattice fails to be a model of intuitionistic linear logic in two different ways. In order to pinpoint the algebraic reasons for this failure, we introduce the concept of a Weihrauch algebra that allows us to formulate the failure in precise and neat terms. Finally, we show that the Medvedev Brouwer algebra can be embedded into our Brouwer algebra, which also implies that the theory of our Brouwer algebra is Jankov logic.

We study computable Polish spaces and Polish groups up to homeomorphism. We prove a natural effective analogy of Stone duality, and we also develop an effective definability technique which works up to homeomorphism. As an application, we show that there is a $\Delta ^0_2$ Polish space not homeomorphic to a computable one. We apply our techniques to build, for any computable ordinal $\alpha $, an effectively closed set not homeomorphic to any $0^{(\alpha )}$-computable Polish space; this answers a question of Nies. We also prove analogous results for compact Polish groups and locally path-connected spaces.

The Wadge hierarchy was originally defined and studied only in the Baire space (and some other zero-dimensional spaces). Here we extend the Wadge hierarchy of Borel sets to arbitrary topological spaces by providing a set-theoretic definition of all its levels. We show that our extension behaves well in second countable spaces and especially in quasi-Polish spaces. In particular, all levels are preserved by continuous open surjections between second countable spaces which implies e.g., several Hausdorff–Kuratowski (HK)-type theorems in quasi-Polish spaces. In fact, many results hold not only for the Wadge hierarchy of sets but also for its extension to Borel functions from a space to a countable better quasiorder Q.

Computability theory is used to evaluate the complexity of classifying various kinds of Lebesgue spaces and associated isometric isomorphism problems.

In 1932, von Neumann proposed classifying the statistical behavior of differentiable systems. Joint work of B. Weiss and the author proved that the classification problem is complete analytic. Based on techniques in that proof, one is able to show that the collection of recursive diffeomorphisms of the 2-torus that are isomorphic to their inverses is $\Pi ^0_1$-hard via a computable 1-1 reduction. As a corollary there is a diffeomorphism that is isomorphic to its inverse if and only if the Riemann Hypothesis holds, a different one that is isomorphic to its inverse if and only if Goldbach’s conjecture holds and so forth. Applying the reduction to the $\Pi ^0_1$-sentence expressing “ZFC is consistent” gives a diffeomorphism T of the 2-torus such that the question of whether $T\cong T^{-1}$ is independent of ZFC.

There are close similarities between the Weihrauch lattice and the zoo of axiom systems in reverse mathematics. Following these similarities has often allowed researchers to translate results from one setting to the other. However, amongst the big five axiom systems from reverse mathematics, so far $\mathrm {ATR}_0$ has no identified counterpart in the Weihrauch degrees. We explore and evaluate several candidates, and conclude that the situation is complicated.

We give several new characterizations of the continuous enumeration degrees. The main one proves that an enumeration degree is continuous if and only if it is not half of a nontrivial relativized $\mathcal {K}$ -pair. This leads to a structural dichotomy in the enumeration degrees.