Index sets for Π01 classes

https://doi.org/10.1016/S0168-0072(97)00052-3Get rights and content
Under an Elsevier user license
open archive

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 (such as having positive measure) 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 (including a new notion of “almost bounded” classes) 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.

MSC

03D80
03D25
03D55

Keywords

Index sets
Π01 classes

Cited by (0)

Expanded version of talk presented at AMS Special Session on Recursive and Feasible Mathematics (Orlando, January 1996).