Hyperarithmetically Encodable Sets

We say that a set of integers, $A$, is hyperarithmetically (recursively) encodable, if every infinite set of integers $X$ contains an infinite subset $Y$ in which $A$ is hyperarithmetical (recursive). We show that the recursively encodable sets are precisely the hyperarithmetic sets. Let $\sigma$ be...

Full description

Saved in:
Bibliographic Details
Published in:Transactions of the American Mathematical Society 1978, Vol.239, p.99-122
Main Author: Solovay, Robert M.
Format: Article
Language:English
Subjects:
Arithmetic
Borel sets
Inductive definitions
Infinite sets
Integers
Mathematical functions
Mathematical logic
Mathematical set theory
Mathematical theorems
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We say that a set of integers, $A$, is hyperarithmetically (recursively) encodable, if every infinite set of integers $X$ contains an infinite subset $Y$ in which $A$ is hyperarithmetical (recursive). We show that the recursively encodable sets are precisely the hyperarithmetic sets. Let $\sigma$ be the closure ordinal of a universal $\Sigma^1_1$ inductive definition. Then $A$ is hyperarithmetically encodable $\operatorname{iff}$ it is constructible before stage $\sigma$. We also prove an effective version of the Galvin-Prikry results that open sets, and more generally Borel sets, are Ramsey, and in the case of open sets prove that our improvement is optimal.
ISSN:0002-9947
1088-6850
DOI:10.1090/S0002-9947-1978-0491103-7