We introduce the computable FS-jump, an analog of the classical Friedman–Stanley jump in the context of equivalence relations on the natural numbers. We prove that the computable FS-jump is proper with respect to computable reducibility. We then study the effect of the computable FS-jump on computably enumerable equivalence relations (ceers).

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)

Cantor’s first set theory paper (1874) establishes the uncountability of ${\mathbb R}$. We study this most basic mathematical fact formulated in the language of higher-order arithmetic. In particular, we investigate the logical and computational properties of ${\mathsf {NIN}}$ (resp. ${\mathsf {NBI}}$ ), i.e., the third-order statement there is no injection resp. bijection from $[0,1]$ to ${\mathbb N}$. Working in Kohlenbach’s higher-order Reverse Mathematics, we show that ${\mathsf {NIN}}$ and ${\mathsf {NBI}}$ are hard to prove in terms of (conventional) comprehension axioms, (...) while many basic theorems, like Arzelà’s convergence theorem for the Riemann integral (1885), are shown to imply ${\mathsf {NIN}}$ and/or ${\mathsf {NBI}}$. Working in Kleene’s higher-order computability theory based on S1–S9, we show that the following fourth-order process based on ${\mathsf {NIN}}$ is similarly hard to compute: for a given $[0,1]\rightarrow {\mathbb N}$ -function, find reals in the unit interval that map to the same natural number. (shrink)

We examine the degree structure $\operatorname {\mathrm {\mathbf {ER}}}$ of equivalence relations on $\omega $ under computable reducibility. We examine when pairs of degrees have a least upper bound. In particular, we show that sufficiently incomparable pairs of degrees do not have a least upper bound but that some incomparable degrees do, and we characterize the degrees which have a least upper bound with every finite equivalence relation. We show that the natural classes of finite, light, and dark degrees are (...) definable in $\operatorname {\mathrm {\mathbf {ER}}}$. We show that every equivalence relation has continuum many self-full strong minimal covers, and that $\mathbf {d}\oplus \mathbf {\operatorname {\mathrm {\mathbf {Id}}}_1}$ needn’t be a strong minimal cover of a self-full degree $\mathbf {d}$. Finally, we show that the theory of the degree structure $\operatorname {\mathrm {\mathbf {ER}}}$ as well as the theories of the substructures of light degrees and of dark degrees are each computably isomorphic with second-order arithmetic. (shrink)

We prove that the Wadge order on the Borel subsets of the Scott domain is not a well-quasi-order, and that this feature even occurs among the sets of Borel rank at most 2. For this purpose, a specific class of countable 2-colored posets$\mathbb{P}_{emb} $equipped with the order induced by homomorphisms is embedded into the Wadge order on the$\Delta _2^0 $-degrees of the Scott domain. We then show that$\mathbb{P}_{emb} $admits both infinite strictly decreasing chains and infinite antichains with respect to this (...) notion of comparison, which therefore transfers to the Wadge order on the$\Delta _2^0 $-degrees of the Scott domain. (shrink)

In this survey we discuss work of Levin and V’yugin on collections of sequences that are non-negligible in the sense that they can be computed by a probabilistic algorithm with positive probability. More precisely, Levin and V’yugin introduced an ordering on collections of sequences that are closed under Turing equivalence. Roughly speaking, given two such collections $\mathcal {A}$ and $\mathcal {B}$, $\mathcal {A}$ is below $\mathcal {B}$ in this ordering if $\mathcal {A}\setminus \mathcal {B}$ is negligible. The degree structure associated (...) with this ordering, the Levin–V’yugin degrees, can be shown to be a Boolean algebra, and in fact a measure algebra. We demonstrate the interactions of this work with recent results in computability theory and algorithmic randomness: First, we recall the definition of the Levin–V’yugin algebra and identify connections between its properties and classical properties from computability theory. In particular, we apply results on the interactions between notions of randomness and Turing reducibility to establish new facts about specific LV-degrees, such as the LV-degree of the collection of 1-generic sequences, that of the collection of sequences of hyperimmune degree, and those collections corresponding to various notions of effective randomness. Next, we provide a detailed explanation of a complex technique developed by V’yugin that allows the construction of semi-measures into which computability-theoretic properties can be encoded. We provide two examples of the use of this technique by explicating a result of V’yugin’s about the LV-degree of the collection of Martin-Löf random sequences and extending the result to the LV-degree of the collection of sequences of DNC degree. (shrink)

