Computability

We study computably enumerable equivalence relations (abbreviated as ceers) under computable reducibility, and we investigate the resulting degree structure Ceers , which is a poset with a smallest and a greatest element. We point out a partition of the ceers into three classes: the finite ceers, the light ceers, and the dark ceers. These classes yield a partition of the degree structure as well, and in the language of posets the corresponding classes of degrees are first order definable within Ceers . There is no least, no maximal, no greatest dark degree, but there are infinitely many minimal dark degrees. We study joins and meets in Ceers , addressing the cases when two incomparable degrees of ceers X, Y have or do not have a join or a meet according to where X, Y are located in the classes of the aforementioned partition: in particular no pair of dark ceers has a join, and no pair in which at least one ceer is dark has a meet. We also exhibit examples of ceers X, Y having as a join their uniform join X ⊕ Y , but also examples with a join which is strictly less than X ⊕ Y . We study join-irreducibility and meet-irreducibility: every dark ceer is both join-, and meet-irreducible. In particular we characterize the property of being meet-irreducible for a ceer E, by showing that it coincides with the property of E being self-full, meaning that every reducibility from E to itself is in fact surjective on its equivalence classes (this property properly extends darkness). We then study the quotient structure obtained by dividing the poset Ceers by the degrees of the finite ceers, and study joins and meets in this quotient structure: interestingly, contrary to what happens in the structure of ceers, here there are pairs of incomparable equivalence classes of dark ceers having a join, and every element different from the greatest one is meet-reducible. In fact in this quotient structure, every degree different from the greatest one has infinitely many strong minimal covers, whereas in Ceers every degree different from the greatest one has either infinitely many strong minimal covers, or the cone strictly above it has a least element: this latter property characterizes the self-full degrees. We look at automorphisms of Ceers , and show that there are continuum many automorphisms fixing the dark ceers, and continuum many automorphisms fixing the light ceers. Finally, we compute the complexity of the index sets of the classes of ceers studied in the paper.

We prove that if A is a non-low c.e. set, then there exists noncomputable sets A 1 ⊔ A 2 = A splitting A with A 1 non-low.

Hindman’s Theorem (HT) states that for every coloring of N with finitely many colors, there is an infinite set H ⊆ N such that all nonempty sums of distinct elements of H have the same color. The investigation of restricted versions of HT from the computability-theoretic and reverse-mathematical perspectives has been a productive line of research recently. In particular, HT k ⩽ n is the restriction of HT to sums of at most n many elements, with at most k colors allowed, and HT k = n is the restriction of HT to sums of exactly n many elements and k colors. Even HT 2 ⩽ 2 appears to be a strong principle, and may even imply HT itself over RCA₀. In contrast, HT 2 = 2 is known to be strictly weaker than HT over RCA₀, since HT 2 = 2 follows immediately from Ramsey’s Theorem for 2-colorings of pairs. In fact, it was open for several years whether HT 2 = 2 is computably true.

We show that HT 2 = 2 and similar results with addition replaced by subtraction and other operations are not provable in RCA₀, or even WKL₀. In fact, we show that there is a computable instance of HT 2 = 2 such that all solutions can compute a function that is diagonally noncomputable relative to ∅ ′ . It follows that there is a computable instance of HT 2 = 2 with no Σ 2 0 solution, which is the best possible result with respect to the arithmetical hierarchy. Furthermore, a careful analysis of the proof of the result above about solutions DNC relative to ∅ ′ shows that HT 2 = 2 implies RRT 2 2 , the Rainbow Ramsey Theorem for colorings of pairs for which there are most two pairs with each color, over RCA₀. The most interesting aspect of our construction of computable colorings as above is the use of an effective version of the Lovász Local Lemma due to Rumyantsev and Shen.

