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)|
References found in this work BETA
Theorie Der Numerierungen III.Ju L. Erš - 1977 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 23 (19-24):289-371.
Citations of this work BETA
No citations found.
Similar books and articles
Presburger Sets and P-Minimal Fields.Raf Cluckers - 2003 - Journal of Symbolic Logic 68 (1):153-162.
The Theory of the Recursively Enumerable Weak Truth-Table Degrees is Undecidable.Klaus Ambos-Spies, André Nies & Richard A. Shore - 1992 - Journal of Symbolic Logic 57 (3):864-874.
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.
Analytic Cell Decomposition and the Closure of P-Adic Semianalytic Sets.Nianzheng Liu - 1997 - Journal of Symbolic Logic 62 (1):285-303.
A Continuous Movement Version of the Banach-Tarski Paradox: A Solution to de Groot's Problem.Trevor M. Wilson - 2005 - Journal of Symbolic Logic 70 (3):946 - 952.
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.
Completions of PA: Models and Enumerations of Representable Sets.Alex M. McAllister - 1998 - Journal of Symbolic Logic 63 (3):1063-1082.
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.
Non-Distributive Upper Semilattice of Kleene Degrees.Hisato Muraki - 1999 - Journal of Symbolic Logic 64 (1):147-158.
Added to index2010-09-12
Total downloads21 ( #232,644 of 2,153,861 )
Recent downloads (6 months)2 ( #279,759 of 2,153,861 )
How can I increase my downloads?