David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Ezio Di Nucci
Jack Alan Reynolds
Learn more about PhilPapers
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)|
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
No references found.
Citations of this work BETA
No citations found.
Similar books and articles
Raf Cluckers (2003). Presburger Sets and P-Minimal Fields. Journal of Symbolic Logic 68 (1):153-162.
Klaus Ambos-Spies, André Nies & Richard A. Shore (1992). The Theory of the Recursively Enumerable Weak Truth-Table Degrees is Undecidable. Journal of Symbolic Logic 57 (3):864-874.
Thomas E. Leathrum (1995). A Special Class of Almost Disjoint Families. Journal of Symbolic Logic 60 (3):879-891.
Simon Andrews (2010). Definable Open Sets As Finite Unions of Definable Open Cells. Notre Dame Journal of Formal Logic 51 (2):247-251.
Anita Wasilewska (1985). Trees and Diagrams of Decomposition. Studia Logica 44 (2):139 - 158.
Nianzheng Liu (1997). Analytic Cell Decomposition and the Closure of P-Adic Semianalytic Sets. Journal of Symbolic Logic 62 (1):285-303.
Trevor M. Wilson (2005). A Continuous Movement Version of the Banach-Tarski Paradox: A Solution to de Groot's Problem. Journal of Symbolic Logic 70 (3):946 - 952.
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.
Alex M. McAllister (1998). Completions of PA: Models and Enumerations of Representable Sets. Journal of Symbolic Logic 63 (3):1063-1082.
C. J. Ash & R. G. Downey (1984). Decidable Subspaces and Recursively Enumerable Subspaces. Journal of Symbolic Logic 49 (4):1137-1145.
Miloš S. Kurilić (2001). Cohen-Stable Families of Subsets of Integers. Journal of Symbolic Logic 66 (1):257-270.
Hisato Muraki (1999). Non-Distributive Upper Semilattice of Kleene Degrees. Journal of Symbolic Logic 64 (1):147-158.
J. B. Nation (2013). Lattices of Theories in Languages Without Equality. Notre Dame Journal of Formal Logic 54 (2):167-175.
Added to index2010-09-12
Total downloads19 ( #184,740 of 1,789,829 )
Recent downloads (6 months)10 ( #82,832 of 1,789,829 )
How can I increase my downloads?