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
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 49,040
Through your library

References found in this work BETA

Theorie der Numerierungen I.Ju L. Eršov - 1973 - Mathematical Logic Quarterly 19 (19‐25):289-388.
Theorie der Numerierungen II.J. U. L. Eršov - 1975 - Mathematical Logic Quarterly 21 (1):473-584.
Theorie Der Numerierungen III.Ju L. Erš - 1977 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 23 (19-24):289-371.
Theorie Der Numerierungen III.Ju L. Erš - 1976 - 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

Presburger Sets and P-Minimal Fields.Raf Cluckers - 2003 - Journal of Symbolic Logic 68 (1):153-162.
A Special Class of Almost Disjoint Families.Thomas E. Leathrum - 1995 - Journal of Symbolic Logic 60 (3):879-891.
Definable Open Sets As Finite Unions of Definable Open Cells.Simon Andrews - 2010 - Notre Dame Journal of Formal Logic 51 (2):247-251.
Trees and Diagrams of Decomposition.Anita Wasilewska - 1985 - Studia Logica 44 (2):139 - 158.
Sets and Point-Sets: Five Grades of Set-Theoretic Involvement in Geometry.John P. Burgess - 1988 - PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association 1988:456 - 463.
Decidable Subspaces and Recursively Enumerable Subspaces.C. J. Ash & R. G. Downey - 1984 - Journal of Symbolic Logic 49 (4):1137-1145.
Cohen-Stable Families of Subsets of Integers.Miloš S. Kurilić - 2001 - Journal of Symbolic Logic 66 (1):257-270.


Added to PP index

Total views
49 ( #186,765 of 2,311,025 )

Recent downloads (6 months)
11 ( #65,594 of 2,311,025 )

How can I increase my downloads?


My notes

Sign in to use this feature