Hyperarithmetically Encodable Sets

DOI10.2307/1997849zbMath0411.03039OpenAlexW4251824600MaRDI QIDQ4198744

Robert M. Solovay

Publication date: 1978

Full work available at URL: https://doi.org/10.2307/1997849

zbMATH Keywords

Turing reducibilitydescriptive set theoryintroreducibilityretraceable setrecursively encodablerelative hyperarithmeticity

Mathematics Subject Classification ID

Descriptive set theory (03E15) Other degrees and reducibilities in computability and recursion theory (03D30) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Related Items

On needed reals ⋮ RAMSEY-LIKE THEOREMS AND MODULI OF COMPUTATION ⋮ Dominating the Erdős-Moser theorem in reverse mathematics ⋮ The Galvin-Prikry theorem and set existence axioms ⋮ Ramsey’s theorem for singletons and strong computable reducibility ⋮ Tall 𝐹_{𝜎} subideals of tall analytic ideals ⋮ Fraïssé’s conjecture in Π11-comprehension ⋮ The coding power of a product of partitions ⋮ Effective properties in compact sets of Borel functions ⋮ Some Questions in Computable Mathematics ⋮ BASES AND BOREL SELECTORS FOR TALL FAMILIES ⋮ A complexity problem for Borel graphs ⋮ Genericity for Mathias forcing over general Turing ideals ⋮ Computing sets from all infinite subsets ⋮ Needed reals and recursion in generic reals ⋮ Canonical forms of shift-invariant maps on \([\mathbb N^{\infty}\)] ⋮ Borel extractions of converging sequences in compact sets of Borel functions ⋮ Thin set theorems and cone avoidance ⋮ \({\Pi^1_2}\)-comprehension and the property of Ramsey ⋮ THE OPEN AND CLOPEN RAMSEY THEOREMS IN THE WEIHRAUCH LATTICE ⋮ A dual form of Ramsey's theorem ⋮ A reducibility related to being hyperimmune-free ⋮ Lawvere-Tierney topologies for computability theorists

Cites Work

• Unnamed Item
• A model of set-theory in which every set of reals is Lebesgue measurable
• Representability in some systems of second order arithmetic
• The Theory of Countable Analytical Sets
• Borel sets and Ramsey's theorem
• Encodability of Kleene's O
• Uniformly introreducible sets
• Sets with no subset of higher degree
• The fine structure of the constructible hierarchy
• The α-finite injury method