Answering an open question raised by Cooper, we show that there exist Δ 2 0 sets D and E such that the singleton degree of E is a minimal cover of the singleton degree of D . This shows that the Σ 2 0 singleton degrees, and the Δ 2 0 singleton degrees, are not dense (and consequently the Π 2 0 Q -degrees, and the Δ 2 0 Q -degrees, are not dense). Moreover D and E can be built to lie in the same enumeration degree.

Abstract In this article, we define and study the notion of a $(c,c_{1})$-cylinder, which turns out to be very useful instrument for investigating the relationships between conjunctive reducibility ($c$-reducibility) and its injective version $c_{1}$-reducibility. Using this notion, we prove the following results: (i) Neither hypersimple sets nor hemimaximal sets can be $(c,c_{1})$-cylinders; (ii) The $c$-degree of a noncomputable c.e. set contains either only one or infinitely many noncomputable $c_{1}$-degrees; (iii) the $c$-degree of either a hemimaximal set or a hypersimple set contains infinitely many noncomputable $c_{1}$-degrees.

Abstract We consider three strong reducibilities, $s_{1}, s_{2}, Q_{1}$ (where we identify a reducibility $\leqslant _r$ with its index $r$). The first two reducibilities can be viewed as injective versions of $s$-reducibility, whereas $Q_1$-reducibility can be viewed as an injective version of $Q$-reducibility. We have, with proper inclusions, $s_{1} \subset s_{2} \subset s$. It is well known that there is no minimal $s$-degree, and there is no minimal $Q$-degree. We show on the contrary that there exist minimal $\varDelta ^{0}_{2}$$s_{2}$-degrees and minimal $\varDelta ^{0}_{2}$$s_{1}$-degrees. On the other hand, both the $\varPi ^{0}_{1}$$s_{2}$-degrees and the $\varPi ^{0}_{1}$$s_{1}$-degrees are downwards dense. By the isomorphism of the $s_1$-degrees with the $Q_1$-degrees induced by complementation of sets, it follows that there exist minimal $\varDelta ^0_2$$Q_1$-degrees, but the c.e. $Q_{1}$-degrees are downwards dense.

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

Abstract In this article we prove the following results: (i) Every hemimaximal set has minimal $c_{1}$-degree, i.e. if $B$ is hemimaximal and $A$ is a c.e. set such that $A \le _{c_{1}} B$ then either $B \leq _{{c}_{1}} A$ or $A$ is computable. (ii) The $sQ$-degree of a c.e. set contains either only one or infinitely many c.e. $c$-degrees. (iii) If $A,B$ are c.e. cylinders in the same $sQ_{1}$-degree and $A<_{c_{1}} B$, then this $sQ_{1}$-degree contains infinitely many c.e. $c_{1}$-degrees.

Abstract A computably enumerable equivalence relation (ceer) $X$ is called self-full if whenever $f$ is a reduction of $X$ to $X$, then the range of $f$ intersects all $X$-equivalence classes. It is known that the infinite self-full ceers properly contain the dark ceers, i.e. the infinite ceers which do not admit an infinite computably enumerable transversal. Unlike the collection of dark ceers, which are closed under the operation of uniform join, we answer a question from [ 4] by showing that there are self-full ceers $X$ and $Y$ so that their uniform join $X\oplus Y$ is non-self-full. We then define and examine the hereditarily self-full ceers, which are the self-full ceers $X$ so that for any self-full $Y$, $X\oplus Y$ is also self-full: we show that they are closed under uniform join and that every non-universal degree in ${\operatorname{\textbf{Ceers}}}_{\operatorname{{\mathcal{I}}}}$ have infinitely many incomparable hereditarily self-full strong minimal covers. In particular, every non-universal ceer is bounded by a hereditarily self-full ceer. Thus, the hereditarily self-full ceers form a properly intermediate class in between the dark ceers and the infinite self-full ceers, which is closed under $\oplus $.

Abstract This paper is part of a project that is based on the notion of a dialectical system, introduced by Magari as a way of capturing trial and error mathematics. In Amidei et al. (2016, Rev. Symb. Logic, 9, 1–26) and Amidei et al. (2016, Rev. Symb. Logic, 9, 299–324), we investigated the expressive and computational power of dialectical systems, and we compared them to a new class of systems, that of quasi-dialectical systems, that enrich Magari’s systems with a natural mechanism of revision. In the present paper we consider a third class of systems, that of $p$-dialectical systems, that naturally combine features coming from the two other cases. We prove several results about $p$-dialectical systems and the sets that they represent. Then we focus on the completions of first-order theories. In doing so, we consider systems with connectives, i.e. systems that encode the rules of classical logic. We show that any consistent system with connectives represents the completion of a given theory. We prove that dialectical and $q$-dialectical systems coincide with respect to the completions that they can represent. Yet, $p$-dialectical systems are more powerful; we exhibit a $p$-dialectical system representing a completion of Peano Arithmetic that is neither dialectical nor $q$-dialectical.

