We show that there exists a recursive coloring function c such that any $\Pi ^0_3$ set is not a solution to c for Hindman’s theorem. We also show that there exists a recursive coloring function c such that any $\Delta ^0_3$ set is not a solution to c for Hindman’s theorem restricted to sums of at most three numbers.

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.

Let K denote prefix-free Kolmogorov complexity, and let $K^A$ denote it relative to an oracle A. We show that for any n, $K^{\emptyset ^{(n)}}$ is definable purely in terms of the unrelativized notion K. It was already known that 2-randomness is definable in terms of K (and plain complexity C) as those reals which infinitely often have maximal complexity. We can use our characterization to show that n-randomness is definable purely in terms of K. To do this we extend a certain “limsup” formula from the literature, and apply Symmetry of Information. This extension entails a novel use of semilow sets, and a more precise analysis of the complexity of $\Delta _2^0$ sets of minimal descriptions.

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.

In the study of the arithmetic degrees the $\omega \text {-REA}$ sets play a role analogous to the role the r.e. degrees play in the study of the Turing degrees. However, much less is known about the arithmetic degrees and the role of the $\omega \text {-REA}$ sets in that structure than about the Turing degrees. Indeed, even basic questions such as the existence of an $\omega \text {-REA}$ set of minimal arithmetic degree are open. This paper makes progress on this question by demonstrating that some promising approaches inspired by the analogy with the r.e. sets fail to show that no $\omega \text {-REA}$ set is arithmetically minimal. Finally, it constructs a $\prod ^0_{2}$ singleton of minimal arithmetic degree. Not only is this a result of considerable interest in its own right, constructions of $\prod ^0_{2}$ singletons often pave the way for constructions of $\omega \text {-REA}$ sets with similar properties. Along the way, a number of interesting results relating arithmetic reducibility and rates of growth are established.

We present the true stages machinery and illustrate its applications to descriptive set theory. We use this machinery to provide new proofs of the Hausdorff–Kuratowski and Wadge theorems on the structure of $\mathbf {\Delta }^0_\xi $, Louveau and Saint Raymond’s separation theorem, and Louveau’s separation theorem.

The aim of this paper is to study supersoluble skew braces, a class of skew braces that encompasses all finite skew braces of square-free order. It turns out that finite supersoluble skew braces have Sylow towers and that in an arbitrary supersoluble skew brace B many relevant skew brace-theoretical properties are easier to identify: For example, a centrally nilpotent ideal of B is B-centrally nilpotent, a fact that simplifies the computational search for the Fitting ideal; also, B has finite multipermutational level if and only if $(B,+)$ is nilpotent.

Given a finite presentation of the structure skew brace $G(X,r)$ associated with a finite nondegenerate solution of the Yang–Baxter equation (YBE), there is an algorithm that decides if $G(X,r)$ is supersoluble or not. Moreover, supersoluble skew braces are examples of almost polycyclic skew braces, so they give rise to solutions of the YBE on which one can algorithmically work on.

We prove an effective version of the Lopez-Escobar theorem for continuous domains. Let $Mod(\tau )$ be the set of countable structures with universe $\omega $ in vocabulary $\tau $ topologized by the Scott topology. We show that an invariant set $X\subseteq Mod(\tau )$ is $\Pi ^0_\alpha $ in the Borel hierarchy of this topology if and only if it is definable by a $\Pi ^p_\alpha $-formula, a positive $\Pi ^0_\alpha $ formula in the infinitary logic $L_{\omega _1\omega }$. As a corollary of this result we obtain a new pullback theorem for positive computable embeddings: Let $\mathcal {K}$ be positively computably embeddable in $\mathcal {K}'$ by $\Phi $, then for every $\Pi ^p_\alpha $ formula $\xi $ in the vocabulary of $\mathcal {K}'$ there is a $\Pi ^p_\alpha $ formula $\xi ^{*}$ in the vocabulary of $\mathcal {K}$ such that for all $\mathcal {A}\in \mathcal {K}$, $\mathcal {A}\models \xi ^{*}$ if and only if $\Phi (\mathcal {A})\models \xi $. We use this to obtain new results on the possibility of positive computable embeddings into the class of linear orderings.

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.

