Archive for Mathematical Logic 45 (7):869-912 (2006)

Abstract
We investigate strong versions of enumeration reducibility, the most important one being s-reducibility. We prove that every countable distributive lattice is embeddable into the local structure $L(\mathfrak D_s)$ of the s-degrees. However, $L(\mathfrak D_s)$ is not distributive. We show that on $\Delta^{0}_{2}$ sets s-reducibility coincides with its finite branch version; the same holds of e-reducibility. We prove some density results for $L(\mathfrak D_s)$ . In particular $L(\mathfrak D_s)$ is upwards dense. Among the results about reducibilities that are stronger than s-reducibility, we show that the structure of the $\Delta^{0}_{2}$ bs-degrees is dense. Many of these results on s-reducibility yield interesting corollaries for Q-reducibility as well
Keywords s-Reducibility   e-Reducibility
Categories (categorize this paper)
DOI 10.1007/s00153-006-0012-4
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 63,319
External links

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

Reducibility and Completeness for Sets of Integers.Richard M. Friedberg & Hartley Rogers - 1959 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 5 (7-13):117-125.
Reducibility and Completeness for Sets of Integers.Richard M. Friedberg & Hartley Rogers - 1959 - Mathematical Logic Quarterly 5 (7‐13):117-125.
Jumps of Quasi-Minimal Enumeration Degrees.Kevin McEvoy - 1985 - Journal of Symbolic Logic 50 (3):839-848.

View all 24 references / Add more references

Citations of this work BETA

Goodness in the Enumeration and Singleton Degrees.Charles M. Harris - 2010 - Archive for Mathematical Logic 49 (6):673-691.
Q 1-Degrees of C.E. Sets.R. Sh Omanadze & Irakli O. Chitaia - 2012 - Archive for Mathematical Logic 51 (5-6):503-515.
Bounded Enumeration Reducibility and its Degree Structure.Daniele Marsibilio & Andrea Sorbi - 2012 - Archive for Mathematical Logic 51 (1-2):163-186.
The Structure of the s -Degrees Contained Within a Single E -Degree.Thomas F. Kent - 2009 - Annals of Pure and Applied Logic 160 (1):13-21.

View all 9 citations / Add more citations

Similar books and articles

Bounded Enumeration Reducibility and its Degree Structure.Daniele Marsibilio & Andrea Sorbi - 2012 - Archive for Mathematical Logic 51 (1-2):163-186.
On Nondeterminism, Enumeration Reducibility and Polynomial Bounds.Kate Copestake - 1997 - Mathematical Logic Quarterly 43 (3):287-310.
On the Symmetric Enumeration Degrees.Charles M. Harris - 2007 - Notre Dame Journal of Formal Logic 48 (2):175-204.
A New Reducibility Between Turing‐ and Wtt‐Reducibility.Sui Yuefei - 1994 - Mathematical Logic Quarterly 40 (1):106-110.
On the (Semi)Lattices Induced by Continuous Reducibilities.Arno Pauly - 2010 - Mathematical Logic Quarterly 56 (5):488-502.
Intrinsic Reducibilities.Timothy H. McNicholl - 2000 - Mathematical Logic Quarterly 46 (3):393-407.
Bounds in the Turing Reducibility of Functions.Karol Habart & K. Habart - 1992 - Mathematical Logic Quarterly 38 (1):423-430.
Supervenience and Reducibility: An Odd Couple.Ausonio Marras - 1994 - Philosophical Quarterly 44 (171):215-222.
On Subcreative Sets and S-Reducibility.John T. Gill Iii & Paul H. Morris - 1974 - Journal of Symbolic Logic 39 (4):669 - 677.
Supervenience, Necessary Coextensions, and Reducibility.John Bacon - 1986 - Philosophical Studies 49 (March):163-76.
1-Reducibility Inside an M-Degree with Maximal Set.E. Herrmann - 1992 - Journal of Symbolic Logic 57 (3):1046-1056.

Analytics

Added to PP index
2013-11-23

Total views
10 ( #872,283 of 2,448,681 )

Recent downloads (6 months)
1 ( #447,034 of 2,448,681 )

How can I increase my downloads?

Downloads

My notes