Reverse Mathematics (RM hereafter) is a program in the foundations of mathematics where the aim is to identify theminimalaxioms needed to prove a given theorem from ordinary, i.e., non-set theoretic, mathematics. This program has unveiled surprising regularities: the minimal axioms are very oftenequivalentto the theorem over thebase theory, a weak system of ‘computable mathematics’, while most theorems are either provable in this base theory, or equivalent to one of onlyfourlogical systems. The latter plus the base theory are called the ‘Big (...) Five’ and the associated equivalences arerobustfollowing Montalbán, i.e., stable under small variations of the theorems at hand. Working in Kohlenbach’shigher-orderRM, we obtain two new and long series of equivalences based on theorems due to Bolzano, Weierstrass, Jordan, and Cantor; these equivalences are extremely robust and have no counterpart among the Big Five systems. Thus, higher-order RM is much richer than its second-order cousin, boasting at least two extra ‘Big’ systems. (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.

Say that a d.c.e. degree d is isolated by a c.e. degree b, if bMathematics Subject Classification (2000): 03D25, 03D30, 03D35 RID=""ID="" Key words or phrases: Computably (...) enumerable set – d.c.e. degree – Isolation – High/low hierarchy RID=""ID="" Ishmukhametov's research is supported by RFBR grant 01-01-00733, and Wu's research is supported by the Marsden Fund of New Zealand. Wu would like to thank his supervisor, Prof. Rod Downey, for his many helpful suggestions and comments. (shrink)

We study the degrees of unsolvability of sets which are cohesive . We answer a question raised by the first author in 1972 by showing that there is a cohesive set A whose degree a satisfies a' = 0″ and hence is not high. We characterize the jumps of the degrees of r-cohesive sets, and we show that the degrees of r-cohesive sets coincide with those of the cohesive sets. We obtain analogous results for strongly hyperimmune and strongly hyperhyperimmune sets (...) in place of r-cohesive and cohesive sets, respectively. We show that every strongly hyperimmune set whose degree contains either a Boolean combination of ∑2 sets or a 1-generic set is of high degree. We also study primitive recursive analogues of these notions and in this case we characterize the corresponding degrees exactly. MSC: 03D30, 03D55. (shrink)

This paper introduces the notion of cW10-creative set, which strengthens that of semicreative set in a similar way as complete creativity strengthens creativity. Two results are proven, both of which imply that not all semicreative sets are cW10-creative. First, it is shown that semicreative Dedekind cuts cannot be cW10-creative; the existence of semicreative Dedekind cuts was shown by Soare. Secondly, it is shown that if A ⊕ B, the join of A and B, is cW10-creative, then either A or B (...) is cW10-creative, and the same is not true with ‘cW10-creative’ replaced by ‘semicreative’. Moreover, sets A, B which provide a counterexample for can be constructed within any given nonrecursive r.e. T-degrees a, b. MSC: 03D30. (shrink)

We investigate the polynomial time isomorphic type structure of (the class of tally, polynomial time computable sets). We partition P T into six parts: D −, D^ − , C, S, F, F^, and study their p-isomorphic properties separately. The structures of , , and are obvious, where F, F^, and C are the class of tally finite sets, the class of tally co-finite sets, and the class of tally bi-dense sets respectively. The following results for the structures of and (...) will be proved, where D^ is the class of tally, co-dense, polynomial time computable sets and S is the class of tally, scatted (i.e., neither dense nor co-dense), polynomial time computable sets. 1. is a countable distributive lattice with the greatest element. 2. Infinitely many intervals in can be distinguished by first order formulas. 3. There exist infinitely many nontrivial automorphisms for . 4. is not distributive, but any interval in is a countable distributive lattice. RID=""ID="" Mathematics Subject Classification (2000): 03D15, 03D25, 03D30, 03D35, 06A06, 06B20 RID=""ID="" Key words or phrases: Computational complexity – Polynomial time – Degree structure – Lattice – Isomorphism RID=""ID="" Part of this work was done when the author was a PhD student at the University of Heidelberg under the direction of Professor Ambos-Spies. (shrink)

We study the structure of Σ11 equivalence relations on hyperarithmetical subsets of ω under reducibilities given by hyperarithmetical or computable functions, called h-reducibility and FF-reducibility, respectively. We show that the structure is rich even when one fixes the number of properly equation imagei.e., Σ11 but not equation image equivalence classes. We also show the existence of incomparable Σ11 equivalence relations that are complete as subsets of ω × ω with respect to the corresponding reducibility on sets. We study complete Σ11 (...) equivalence relations and show that existence of infinitely many properly Σ11 equivalence classes that are complete as Σ11 sets is necessary but not sufficient for a relation to be complete in the context of Σ11 equivalence relations. (shrink)

Recall that B is PA relative to A if B computes a member of every nonempty $\Pi ^0_1(A)$ class. This two-place relation is invariant under Turing equivalence and so can be thought of as a binary relation on Turing degrees. Miller and Soskova [23] introduced the notion of a $\Pi ^0_1$ class relative to an enumeration oracle A, which they called a $\Pi ^0_1{\left \langle {A}\right \rangle }$ class. We study the induced extension of the relation B is PA relative (...) to A to enumeration oracles and hence enumeration degrees. We isolate several classes of enumeration degrees based on their behavior with respect to this relation: the PA bounded degrees, the degrees that have a universal class, the low for PA degrees, and the ${\left \langle {\text {self}\kern1pt}\right \rangle }$ -PA degrees. We study the relationship between these classes and other known classes of enumeration degrees. We also investigate a group of classes of enumeration degrees that were introduced by Kalimullin and Puzarenko [14] based on properties that are commonly studied in descriptive set theory. As part of this investigation, we give characterizations of three of their classes in terms of a special sub-collection of relativized $\Pi ^0_1$ classes—the separating classes. These three can then be seen to be direct analogues of three of our classes. We completely determine the relative position of all classes in question. (shrink)

The tower number ${\mathfrak t}$ and the ultrafilter number $\mathfrak {u}$ are cardinal characteristics from set theory. They are based on combinatorial properties of classes of subsets of $\omega $ and the almost inclusion relation $\subseteq ^*$ between such subsets. We consider analogs of these cardinal characteristics in computability theory.We say that a sequence $(G_n)_{n \in {\mathbb N}}$ of computable sets is a tower if $G_0 = {\mathbb N}$, $G_{n+1} \subseteq ^* G_n$, and $G_n\smallsetminus G_{n+1}$ is infinite for each n. (...) A tower is maximal if there is no infinite computable set contained in all $G_n$. A tower ${\left \langle {G_n}\right \rangle }_{n\in \omega }$ is an ultrafilter base if for each computable R, there is n such that $G_n \subseteq ^* R$ or $G_n \subseteq ^* \overline R$ ; this property implies maximality of the tower. A sequence $(G_n)_{n \in {\mathbb N}}$ of sets can be encoded as the “columns” of a set $G\subseteq \mathbb N$. Our analogs of ${\mathfrak t}$ and ${\mathfrak u}$ are the mass problems of sets encoding maximal towers, and of sets encoding towers that are ultrafilter bases, respectively. The relative position of a cardinal characteristic broadly corresponds to the relative computational complexity of the mass problem. We use Medvedev reducibility to formalize relative computational complexity, and thus to compare such mass problems to known ones.We show that the mass problem of ultrafilter bases is equivalent to the mass problem of computing a function that dominates all computable functions, and hence, by Martin’s characterization, it captures highness. On the other hand, the mass problem for maximal towers is below the mass problem of computing a non-low set. We also show that some, but not all, noncomputable low sets compute maximal towers: Every noncomputable (low) c.e. set computes a maximal tower but no 1-generic $\Delta ^0_2$ -set does so.We finally consider the mass problems of maximal almost disjoint, and of maximal independent families. We show that they are Medvedev equivalent to maximal towers, and to ultrafilter bases, respectively. (shrink)

The Probably Approximately Correct (PAC) learning is a machine learning model introduced by Leslie Valiant in 1984. The PACi reducibility refers to the PAC reducibility independent of size and computation time. This reducibility in PAC learning resembles the reducibility in Turing computability. The ordering of concept classes under PAC reducibility is nonlinear, even when restricted to particular concrete examples.Due to the resemblance to Turing Reducibility, we suspected that there could be incomparable PACi and PAC degrees for the PACi and PAC (...) reducibilities as in Turing incomparable degrees. In 1957 Friedberg and in 1956 Muchnik independently solved the Post problem by constructing computably enumerable sets A and B of incomparable degrees using the priority construction method. We adapt this idea to PACi and PAC reducibilities and construct two effective concept classes C and D such that C is not reducible to D and vice versa. When considering PAC reducibility it was necessary to work on the size of an effective concept class, thus we use Kolmogorov complexity to obtain the size. The non-learnability of concept classes in the PAC learning model is explained by the existence of PAC incomparable degrees.Analogous to the Turing jump, we give a jump operation on effective concept classes for the zero jump. To define the zero jump operator for PACi degrees the join of all the effective concept classes is constructed and proved that it is a greatest element. There are many properties proven for existing degrees. Thus we can explore proving those properties to PACi and PAC degrees. But if we prove an embedding from those degrees to PACi and PAC degrees then those properties will be true for PACi and PAC degrees without explicitly proving them.Abstract prepared by Dodamgodage Gihnee M. Senadheera and taken directly from the thesisE-mail: [email protected]: https://www.proquest.com/docview/2717762461/abstract/ACD19F29A8774AF6PQ/1?accountid=13864. (shrink)

The Friedman–Stanley jump, extensively studied by descriptive set theorists, is a fundamental tool for gauging the complexity of Borel isomorphism relations. This paper focuses on a natural computable analog of this jump operator for equivalence relations on $\omega $, written ${\dotplus }$, recently introduced by Clemens, Coskey, and Krakoff. We offer a thorough analysis of the computable Friedman–Stanley jump and its connections with the hierarchy of countable equivalence relations under the computable reducibility $\leq _c$. In particular, we show that this (...) jump gives benchmark equivalence relations going up the hyperarithmetic hierarchy and we unveil the complicated highness hierarchy that arises from ${\dotplus }$. (shrink)

We study the relative computational power of structures related to the ordered field of reals, specifically using the notion of generic Muchnik reducibility. We show that any expansion of the reals by a continuous function has no more computing power than the reals, answering a question of Igusa, Knight, and Schweber [7]. On the other hand, we show that there is a certain Borel expansion of the reals that is strictly more powerful than the reals and such that any Borel (...) quotient of the reals reduces to it. (shrink)

It is known that every non-universal self-full degree in the structure of the degrees of computably enumerable equivalence relations (ceers) under computable reducibility has exactly one strong minimal cover. This leaves little room for embedding wide partial orders as initial segments using self-full degrees. We show that considerably more can be done by staying entirely inside the collection of non-self-full degrees. We show that the poset can be embedded as an initial segment of the degrees of ceers with infinitely many (...) classes. A further refinement of the proof shows that one can also embed the free distributive lattice generated by the lower semilattice as an initial segment of the degrees of ceers with infinitely many classes. (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)

Given a reducibility ⩽r, we say that an infinite set A is r-introimmune if A is not r-reducible to any of its subsets B with |A\B| = ∞. We consider the many-one reducibility ⩽m and we prove the existence of a low1 m-introimmune set in Π01 and the existence of a low1 bi-m-introimmune set.

Working toward showing the decidability of the $\forall \exists $ -theory of the ${\Sigma ^0_2}$ -enumeration degrees, we prove that no so-called Ahmad pair of ${\Sigma ^0_2}$ -enumeration degrees can join to ${\mathbf 0}_e'$.