Index sets for Π01 classes

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

Abstract

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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 89,330

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

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.

Analytics

Added to PP
2014-01-16

Downloads
20 (#646,615)

6 months
2 (#637,499)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Density of the Medvedev lattice of Π0 1 classes.Douglas Cenzer & Peter G. Hinman - 2003 - Archive for Mathematical Logic 42 (6):583-600.
Ordinal analysis of partial combinatory algebras.Paul Shafer & Sebastiaan A. Terwijn - 2021 - Journal of Symbolic Logic 86 (3):1154-1188.
Index sets for computable differential equations.Douglas Cenzer & Jeffrey B. Remmel - 2004 - Mathematical Logic Quarterly 50 (4-5):329-344.
Effectively closed sets and enumerations.Paul Brodhead & Douglas Cenzer - 2008 - Archive for Mathematical Logic 46 (7-8):565-582.
Index sets for ω‐languages.Douglas Czenzer & Jeffrey B. Remmel - 2003 - Mathematical Logic Quarterly 49 (1):22-33.

View all 7 citations / Add more citations

References found in this work

Extensions of some theorems of gödel and church.Barkley Rosser - 1936 - Journal of Symbolic Logic 1 (3):87-91.
Hiearchies of Boolean algebras.Lawrence Feiner - 1970 - Journal of Symbolic Logic 35 (3):365-374.
Effective coloration.Dwight R. Bean - 1976 - Journal of Symbolic Logic 41 (2):469-480.

View all 20 references / Add more references