We examine how degrees of computably enumerable equivalence relations under computable reduction break down into isomorphism classes. Two ceers are isomorphic if there is a computable permutation of ω which reduces one to the other. As a method of focusing on nontrivial differences in isomorphism classes, we give special attention to weakly precomplete ceers. For any degree, we consider the number of isomorphism types contained in the degree and the number of isomorphism types of weakly precomplete ceers contained in the (...) degree. We show that the number of isomorphism types must be 1 or ω, and it is 1 if and only if the ceer is self-full and has no computable classes. On the other hand, we show that the number of isomorphism types of weakly precomplete ceers contained in the degree can be any member of $[0,\omega ]$. In fact, for any $n \in [0,\omega ]$, there is a degree d and weakly precomplete ceers ${E_1}, \ldots,{E_n}$ in d so that any ceer R in d is isomorphic to ${E_i} \oplus D$ for some $i \le n$ and D a ceer with domain either finite or ω comprised of finitely many computable classes. Thus, up to a trivial equivalence, the degree d splits into exactly n classes.We conclude by answering some lingering open questions from the literature: Gao and Gerdes [11] define the collection of essentially FC ceers to be those which are reducible to a ceer all of whose classes are finite. They show that the index set of essentially FC ceers is ${\rm{\Pi }}_3^0$-hard, though the definition is ${\rm{\Sigma }}_4^0$. We close the gap by showing that the index set is ${\rm{\Sigma }}_4^0$-complete. They also use index sets to show that there is a ceer all of whose classes are computable, but which is not essentially FC, and they ask for an explicit construction, which we provide.Andrews and Sorbi [4] examined strong minimal covers of downwards-closed sets of degrees of ceers. We show that if $\left$ is a uniform c.e. sequence of non universal ceers, then $\left\{ {{ \oplus _{i \le j}}{E_i}|j \in \omega } \right\}$ has infinitely many incomparable strong minimal covers, which we use to answer some open questions from [4].Lastly, we show that there exists an infinite antichain of weakly precomplete ceers. (shrink)

Using computable reducibility ⩽ on equivalence relations, we investigate weakly precomplete ceers (a “ceer” is a computably enumerable equivalence relation on the natural numbers), and we compare their class with the more restricted class of precomplete ceers. We show that there are infinitely many isomorphism types of universal (in fact uniformly finitely precomplete) weakly precomplete ceers, that are not precomplete; and there are infinitely many isomorphism types of non‐universal weakly precomplete ceers. Whereas the Visser space of a precomplete ceer always (...) contains an infinite effectively discrete subset, there exist weakly precomplete ceers whose Visser spaces do not contain infinite effectively discrete subsets. As a consequence, contrary to precomplete ceers which always yield partitions into effectively inseparable sets, we show that although weakly precomplete ceers always yield partitions into computably inseparable sets, nevertheless there are weakly precomplete ceers for which no equivalence class is creative. Finally, we show that the index set of the precomplete ceers is Σ3‐complete, whereas the index set of the weakly precomplete ceers is Π3‐complete. As a consequence of these results, we also show that the index sets of the uniformly precomplete ceers and of the e‐complete ceers are Σ3‐complete. (shrink)

Khutoretskii's Theorem states that the Rogers semilattice of any family of c.e. sets has either at most one or infinitely many elements. A lemma in the inductive step of the proof shows that no Rogers semilattice can be partitioned into a principal ideal and a principal filter. We show that such a partitioning is possible for some family of d.c.e. sets. In fact, we construct a family of c.e. sets which, when viewed as a family of d.c.e. sets, has (up (...) to equivalence) exactly two computable Friedberg numberings ¼ and ν, and ¼ reduces to any computable numbering not equivalent to ν. The question of whether the full statement of Khutoretskii's Theorem fails for families of d.c.e. sets remains open. (shrink)

We work with weakly precomplete equivalence relations introduced by Badaev. The weak precompleteness is a natural notion inspired by various fixed point theorems in computability theory. Let E be an equivalence relation on the set of natural numbers $$\omega $$, having at least two classes. A total function f is a diagonal function for E if for every x, the numbers x and f(x) are not E-equivalent. It is known that in the case of c.e. relations E, the weak precompleteness (...) of E is equivalent to the lack of computable diagonal functions for E. Here we prove that this result fails already for $$\Delta ^0_2$$ equivalence relations, starting with the $$\Pi ^{-1}_2$$ level. We focus on the Turing degrees of possible diagonal functions. We prove that for any noncomputable c.e. degree $${\textbf{d}}$$, there exists a weakly precomplete c.e. equivalence E admitting a $${\textbf{d}}$$ -computable diagonal function. We observe that a Turing degree $${\textbf{d}}$$ can compute a diagonal function for every $$\Delta ^0_2$$ equivalence relation E if and only if $${\textbf{d}}$$ computes $${\textbf{0}}'$$. On the other hand, every PA degree can compute a diagonal function for an arbitrary c.e. equivalence E. In addition, if $${\textbf{d}}$$ computes diagonal functions for all c.e. E, then $${\textbf{d}}$$ must be a DNC degree. (shrink)

Let a be a Kleene's ordinal notation of a nonzero computable ordinal. We give a sufficient condition on a, so that for every \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\Sigma ^{-1}_a$\end{document}‐computable family of two embedded sets, i.e., two sets A, B, with A properly contained in B, the Rogers semilattice of the family is infinite. This condition is satisfied by every notation of ω; moreover every nonzero computable ordinal that is not sum of any two smaller ordinals has a notation that satisfies this condition. On the (...) other hand, we also give a sufficient condition on a, that yields that there is a \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\Sigma ^{-1}_a$\end{document}‐computable family of two embedded sets, whose Rogers semilattice consists of exactly one element; this condition is satisfied by all notations of every successor ordinal bigger than 1, and by all notations of the ordinal ω + ω; moreover every computable ordinal that is sum of two smaller ordinals has a notation that satisfies this condition. We also show that for every nonzero n ∈ ω, or n = ω, and every notation a of a nonzero ordinal there exists a \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\Sigma ^{-1}_a$\end{document}‐computable family of cardinality n, whose Rogers semilattice consists of exactly one element. (shrink)

The different behaviour of total and partial numberings with respect to the reducibility preorder is investigated. Partial numberings appear quite naturally in computability studies for topological spaces. The degrees of partial numberings form a distributive lattice which in the case of an infinite numbered set is neither complete nor contains a least element. Friedberg numberings are no longer minimal in this situation. Indeed, there is an infinite descending chain of non-equivalent Friedberg numberings below every given numbering, as well as an (...) uncountable antichain. (shrink)

We show that for every ordinal notation ξ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\xi}$$\end{document} of a nonzero computable ordinal, there exists a Σξ-1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Sigma^{-1}_\xi}$$\end{document}—computable family which up to equivalence has exactly one Friedberg numbering, which does not induce the least element in the corresponding Rogers semilattice.