Annals of Pure and Applied Logic 93 (1-3):3-61 (1998)

A Π01 class is an effectively closed set of reals. We study properties of these classes determined by cardinality, measure and category as well as by the complexity of the members of a class P. Given an effective enumeration {Pe:e < ω} of the Π01 classes, the index set I for a certain property is the set of indices e such that Pe has the property. For example, the index set of binary Π01 classes of positive measure is Σ02 complete. Various notions of boundedness are discussed and classified. For example, the index set of the recursively bounded classes is Σ03 complete and the index set of the recursively bounded classes which have infinitely many recursive members is Π04 complete. Consideration of the Cantor-Bendixson derivative leads to index sets in the transfinite levels of the hyperarithmetic hierarchy
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/s0168-0072(97)00052-3
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: 56,949
Through your library

References found in this work BETA

Extensions of Some Theorems of Gödel and Church.Barkley Rosser - 1936 - Journal of Symbolic Logic 1 (3):87-91.
Effective Coloration.Dwight R. Bean - 1976 - Journal of Symbolic Logic 41 (2):469-480.
Hiearchies of Boolean Algebras.Lawrence Feiner - 1970 - Journal of Symbolic Logic 35 (3):365-374.
Countable Thin Π01 Classes.Douglas Cenzer, Rodney Downey, Carl Jockusch & Richard A. Shore - 1993 - Annals of Pure and Applied Logic 59 (2):79-139.

View all 20 references / Add more references

Citations of this work BETA

Effectively Closed Sets and Enumerations.Paul Brodhead & Douglas Cenzer - 2008 - Archive for Mathematical Logic 46 (7-8):565-582.
PAC Learning, VC Dimension, and the Arithmetic Hierarchy.Wesley Calvert - 2015 - Archive for Mathematical Logic 54 (7-8):871-883.
The Complexity of Recursive Constraint Satisfaction Problems.Victor W. Marek & Jeffrey B. Remmel - 2010 - Annals of Pure and Applied Logic 161 (3):447-457.

Add more citations

Similar books and articles

Index Sets for< I> Π_< Sup> 0< Sub> 1 Classes.Douglas Cenzer & Jeffrey Remmel - 1998 - Annals of Pure and Applied Logic 93 (1):3-61.
Index Sets and Parametric Reductions.Rod G. Downey & Michael R. Fellows - 2001 - Archive for Mathematical Logic 40 (5):329-348.
Index Sets for Ω‐Languages.Douglas Czenzer & Jeffrey B. Remmel - 2003 - Mathematical Logic Quarterly 49 (1):22-33.
Index Sets of Finite Classes of Recursively Enumerable Sets.Louise Hay - 1969 - Journal of Symbolic Logic 34 (1):39-44.
Density of the Medvedev Lattice of Π0 1 Classes.Douglas Cenzer & Peter G. Hinman - 2003 - Archive for Mathematical Logic 42 (6):583-600.
Kleene Index Sets and Functional M-Degrees.Jeanleah Mohrherr - 1983 - Journal of Symbolic Logic 48 (3):829-840.
Classes of Recursive Functions and Their Index Sets.F. D. Lewis - 1971 - Mathematical Logic Quarterly 17 (1):291-294.
Index Sets for Some Classes of Structures.Ekaterina B. Fokina - 2009 - Annals of Pure and Applied Logic 157 (2-3):139-147.
Classifications of Generalized Index Sets of Open Classes.Nancy Johnson - 1978 - Journal of Symbolic Logic 43 (4):694-714.
Sets and Classes as Many.John L. Bell - 2000 - Journal of Philosophical Logic 29 (6):585-601.


Added to PP index

Total views
15 ( #648,007 of 2,409,938 )

Recent downloads (6 months)
1 ( #541,494 of 2,409,938 )

How can I increase my downloads?


My notes