The class of recursively enumerable subsets of a recursively enumerable set

Louise Hay

Vol. 46 (1973), No. 1, 167–183

DOI: 10.2140/pjm.1973.46.167

Abstract

For any set α, let 𝜃A^α denote the index set of the class of all recursively enumerable (r.e.) subsets of α (i.e., if {W_x}_x≧0 is a standard enumeration of all r.e. sets, 𝜃A^α = {x|W_x ⊂ α}.) The purpose of this paper is to examine the possible Turing degrees of the sets 𝜃A^α when α is r.e. It is proved that if b is any nonrecursive r.e. degree, the Turing degrees of sets 𝜃A^α for α r.e., α ∈ b, are exactly the degrees c > 0′ such that c is r.e. in b.

Mathematical Subject Classification

Primary: 02F25

Milestones

Received: 2 January 1972

Published: 1 May 1973