Computable reducibility is a well-established notion that allows to compare the complexity of various equivalence relations over the natural numbers. We generalize computable reducibility by introducing degree spectra of reducibility and bi-reducibility. These spectra provide a natural way of measuring the complexity of reductions between equivalence relations. We prove that any upward closed collection of Turing degrees with a countable basis can be realised as a reducibility spectrum or as a bi-reducibility spectrum. We show also that there is a reducibility spectrum of computably enumerable equivalence relations with no countable basis and a reducibility spectrum of computably enumerable equivalence relations which is downward dense, thus has no basis.

In this paper we study, for n ⩾ 1 , the projection operators over R n , that is the multi-valued functions that associate to x ∈ R n and A ⊆ R n closed, the points of A which are closest to x. We also deal with approximate projections, where we content ourselves with points of A which are almost the closest to x. We use the tools of Weihrauch reducibility to classify these operators depending on the representation of A and the dimension n. It turns out that, depending on the representation of the closed sets and the dimension of the space, the projection and approximate projection operators characterize some of the most fundamental computational classes in the Weihrauch lattice.

We provide a survey of results using Weihrauch problems to find analogs between set theory and computability theory. In our treatment, we emphasize the role of morphisms in explaining these coincidences. We end with a discussion of the use of forcing to prove the nonexistence of morphisms.

The class of Abelian p-groups are an example of some very interesting phenomena in computable structure theory. We will give an elementary first-order theory T p whose models are each bi-interpretable with the disjoint union of an Abelian p-group and a pure set (and so that every Abelian p-group is bi-interpretable with a model of T p ) using computable infinitary formulas. This answers a question of Knight by giving an example of an elementary first-order theory of “Ulm type”: Any two models, low for ω 1 C K , and with the same computable infinitary theory, are isomorphic. It also gives a new example of an elementary first-order theory whose isomorphism problem is Σ 1 1 -complete but not Borel complete.

In this paper we study various properties of algorithmically random infinite structures. Our results address the following questions. How would one define algorithmic randomness for infinite structures? Could algorithmically random structures be computable? What are the similarities and differences between algorithmically random structures and algorithmically random infinite strings? What are the possible Turing degrees of algorithmically random structures? Are there algorithmically random infinite groups? For instance, we prove the following in this paper: (1) there are classes which contain algorithmically random yet computable structures, (2) there exist algorithmically random universal algebras with co-computably enumerable as well as computably enumerable word problems, (3) there are natural classes of structures in which the Turing degrees of algorithmically random structures can only be either computable or equivalent to the halting set, and (4) there are examples of algorithmically random groups. The first result shows a dramatic difference between algorithmically random strings and algorithmically random structures. The second result significantly improves the known theorem that algorithmically random structures computable in the halting set exist; these examples of algebras are sharp in terms of arithmetical hierarchy of the word problem for random algebras. The third result is a dichotomy theorem that characterises all possible Turing degrees of algorithmically random structures. Finally, the fourth result answers a nontrivial open question about the existence of algorithmically random groups.

The notion of ‘modulus of regularity’, as recently studied in [Moduli of regularity and rates of convergence for Fejér monotone sequences, 2017, Preprint], unifies a number of different concepts used in convex optimization to establish rates of convergence for Fejér monotone iterative procedures. It generalizes the notion of ‘modulus of uniqueness’ to the nonunique case. In this paper, we investigate both notions in terms of reverse mathematics and calibrate their Weihrauch complexity.

We introduce and study effective versions of the localization numbers introduced by Newelski and Roslanowski (Proceedings of the American Mathematical Society117(3) (1993), 823–831). We show that proper hierarchies are produced, and that the corresponding highness notions are relatively weak, in that they can often be made computably traceable. We discuss connections with other better-understood effective cardinal characteristics.

Consider two paths f , g : [ 0 ; 1 ] → [ 0 ; 1 ] 2 in the unit square such that f ( 0 ) = ( 0 , 0 ) , f ( 1 ) = ( 1 , 1 ) , g ( 0 ) = ( 0 , 1 ) and g ( 1 ) = ( 1 , 0 ) . By continuity of f and g there is a point of intersection. We prove that there is a computable point of intersection if f and g are computable.