(1) There is a finitely presented group with a word problem which is a uniformly effectively inseparable equivalence relation. (2) There is a finitely generated group of computable permutations with a word problem which is a universal co-computably enumerable equivalence relation. (3) Each c.e. truth-table degree contains the word problem of a finitely generated group of computable permutations.

Abstract Let $ \le _c $ be computable the reducibility on computably enumerable equivalence relations (or ceers). We show that for every ceerRwith infinitely many equivalence classes, the index sets $\left\{ {i:R_i \le _c R} \right\}$ (withRnonuniversal), $\left\{ {i:R_i \ge _c R} \right\}$ , and $\left\{ {i:R_i \equiv _c R} \right\}$ are ${\rm{\Sigma }}_3^0$ complete, whereas in caseRhas only finitely many equivalence classes, we have that $\left\{ {i:R_i \le _c R} \right\}$ is ${\rm{\Pi }}_2^0$ complete, and $\left\{ {i:R \ge _c R} \right\}$ (withRhaving at least two distinct equivalence classes) is ${\rm{\Sigma }}_2^0$ complete. Next, solving an open problem from [1], we prove that the index set of the effectively inseparable ceers is ${\rm{\Pi }}_4^0$ complete. Finally, we prove that the 1-reducibility preordering on c.e. sets is a ${\rm{\Sigma }}_3^0$ complete preordering relation, a fact that is used to show that the preordering relation $ \le _c $ on ceers is a ${\rm{\Sigma }}_3^0$ complete preordering relation.

Abstract Using properties of ${\cal K}$ -pairs of sets, we show that every nonzero enumeration degreeabounds a nontrivial initial segment of enumeration degrees whose nonzero elements have all the same jump asa. Some consequences of this fact are derived, that hold in the local structure of the enumeration degrees, including: There is an initial segment of enumeration degrees, whose nonzero elements are all high; there is a nonsplitting high enumeration degree; every noncappable enumeration degree is high; every nonzero low enumeration degree can be capped by degrees of any possible local jump (i.e., any jump that can be realized by enumeration degrees of the local structure); every enumeration degree that bounds a nonzero element of strictly smaller jump, is bounding; every low enumeration degree below a non low enumeration degreeacan be capped belowa.

Abstract We study computably enumerable equivalence relations (ceers), under the reducibility $R \le S$ if there exists a computable function f such that $x\,R\,y$ if and only if $f\left( x \right)\,\,S\,f\left( y \right)$ , for every $x,y$ . We show that the degrees of ceers under the equivalence relation generated by $\le$ form a bounded poset that is neither a lower semilattice, nor an upper semilattice, and its first-order theory is undecidable. We then study the universal ceers. We show that 1) the uniformly effectively inseparable ceers are universal, but there are effectively inseparable ceers that are not universal; 2) a ceer R is universal if and only if $R\prime \le R$ , where $R\prime$ denotes the halting jump operator introduced by Gao and Gerdes (answering an open question of Gao and Gerdes); and 3) both the index set of the universal ceers and the index set of the uniformly effectively inseparable ceers are ${\rm{\Sigma }}_3^0$ -complete (the former answering an open question of Gao and Gerdes).

Abstract We show that no nontrivial principal ideal of the enumeration degrees is linearly ordered: in fact, below every nonzero enumeration degree one can embed every countable partial order. The result can be relativized above any total degree: if a,b are enumeration degrees, with a total, and a < b, then in the degree interval (a,b), one can embed every countable partial order.

We show that the first-order theories of the s-degrees, and of the Q-degrees, are computably isomorphic to true second-order arithmetic.

Alexandra Soskova, S. Barry Cooper, Andrea Sorbi; Computability at Logic Colloquium 2009, Journal of Logic and Computation, Volume 22, Issue 4, 1 August 20

We show that the diamond lattice can be embedded into the Σ02enumeration degrees preserving 0 and 1, with atoms one high and Π01, and the other one low.

Abstract Let A be an infinite set and let K be creative: we show that K ≤QA if and only if K A. (Here ≤Q denotes Q-reducibility, and is the subreducibility of ≤Q obtained by requesting that Q-reducibility be provided by a computable function f such that Wf(x) ∩ Wf(y) = ∅. if x ≠ y.) Using this result we prove that A is hyperhyperimmune if and only if no subset B of A is s-complete, i.e., there is no subset B of A such that ≤sB, where ≤s denotes s-reducibility, and denotes the complement of K.

Abstract We show that every nonzero enumeration degree bounds a nonsplitting nonzero enumeration degree.

Abstract We show that there exist downwards properly (in fact noncuppable) e-degrees that are not high. We also show that every high e-degree bounds a noncuppable e-degree.

