A non-splitting theorem for d.r.e. sets

Annals of Pure and Applied Logic 82 (1):17-96 (1996)
  Copy   BIBTEX

Abstract

A set of natural numbers is called d.r.e. if it may be obtained from some recursively enumerable set by deleting the numbers belonging to another recursively enumerable set. Sacks showed that for each non-recursive recursively enumerable set A there are disjoint recursively enumerable sets B, C which cover A such that A is recursive in neither A ∩ B nor A ∩ C. In this paper, we construct a counterexample which shows that Sacks's theorem is not in general true when A is d.r.e. rather than r.e

Categories

Keywords

Reprint years

DOI

10.1016/0168-0072(95)00070-4

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 93,031

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Difference Sets and Recursion Theory.James H. Schmerl - 1998 - Mathematical Logic Quarterly 44 (4):515-521.
On a Class of Recursively Enumerable Sets.Farzad Didehvar - 1999 - Mathematical Logic Quarterly 45 (4):467-470.
On recursive enumerability with finite repetitions.Stephan Wehner - 1999 - Journal of Symbolic Logic 64 (3):927-945.
On Recursive Enumerability with Finite Repetitions.Stephan Wehner - 1999 - Journal of Symbolic Logic 64 (3):927-945.
On the r.e. predecessors of d.r.e. degrees.Shamil Ishmukhametov - 1999 - Archive for Mathematical Logic 38 (6):373-386.
Effective Nonrecursiveness.Takeshi Yamaguchi - 1997 - Mathematical Logic Quarterly 43 (1):45-48.
Splitting theorems for speed-up related to order of enumeration.A. M. Dawes - 1982 - Journal of Symbolic Logic 47 (1):1-7.
Recursively enumerable generic sets.Wolfgang Maass - 1982 - Journal of Symbolic Logic 47 (4):809-823.
The undecidability of the lattice of R.E. closed subsets of an effective topological space.Sheryl Silibovsky Brady & Jeffrey B. Remmel - 1987 - Annals of Pure and Applied Logic 35 (C):193-203.
Recursive constructions in topological spaces.Iraj Kalantari & Allen Retzlaff - 1979 - Journal of Symbolic Logic 44 (4):609-625.

Analytics

Added to PP
2014-01-16

Downloads
43 (#380,703)

6 months
8 (#416,172)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

A non-splitting theorem for d.r.e. sets.Xiaoding Yi - 1996 - Annals of Pure and Applied Logic 82 (1):17-96.

Add more citations

References found in this work

The d.r.e. degrees are not dense.S. Cooper, Leo Harrington, Alistair Lachlan, Steffen Lempp & Robert Soare - 1991 - Annals of Pure and Applied Logic 55 (2):125-151.
The density of the low2 n-r.e. degrees.S. Barry Cooper - 1991 - Archive for Mathematical Logic 31 (1):19-24.
A non-splitting theorem for d.r.e. sets.Xiaoding Yi - 1996 - Annals of Pure and Applied Logic 82 (1):17-96.

Add more references