Degree theoretical splitting properties of recursively enumerable sets

Journal of Symbolic Logic 53 (4):1110-1137 (1988)
  Copy   BIBTEX

Abstract

A recursively enumerable splitting of an r.e. setAis a pair of r.e. setsBandCsuch thatA=B∪CandB∩C= ⊘. Since for such a splitting degA= degB∪ degC, r.e. splittings proved to be a quite useful notion for investigations into the structure of the r.e. degrees. Important splitting theorems, like Sacks splitting [S1], Robinson splitting [R1] and Lachlan splitting [L3], use r.e. splittings.Since each r.e. splitting of a set induces a splitting of its degree, it is natural to study the relation between the degrees of r.e. splittings and the degree splittings of a set. We say a setAhas thestrong universal splitting property if each splitting of its degree is represented by an r.e. splitting of itself, i.e., if for degA=b∪cthere is an r.e. splittingB, CofAsuch that degB=band degC=c. The goal of this paper is the study of this splitting property.In the literature some weaker splitting properties have been studied as well as splitting properties which imply failure of the SUSP.

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 100,978

External links

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

Through your library

Similar books and articles

Splitting theorems in recursion theory.Rod Downey & Michael Stob - 1993 - Annals of Pure and Applied Logic 65 (1):1-106.
Friedberg splittings of recursively enumerable sets.Rod Downey & Michael Stob - 1993 - Annals of Pure and Applied Logic 59 (3):175-199.
A non-splitting theorem for d.r.e. sets.Xiaoding Yi - 1996 - Annals of Pure and Applied Logic 82 (1):17-96.
On the Universal Splitting Property.Rod Downey - 1997 - Mathematical Logic Quarterly 43 (3):311-320.
Splittings of 0' into the Recursively Enumerable Degrees.Xiaoding Yi - 1996 - Mathematical Logic Quarterly 42 (1):249-269.
An extended Lachlan splitting theorem.Steffen Lempp & Sui Yuefei - 1996 - Annals of Pure and Applied Logic 79 (1):53-59.
Friedberg splittings in Σ3 0 quotient lattices of.Todd Hammond - 1999 - Journal of Symbolic Logic 64 (4):1403-1406.
Splitting theorems and the jump operator.R. G. Downey & Richard A. Shore - 1998 - Annals of Pure and Applied Logic 94 (1-3):45-52.
A non-splitting theorem in the enumeration degrees.Mariya Ivanova Soskova - 2009 - Annals of Pure and Applied Logic 160 (3):400-418.
On the r.e. predecessors of d.r.e. degrees.Shamil Ishmukhametov - 1999 - Archive for Mathematical Logic 38 (6):373-386.

Analytics

Added to PP
2009-01-28

Downloads
43 (#515,708)

6 months
3 (#1,470,969)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Splitting theorems in recursion theory.Rod Downey & Michael Stob - 1993 - Annals of Pure and Applied Logic 65 (1):1-106.
Completely mitotic R.E. degrees.R. G. Downey & T. A. Slaman - 1989 - Annals of Pure and Applied Logic 41 (2):119-152.
Parameter definability in the recursively enumerable degrees.André Nies - 2003 - Journal of Mathematical Logic 3 (01):37-65.
Embeddings of N5 and the contiguous degrees.Klaus Ambos-Spies & Peter A. Fejer - 2001 - Annals of Pure and Applied Logic 112 (2-3):151-188.

View all 7 citations / Add more citations

References found in this work

Theory of Recursive Functions and Effective Computability.Hartley Rogers - 1971 - Journal of Symbolic Logic 36 (1):141-146.
The density of the nonbranching degrees.Peter A. Fejer - 1983 - Annals of Pure and Applied Logic 24 (2):113-130.
The Priority Method I.A. H. Lachlans - 1967 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 13 (1-2):1-10.
The Priority Method I.A. H. Lachlans - 1967 - Mathematical Logic Quarterly 13 (1‐2):1-10.

View all 7 references / Add more references