We study the existence and the distribution of “long” chains in the Weihrauch degrees, mostly focusing on chains with uncountable cofinality. We characterize when such chains have an upper bound and prove that there are no cofinal chains (of any order type) in the Weihrauch degrees. Furthermore, we show that the existence of coinitial sequences of non-zero degrees is equivalent to CH $\mathrm {CH}$ upper C upper H. Finally, we explore the extendibility of antichains, providing some necessary conditions for maximality.

We explore the Weihrauch degree of the problems “find a bad sequence in a non-well quasi order” ( $\mathsf {BS}$ ) and “find a descending sequence in an ill-founded linear order” ( $\mathsf {DS}$ ). We prove that $\mathsf {DS}$ is strictly Weihrauch reducible to $\mathsf {BS}$, correcting our mistaken claim in [18]. This is done by separating their respective first-order parts. On the other hand, we show that $\mathsf {BS}$ and $\mathsf {DS}$ have the same finitary and deterministic parts, (...) confirming that $\mathsf {BS}$ and $\mathsf {DS}$ have very similar uniform computational strength. We prove that König’s lemma $\mathsf {KL}$ and the problem $\mathsf {wList}_{{2^{\mathbb {N}}},\leq \omega }$ of enumerating a given non-empty countable closed subset of ${2^{\mathbb {N}}}$ are not Weihrauch reducible to $\mathsf {DS}$ or $\mathsf {BS}$, resolving two main open questions raised in [18]. We also answer the question, raised in [12], on the existence of a “parallel quotient” operator, and study the behavior of $\mathsf {BS}$ and $\mathsf {DS}$ under the quotient with some known problems. (shrink)

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. (shrink)

In this article, we study an analogue of tt-reducibility for points in computable metric spaces. We characterize the notion of the metric tt-degree in the context of first-level Borel isomorphism. Then, we study this concept from the perspectives of effective topological dimension theory and of effective fractal dimension theory.

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. (shrink)

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. (shrink)

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 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.

We examine topological pairs $(A,B)$ which have computable type, which means that the following holds: if X is a computable topological space and $f:A\rightarrow X$ is an embedding such that $f(A)$ and $f(B)$ are semicomputable sets in X, then $f(A)$ is a computable set in X. If $(A,\emptyset )$ has computable type, we say that A has computable type. In general, if a topological pair $(A,B)$ is such that the quotient space $A/B$ has computable type, then $(A,B)$ need not have (...) computable type. We prove the following: if $A/B$ has computable type and the interior of B in A is empty, then $(A,B)$ has computable type. On the other hand, if $(A,B)$ has computable type, then $A/B$ need not have computable type even if $\mathop {\mathrm {Int}}_{A}B=\emptyset $. Related to this, we introduce the notion of a local computable type. We show that $\mathbb {R}^{n} /K$ has local computable type if K is a compact subspace of $\mathbb {R}^{n} $ such that $\mathbb {R}^{n} \setminus K$ has finitely many connected components. (shrink)

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. (shrink)

We examine conditions under which, in a computable topological space, a semicomputable set is computable. It is known that in a computable metric space a semicomputable set S is computable if S is a continuum chainable from a to b, where a and b are computable points, or S is a circularly chainable continuum which is not chainable. We prove that this result holds in any computable topological space.

We study the computational complexity of converting between different representations of irrational numbers. Typical examples of representations are Cauchy sequences, base-10 expansions, Dedekind cuts and continued fractions.

A computable topological presentation of a space is given by an effective list of a countable basis of non-empty open sets so that the intersection of the basic sets is uniformly effectively enumerable. We show that every countably-based $T_0$ -space has a computable topological presentation, and that, conversely, every (formal) computable topological presentation represents some Polish space. In the compact case, we give a computable uniform list of computable topological presentations such that every compact Polish space is represented by exactly (...) one presentation from the list. Note that none of these results assume that the Polish (or $T_0$ ) spaces are effective. Quite surprisingly, the effectively compact topological presentations turn out to be rather well behaved. Not only do such presentations allow one to construct a $\Delta ^0_2$ (complete) metric compatible with the topology, but also, under a mild extra condition, they can be turned into a computably compact Polish presentation of the space. (shrink)

