A decomposition of the Rogers semilattice of a family of d.c.e. sets

2009

Closed access Metadata (CSL-JSON)
DOI 10.2178/jsl/1243948330
Data confidence 70 medium
How this score is calculated

It is built from checkable properties of the record itself: whether the article has a DOI, how many independent sources confirmed its data, whether the required fields are filled in, and how recent the latest confirmation is. Disagreement between sources and a missing identifier lower it. A value of 80 or above means the record was published without further checking; 60 to 79 means it is published at reduced confidence, with a manual check advisable. A record verified by an editor by hand is never pushed below 90 by a recalculation. This scores our data about the article, not the article itself.

Abstract

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