Annals of Pure and Applied Logic 116 (1-3):273-295 (2002)

Abstract
We study connections between strong reducibilities and properties of computably enumerable sets such as simplicity. We say that a class of computably enumerable sets bounded iff there is an m-incomplete computably enumerable set A such that every set in is m-reducible to A. For example, we show that the class of effectively simple sets is bounded; but the class of maximal sets is not. Furthermore, the class of computably enumerable sets Turing reducible to a computably enumerable set B is bounded iff B is low2. For r = bwtt,tt,wtt and T, there is a bounded class intersecting every computably enumerable r-degree; for r = c, d and p, no such class exists
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/s0168-0072(01)00114-2
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: 71,489
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.
Creative Sets.John Myhill - 1955 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 1 (2):97-108.
Reducibility and Completeness for Sets of Integers.Richard M. Friedberg & Hartley Rogers - 1959 - Mathematical Logic Quarterly 5 (7‐13):117-125.
Creative Sets.John Myhill - 1955 - Mathematical Logic Quarterly 1 (2):97-108.

View all 9 references / Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

An Incomplete Set of Shortest Descriptions.Frank Stephan & Jason Teutsch - 2012 - Journal of Symbolic Logic 77 (1):291-307.
On Σ1 1 Equivalence Relations with Borel Classes of Bounded Rank.Ramez L. Sami - 1984 - Journal of Symbolic Logic 49 (4):1273 - 1283.
On Recursive Enumerability with Finite Repetitions.Stephan Wehner - 1999 - Journal of Symbolic Logic 64 (3):927-945.
Approximate Counting in Bounded Arithmetic.Emil Jeřábek - 2007 - Journal of Symbolic Logic 72 (3):959 - 993.
Sets and Classes as Many.John L. Bell - 2000 - Journal of Philosophical Logic 29 (6):585-601.
Bounded Scott Set Saturation.Alex M. McAllister - 2002 - Mathematical Logic Quarterly 48 (2):245-259.
Plural Quantification and Classes.Gabriel Uzquiano - 2003 - Philosophia Mathematica 11 (1):67-81.
Returning to Semi-Bounded Sets.Ya'acov Peterzil - 2009 - Journal of Symbolic Logic 74 (2):597-617.

Analytics

Added to PP index
2014-01-16

Total views
5 ( #1,208,349 of 2,520,891 )

Recent downloads (6 months)
1 ( #405,457 of 2,520,891 )

How can I increase my downloads?

Downloads

My notes