Goodstein’s principle is arguably the first purely number-theoretic statement known to be independent of Peano arithmetic. It involves sequences of natural numbers which at first appear to diverge, but eventually decrease to zero. These sequences are defined relative to a notation system based on exponentiation for the natural numbers. In this article, we provide a self-contained and modern analysis of Goodstein’s principle, obtaining some variations and improvements. We explore notions of optimality for notation systems and apply them to the classical Goodstein process and to a weaker variant based on multiplication rather than exponentiation. In particular, we introduce the notion of base-change maximality, and show how it leads to far-reaching extensions of Goodstein’s result. We moreover show that by varying the initial base of the Goodstein process, one readily obtains independence results for each of the fragments $\mathsf {I}\Sigma _n$ of Peano arithmetic.

We define $\Psi $-autoreducible sets given an autoreduction procedure $\Psi $. Then, we show that for any $\Psi $, a measurable class of $\Psi $-autoreducible sets has measure zero. Using this, we show that classes of cototal, uniformly introenumerable, introenumerable, and hyper-cototal enumeration degrees all have measure zero.

By analyzing the arithmetical complexity of the classes of cototal sets and cototal enumeration degrees, we show that weakly 2-random sets cannot be cototal and weakly 3-random sets cannot be of cototal enumeration degree. Then, we see that this result is optimal by showing that there exists a 1-random cototal set and a 2-random set of cototal enumeration degree. For uniformly introenumerable degrees and introenumerable degrees, we utilize $\Psi $-autoreducibility again to show the optimal result that no weakly 3-random sets can have introenumerable enumeration degree. We also show that no 1-random set can be introenumerable.

A Polish space is not always homeomorphic to a computably presented Polish space. In this article, we examine degrees of non-computability of presenting homeomorphic copies of compact Polish spaces. We show that there exists a $\mathbf {0}'$-computable low$_3$ compact Polish space which is not homeomorphic to a computable one, and that, for any natural number $n\geq 2$, there exists a Polish space $X_n$ such that exactly the high$_{n}$-degrees are required to present the homeomorphism type of $X_n$. Along the way we investigate the computable aspects of Čech homology groups. We also show that no compact Polish space has a least presentation with respect to Turing reducibility.

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 study ordered groups in the context of both algebra and computability. Ordered groups are groups that admit a linear order that is compatible with the group operation. We explore some properties of ordered groups and discuss some related topics. We prove results about the semidirect product in relation to orderability and computability. In particular, we give a criteria for when a semidirect product of orderable groups is orderable and for when a semidirect product is computably categorical. We also give an example of a semidirect product that has the halting set coded into its multiplication structure but it is possible to construct a computable presentation of this semidirect product.

We examine a family of orderable groups that admit exactly countably many orders and show that their space of orders has arbitrary finite Cantor–Bendixson rank. Furthermore, this family of groups is also shown to be computably categorical, which in particular will allow us to conclude that any computable presentation of the groups does not admit any noncomputable orders. Lastly, we construct an example of an orderable computable group with no computable Archimedean orders but at least one computable non-Archimedean order.

Abstract prepared by Waseet Kazmi.

E-mail: [email protected]

URL: http://hdl.handle.net/11134/20002:860745910

We explore the complexity of Sacks’ Splitting Theorem in terms of the mind change functions associated with the members of the splits. We prove that, for any c.e. set A, there are low computably enumerable sets $A_0\sqcup A_1=A$ splitting A with $A_0$ and $A_1$ both totally $\omega ^2$-c.a. in terms of the Downey–Greenberg hierarchy, and this result cannot be improved to totally $\omega $-c.a. as shown in [9]. We also show that if cone avoidance is added then there is no level below $\varepsilon _0$ which can be used to characterize the complexity of $A_1$ and $A_2$.

