On Subcreative Sets and S-Reducibility
Journal of Symbolic Logic 39 (4):669 - 677 (1974)
| Abstract | Subcreative sets, introduced by Blum, are known to coincide with the effectively speedable sets. Subcreative sets are shown to be the complete sets with respect to S-reducibility, a special case of Turing reducibility. Thus a set is effectively speedable exactly when it contains the solution to the halting problem in an easily decodable form. Several characterizations of subcreative sets are given, including the solution of an open problem of Blum, and are used to locate the subcreative sets with respect to the complete sets of other reducibilities. It is shown that q-cylindrification is an order-preserving map from the r.e. T-degrees to the r.e. S-degrees. Consequently, T-complete sets are precisely the r.e. sets whose q-cylindrifications are S-complete. | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | No categories specified (fix it) | |||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,672 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesI. I. I. Gill & Paul H. Morris (1974). On Subcreative Sets and s-Reducibility. Journal of Symbolic Logic 39 (4):669-677.
Douglas Cenzer (1984). Monotone Reducibility and the Family of Infinite Sets. Journal of Symbolic Logic 49 (3):774-782.
Michael Stob (1983). Wtt-Degrees and T-Degrees of R.E. Sets. Journal of Symbolic Logic 48 (4):921-930.
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.
Jeanleah Mohrherr (1983). Kleene Index Sets and Functional M-Degrees. Journal of Symbolic Logic 48 (3):829-840.
Roland SH Omanadze (2004). Splittings of Effectively Speedable Sets and Effectively Levelable Sets. Journal of Symbolic Logic 69 (1):143-158.
Leo Harrington & Robert I. Soare (1996). Definability, Automorphisms, and Dynamic Properties of Computably Enumerable Sets. Bulletin of Symbolic Logic 2 (2):199-213.
Wolfgang Maass (1982). Recursively Enumerable Generic Sets. Journal of Symbolic Logic 47 (4):809-823.
André Nies, Frank Stephan & Sebastiaan A. Terwijn (2005). Randomness, Relativization and Turing Degrees. Journal of Symbolic Logic 70 (2):515 - 535.
E. Herrmann (1983). Orbits of Hyperhypersimple Sets and the Lattice of ∑03 Sets. Journal of Symbolic Logic 48 (3):693 - 699.
Siegfried Gottwald (2006). Universes of Fuzzy Sets and Axiomatizations of Fuzzy Set Theory. Part I: Model-Based and Axiomatic Approaches. Studia Logica 82 (2):211 - 244.
E. Hermann (1992). 1-Reducibility Inside an M-Degree with Maximal Set. Journal of Symbolic Logic 57 (3):1046-1056.
A. M. Dawes (1982). Splitting Theorems for Speed-Up Related to Order of Enumeration. Journal of Symbolic Logic 47 (1):1-7.
Theodore A. Slaman (1986). On the Kleene Degrees of Π11 Sets. Journal of Symbolic Logic 51 (2):352 - 359.
Analytics
Monthly downloads
Sorry, there are not enough data points to plot this chart.
|
Added to index2011-05-29Total downloads1 ( #274,652 of 549,066 )Recent downloads (6 months)0How can I increase my downloads? |
My notes
Discussion