Abstract We show that every nonzero Δ20, e-degree bounds a minimal pair. On the other hand, there exist Σ20, e-degrees which bound no minimal pair.

Abstract We show that every finite lattice is embeddable into the Σ20 enumeration degrees via a lattice-theoretic embedding which preserves 0 and 1.

Abstract We show that for every enumeration degree a < 0′e there exists an e-degree c such that a ≤ c < 0′e, and all degrees b, with c ≤ b < 0′e, are properly Σ20.

Abstract We prove that each Σ20 set which is hypersimple relative to ∅′ is noncuppable in the structure of the Σ20 enumeration degrees. This gives a connection between properties of Σ20 sets under inclusion and and the Σ20 enumeration degrees. We also prove that some low non-computably enumerable enumeration degree contains no set which is simple relative to ∅′.

We prove the following three theorems on the enumeration degrees of ∑20 sets. Theorem A: There exists a nonzero noncuppable ∑20 enumeration degree. Theorem B: Every nonzero Δ20enumeration degree is cuppable to 0′e by an incomplete total enumeration degree. Theorem C: There exists a nonzero low Δ20 enumeration degree with the anticupping property.

Abstract We prove that there exists a noncappable enumeration degree strictly below 0e′.

Abstract This paper investigates the algebraic structure of the Medvedev lattice . We prove that is not a Heyting algebra. We point out some relations between and the Dyment lattice and the Mučnik lattice. Some properties of the degrees of enumerability are considered. We give also a result on embedding countable distributive lattices in the Medvedev lattice.

Recursion categories have been proposed by Di Paola and Heller in [DPH] as the basis for a category-theoretic approach to recursion theory, in the context of a more general and ambitious project of a purely algebraic treatment of incompleteness phenomena. The way in which the classical notion of creative set is rendered in this new category-theoretic framework plays, therefore, a central role. This is done in [DPH] (Definition 8.1) by defining the notion of creative domains or, rather, domains which are creative relative to some criterion: thus, in a recursion category, every criterion provides a notion of creativeness. A basic result on creative domains (cf. [DPH, Theorem 8.13]) is that, under certain assumptions, a version of the classical result, due to Myhill [MYH], stating that every creative set is complete, holds: in a recursion category with equality (i.e. exists for every object X) and having enough atoms, every domain which is creative with respect to atoms is also complete.

When dealing with axiomatic theories from a recursion-theoretic point of view, the notion of r.e. preordering naturally arises. We agree that an r.e. preorder is a pair = 〈P, ≤P〉 such that P is an r.e. subset of the set of natural numbers (denoted by ω), ≤P is a preordering on P and the set {〈;x, y〉: x ≤Py} is r.e.. Indeed, if is an axiomatic theory, the provable implication of yields a preordering on the class of (Gödel numbers of) formulas of . Of course, if ≤P is a preordering on P, then it yields an equivalence relation ~P on P, by simply letting x ~Py iff x ≤Py and y ≤Px. Hence, in the case of P = ω, any preordering yields an equivalence relation on ω and consequently a numeration in the sense of [4]. It is also clear that any equivalence relation on ω (hence any numeration) can be regarded as a preordering on ω. In view of this connection, we sometimes apply to the theory of preorders some of the concepts from the theory of numerations (see also Eršov [6]). Our main concern will be in applications of these concepts to logic, in particular as regards sufficiently strong axiomatic theories (essentially the ones in which recursive functions are representable). From this point of view it seems to be of some interest to study some remarkable prelattices and Boolean prealgebras which arise from such theories. It turns out that these structures enjoy some rather surprising lattice-theoretic and universal recursion-theoretic properties. After making our main definitions in §1, we examine universal recursion-theoretic properties of some r.e. prelattices in §2.

Abstract Given two (positive) equivalence relations ~1, ~2 on the set ω of natural numbers, we say that ~1 is m-reducible to ~2 if there exists a total recursive function h such that for every x, y ∈ ω, we have x ~1y iff hx ~2hy. We prove that the equivalence relation induced in ω by a positive precomplete numeration is complete with respect to this reducibility (and, moreover, a “uniformity property” holds). This result allows us to state a classification theorem for positive equivalence relations (Theorem 2). We show that there exist nonisomorphic positive equivalence relations which are complete with respect to the above reducibility; in particular, we discuss the provable equivalence of a strong enough theory: this relation is complete with respect to reducibility but it does not correspond to a precomplete numeration. From this fact we deduce that an equivalence relation on ω can be strongly represented by a formula (see Definition 8) iff it is positive. At last, we interpret the situation from a topological point of view. Among other things, we generalize a result of Visser by showing that the topological space corresponding to a partition in e.i. sets is irreducible and we prove that the set of equivalence classes of true sentences is dense in the Lindenbaum algebra of the theory.