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

Journal of Symbolic Logic 74 (2):618-640 (2009)
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
Keywords d.c.e. sets   Rogers semilattice   Khutoretskii's Theorem
Categories (categorize this paper)
DOI 10.2178/jsl/1243948330
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history Request removal from index
Download options
PhilPapers Archive

Upload a copy of this paper     Check publisher's policy on self-archival     Papers currently archived: 23,209
External links
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library
References found in this work BETA
Ju L. Erš (1977). Theorie Der Numerierungen III. Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 23 (19-24):289-371.
Ju L. Eršov (1973). Theorie der Numerierungen I. Mathematical Logic Quarterly 19 (19‐25):289-388.
J. U. L. Eršov (1975). Theorie der Numerierungen II. Mathematical Logic Quarterly 21 (1):473-584.
Ju L. Erš (1977). Theorie Der Numerierungen III. Mathematical Logic Quarterly 23 (19‐24):289-371.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles
Raf Cluckers (2003). Presburger Sets and P-Minimal Fields. Journal of Symbolic Logic 68 (1):153-162.
John P. Burgess (1988). Sets and Point-Sets: Five Grades of Set-Theoretic Involvement in Geometry. PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association 1988:456 - 463.
J. B. Nation (2013). Lattices of Theories in Languages Without Equality. Notre Dame Journal of Formal Logic 54 (2):167-175.

Monthly downloads

Added to index


Total downloads

19 ( #243,691 of 1,941,049 )

Recent downloads (6 months)

1 ( #458,101 of 1,941,049 )

How can I increase my downloads?

My notes
Sign in to use this feature

Start a new thread
There  are no threads in this forum
Nothing in this forum yet.