For any subset $Z \subseteq {\mathbb {Q}}$, consider the set $S_Z$ of subfields $L\subseteq {\overline {\mathbb {Q}}}$ which contain a co-infinite subset $C \subseteq L$ that is universally definable in L such that $C \cap {\mathbb {Q}}=Z$. Placing a natural topology on the set ${\operatorname {Sub}({\overline {\mathbb {Q}}})}$ of subfields of ${\overline {\mathbb {Q}}}$, we show that if Z is not thin in ${\mathbb {Q}}$, then $S_Z$ is meager in ${\operatorname {Sub}({\overline {\mathbb {Q}}})}$. Here, thin and meager both mean “small”, in terms of arithmetic geometry and topology, respectively. For example, this implies that only a meager set of fields L have the property that the ring of algebraic integers $\mathcal {O}_L$ is universally definable in L. The main tools are Hilbert’s Irreducibility Theorem and a new normal form theorem for existential definitions. The normal form theorem, which may be of independent interest, says roughly that every $\exists $-definable subset of an algebraic extension of ${\mathbb Q}$ is a finite union of single points and projections of hypersurfaces defined by absolutely irreducible polynomials.

We investigate what it means for a (Hausdorff, second-countable) topological group to be computable. We compare several potential definitions based on classical notions in the literature. We relate these notions with the well-established definitions of effective presentability for discrete and profinite groups, and compare our results with similar results in computable topology.

This paper seeks to build on the extensive connections that have arisen between automata theory, combinatorics on words, fractal geometry, and model theory. Results in this paper establish a characterization for the behavior of the fractal geometry of “k-automatic” sets, subsets of $[0,1]^d$ that are recognized by Büchi automata. The primary tools for building this characterization include the entropy of a regular language and the digraph structure of an automaton. Via an analysis of the strongly connected components of such a structure, we give an algorithmic description of the box-counting dimension, Hausdorff dimension, and Hausdorff measure of the corresponding subset of the unit box. Applications to definability in model-theoretic expansions of the real additive group are laid out as well.

We study the position of the computable setting in the “common theory of locality” developed in [4, 5] for local problems on $\Delta $-regular trees, $\Delta \in \omega $. We show that such a problem admits a computable solution on every highly computable $\Delta $-regular forest if and only if it admits a Baire measurable solution on every Borel $\Delta $-regular forest. We also show that if such a problem admits a computable solution on every computable maximum degree $\Delta $ forest then it admits a continuous solution on every maximum degree $\Delta $ Borel graph with appropriate topological hypotheses, though the converse does not hold.

In their logical analysis of theorems about disjoint rays in graphs, Barnes, Shore, and the author (hereafter BGS) introduced a weak choice scheme in second-order arithmetic, called the $\Sigma ^1_1$ axiom of finite choice (hereafter finite choice). This is a special case of the $\Sigma ^1_1$ axiom of choice ($\Sigma ^1_1\text {-}\mathsf {AC}_0$) introduced by Kreisel. BGS showed that $\Sigma ^1_1\text {-}\mathsf {AC}_0$ suffices for proving many of the aforementioned theorems in graph theory. While it is not known if these implications reverse, BGS also showed that those theorems imply finite choice (in some cases, with additional induction assumptions). This motivated us to study the proof-theoretic strength of finite choice. Using a variant of Steel forcing with tagged trees, we show that finite choice is not provable from the $\Delta ^1_1$-comprehension scheme (even over $\omega $-models). We also show that finite choice is a consequence of the arithmetic Bolzano–Weierstrass theorem (introduced by Friedman and studied by Conidis), assuming $\Sigma ^1_1$-induction. Our results were used by BGS to show that several theorems in graph theory cannot be proved using $\Delta ^1_1$-comprehension. Our results also strengthen results of Conidis.