< i> Σ_< sub> 5-completeness of index sets arising from the recursively enumerable Turing degrees

Annals of Pure and Applied Logic 79 (2):109-137 (1996)
  Copy   BIBTEX

Abstract

We employ techniques related to Lempp and Lerman's “iterated trees of strategies” to directly measure a Σ5-predicate and use this in showing the index set of the cuppable r.e. sets to be Σ5-complete. We also show how certain technical devices arise naturally out of the iterated-trees context, in particular, links arise as manifestations of a generalized notion of “stage”

Categories

Keywords

Reprint years

DOI

10.1016/0168-0072(95)00054-2

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,386

External links

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

Through your library

My notes

Similar books and articles

Σ5-completeness of index sets arising from the recursively enumerable Turing degrees.Michael A. Jahn - 1996 - Annals of Pure and Applied Logic 79 (2):109-137.
∑5-completeness of index sets arising from the lattice of recursively enumerable sets.Michael A. Jahn - 1996 - Annals of Pure and Applied Logic 80 (1):55-67.
Recursively enumerable generic sets.Wolfgang Maass - 1982 - Journal of Symbolic Logic 47 (4):809-823.
Complementation in the Turing degrees.Theodore A. Slaman & John R. Steel - 1989 - Journal of Symbolic Logic 54 (1):160-176.
On recursive enumerability with finite repetitions.Stephan Wehner - 1999 - Journal of Symbolic Logic 64 (3):927-945.
On relative enumerability of Turing degrees.Shamil Ishmukhametov - 2000 - Archive for Mathematical Logic 39 (3):145-154.
On the r.e. predecessors of d.r.e. degrees.Shamil Ishmukhametov - 1999 - Archive for Mathematical Logic 38 (6):373-386.
A limit on relative genericity in the recursively enumerable sets.Steffen Lempp & Theodore A. Slaman - 1989 - Journal of Symbolic Logic 54 (2):376-395.
On the orbits of hyperhypersimple sets.Wolfgang Maass - 1984 - Journal of Symbolic Logic 49 (1):51-62.
The role of true finiteness in the admissible recursively enumerable degrees.Noam Greenberg - 2005 - Bulletin of Symbolic Logic 11 (3):398-410.
The Isolated D. R. E. Degrees are Dense in the R. E. Degrees.Geoffrey Laforte - 1996 - Mathematical Logic Quarterly 42 (1):83-103.
Decidability of the two-quantifier theory of the recursively enumerable weak truth-table degrees and other distributive upper semi-lattices.Klaus Ambos-Spies, Peter A. Fejer, Steffen Lempp & Manuel Lerman - 1996 - Journal of Symbolic Logic 61 (3):880-905.
The Index Set of Injectively Enumerable Classes of Recursively Enumerable Sets in ∑5‐Complete.Stephan Wehner - 1994 - Mathematical Logic Quarterly 40 (1):87-94.
The Sacks density theorem and Σ2-bounding.Marcia J. Groszek, Michael E. Mytilinaios & Theodore A. Slaman - 1996 - Journal of Symbolic Logic 61 (2):450 - 467.

Analytics

Added to PP
2014-03-25

Downloads
12 (#1,058,801)

6 months
3 (#992,474)

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

Recursively enumerable sets modulo iterated jumps and extensions of Arslanov's completeness criterion.C. G. Jockusch, M. Lerman, R. I. Soare & R. M. Solovay - 1989 - Journal of Symbolic Logic 54 (4):1288-1323.
A non-inversion theorem for the jump operator.Richard A. Shore - 1988 - Annals of Pure and Applied Logic 40 (3):277-303.
Degrees which do not bound minimal degrees.Manuel Lerman - 1986 - Annals of Pure and Applied Logic 30 (3):249-276.
A limit on relative genericity in the recursively enumerable sets.Steffen Lempp & Theodore A. Slaman - 1989 - Journal of Symbolic Logic 54 (2):376-395.
∑5-completeness of index sets arising from the lattice of recursively enumerable sets.Michael A. Jahn - 1996 - Annals of Pure and Applied Logic 80 (1):55-67.

Add more references