Abstract We study the structure of the c.e. $Q$- and $sQ$-degrees. For both structures, we show that there are join irreducible degrees but no Ahmad pairs. We show that the structures are not distributive, and that the lattice $N_{5}$ embeds in both structures. On the other hand the lattice $M_{5}$ cannot be embedded in the c.e. $sQ$-degrees, but a critical triple can be embedded. Finally, we show that no initial segment of the c.e. $sQ$-degrees or the c.e. $Q$-degrees is a lattice.

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

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

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

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

S. Barry Cooper, Mariya I. Soskova; The incomputable, Journal of Logic and Computation, Volume 23, Issue 6, 1 December 2013, Pages 1143–1144, https://doi.o

Abstract We show that every splitting of in the local structure of the enumeration degrees, , contains at least one low-cuppable member. We apply this new structural property to show that the classes of all -pairs in , all downwards properly enumeration degrees and all upwards properly enumeration degrees are first order definable in .

Abstract We show that the theory of the local structure of the enumeration degrees is computably isomorphic to the theory of first order arithmetic. We introduce a novel coding method, using the notion of a -pair, to code a large class of countable relations.

We prove that every countable distributive lattice is embeddable in the Σ02 enumeration degrees via a 0—1 preserving monomorphism. Moreover, we prove that every countable distributive lattice is embeddable below arbitrary Δ02 degree via a 0 preserving monomorphism.

Journal Article Embedding countable partial orderings in the enumeration degrees and the ω-enumeration degrees Get access Mariya I. Soskova, Mariya I. Soskova Faculty of Mathematics, Sofia University, 5 James Bourchier Boulevard, 1164 Sofia, Bulgaria.E-mail: [email protected]; [email protected] Search for other works by this author on: Oxford Academic Google Scholar Ivan N. Soskov Ivan N. Soskov Faculty of Mathematics, Sofia University, 5 James Bourchier Boulevard, 1164 Sofia, Bulgaria.E-mail: [email protected]; [email protected] Search for other works by this author on: Oxford Academic Google Scholar Journal of Logic and Computation, Volume 22, Issue 4, August 2012, Pages 927–952, https://doi.org/10.1093/logcom/exq051 Published: 23 October 2010 Article history Received: 15 October 2009 Published: 23 October 2010

In this paper we prove that every non-zero Δ20e-degree is cuppable to 0e′ by a 1-generic Δ20e-degree (and is thus low and non-total), and that every non-zero ω-c.e. e-degree is cuppable to 0e′ by an incomplete 3-c.e. e-degree.

Abstract We say that A ≤LRB if every B-random number is A-random. Intuitively this means that if oracle A can identify some patterns on some real γ, oracle B can also find patterns on γ. In other words, B is at least as good as A for this purpose. We study the structure of the LR degrees globally and locally (i.e., restricted to the computably enumerable degrees) and their relationship with the Turing degrees. Among other results we show that whenever ∝ is not GL2 the LR degree of ∝ bounds degrees (so that, in particular, there exist LR degrees with uncountably many predecessors) and we give sample results which demonstrate how various techniques from the theory of the c.e. degrees can be used to prove results about the c.e. LR degrees.

§1. Introduction. Sacks [16] showed that every computably enumerable (c.e.) degree > 0 has a c.e. splitting. Hence, relativising, every c.e. degree has a Δ2 splitting above each proper predecessor (by ‘splitting’ we understand ‘nontrivial splitting’). Arslanov [1] showed that 0′ has a d.c.e. splitting above each c.e. a < 0′. On the other hand, Lachlan [11] proved the existence of a c.e. a < 0 which has no c.e. splitting above some proper c.e. predecessor, and Harrington [10] showed that one could take a = 0′. Splitting and nonsplitting techniques have had a number of consequences for definability and elementary equivalence in the degrees below 0′. Heterogeneous splittings are best considered in the context of cupping and non-cupping. Posner and Robinson [15] showed that every nonzero Δ2 degree can be nontrivially cupped to 0′, and Arslanov [1] showed that every c.e. degree > 0 can be d.c.e. cupped to 0′ (and hence since every d.c.e., or even n-c.e., degree has a nonzero c.e. predecessor, every n-c.e. degree > 0 is d.c.e. cuppable). Cooper [4] and Yates (see Miller [13]) showed the existence of degrees noncuppable in the c.e. degrees. Moreover, the search for relative cupping results was drastically limited by Cooper [5], and Slaman and Steel [17] (see also Downey [9]), who showed that there is a nonzero c.e. degree a below which even Δ2 cupping of c.e. degrees fails. We prove below what appears to be the strongest possible of such nonsplitting and noncupping results.

Journal Article Genericity and Non-bounding in the Enumeration degrees Get access Mariya Ivanova Soskova Mariya Ivanova Soskova Department of Pure Mathematics, University of Leeds, Leeds, LS2 9JT, UK E-mail: [email protected] Search for other works by this author on: Oxford Academic Google Scholar Journal of Logic and Computation, Volume 17, Issue 6, December 2007, Pages 1235–1255, https://doi.org/10.1093/logcom/exm042 Published: 09 October 2007 Article history Received: 18 October 2006 Published: 09 October 2007