This paper continues the program connecting reverse mathematics and computable analysis via the framework of Weihrauch reducibility. In particular, we consider problems related to perfect subsets of Polish spaces, studying the perfect set theorem, the Cantor–Bendixson theorem, and various problems arising from them. In the framework of reverse mathematics, these theorems are equivalent, respectively, to $\mathsf {ATR}_0$ and $\boldsymbol {\Pi }^1_1{-}\mathsf{CA}_0$, the two strongest subsystems of second order arithmetic among the so-called big five. As far as we know, this is (...) the first systematic study of problems at the level of $\boldsymbol {\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. (shrink)

We study versions of the tree pigeonhole principle, $\mathsf {TT}^1$, in the context of Weihrauch-style computable analysis. The principle has previously been the subject of extensive research in reverse mathematics, an outstanding question of which investigation is whether $\mathsf {TT}^1$ is $\Pi ^1_1$ -conservative over the ordinary pigeonhole principle, $\mathsf {RT}^1$. Using the recently introduced notion of the first-order part of an instance-solution problem, we formulate the analog of this question for Weihrauch reducibility, and give an affirmative answer. In combination (...) with other results, we use this to show that unlike $\mathsf {RT}^1$, the problem $\mathsf {TT}^1$ is not Weihrauch requivalent to any first-order problem. Our proofs develop new combinatorial machinery for constructing and understanding solutions to instances of $\mathsf {TT}^1$. (shrink)

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]: https://air.uniud.it/handle/11390/1252226. (shrink)

Suppose \ is a computable real. We extend previous work of Clanin, Stull, and McNicholl by determining the degrees of categoricity of the separable \ spaces whose underlying measure spaces are atomic but not purely atomic. In addition, we ascertain the complexity of associated projection maps.

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. (shrink)

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]. (shrink)

We study the uniform computational content of Ramsey’s theorem using both Weihrauch reducibility and a new variant of Weihrauch reducibility, where the functions in the reduction are required to be total. In the latter setting, we show that the strength of Ramsey’s theorem varies significantly depending on how one represents its solutions, for example, using characteristic functions or using enumerations. Some of our results extend beyond variants of Ramsey’s theorem. In particular, we show that RT 2 2 $\mathsf {RT}^{2}_{2}$ sans (...) serif upper R upper T 2 squared where solutions are represented using characteristic functions is not totally Weihrauch reducible to any computational problem whose solutions are represented using enumerations. Next, we study the computational problems RT ∞ n $\mathsf {RT}^{n}_{\infty }$ sans serif upper R upper T Subscript infinity Superscript n which take as input a colouring of n-tuples which has some infinite homogeneous set and asks for any such set. The problem RT ∞ 1 $\mathsf {RT}^{1}_{\infty }$ sans serif upper R upper T Subscript infinity Superscript 1 is fairly well-studied, as it is Weihrauch equivalent to the cluster point problem on N $\mathbb {N}$ double struck upper N. Our main result shows that RT ∞ 1 $\mathsf {RT}^{1}_{\infty }$ sans serif upper R upper T Subscript infinity Superscript 1 is not Weihrauch reducible to RT N 2 $\mathsf {RT}^{2}_{\mathbb {N}}$ sans serif upper R upper T Subscript double struck upper N Superscript 2, strengthening a result of Soldà and Valenti. We also show that the jump of RT ∞ 1 $\mathsf {RT}^{1}_{\infty }$ sans serif upper R upper T Subscript infinity Superscript 1 is Weihrauch equivalent to SRT ∞ 2 $\mathsf {SRT}^{2}_{\infty }$ sans serif upper S upper R upper T Subscript infinity Superscript 2. (shrink)