Index sets and parametric reductions

Archive for Mathematical Logic 40 (5):329-348 (2001)
  Copy   BIBTEX


We investigate the index sets associated with the degree structures of computable sets under the parameterized reducibilities introduced by the authors. We solve a question of Peter Cholakand the first author by proving the fundamental index sets associated with a computable set A, {e : W e ≤ q u A} for q∈ {m, T} are Σ4 0 complete. We also show hat FPT(≤ q n ), that is {e : W e computable and ≡ q n ?}, is Σ4 0 complete. We also look at computable presentability of these classes



    Upload a copy of this work     Papers currently archived: 86,213

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

Kleene index sets and functional m-degrees.Jeanleah Mohrherr - 1983 - Journal of Symbolic Logic 48 (3):829-840.
Index sets for ω‐languages.Douglas Czenzer & Jeffrey B. Remmel - 2003 - Mathematical Logic Quarterly 49 (1):22-33.
Immunity and Hyperimmunity for Sets of Minimal Indices.Frank Stephan & Jason Teutsch - 2008 - Notre Dame Journal of Formal Logic 49 (2):107-125.
Lusin-sierpinski index for the internal sets.Boško Živaljević - 1992 - Journal of Symbolic Logic 57 (1):172 - 178.
Index sets of finite classes of recursively enumerable sets.Louise Hay - 1969 - Journal of Symbolic Logic 34 (1):39-44.


Added to PP

30 (#438,300)

6 months
2 (#518,672)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references