Back to Search
Start Over
COMPLEXITY OF INDEX SETS OF DESCRIPTIVE SET-THEORETIC NOTIONS.
- Source :
- Journal of Symbolic Logic; Sep2022, Vol. 87 Issue 3, p894-911, 18p
- Publication Year :
- 2022
-
Abstract
- Descriptive set theory and computability theory are closely-related fields of logic; both are oriented around a notion of descriptive complexity. However, the two fields typically consider objects of very different sizes; computability theory is principally concerned with subsets of the naturals, while descriptive set theory is interested primarily in subsets of the reals. In this paper, we apply a generalization of computability theory, admissible recursion theory, to consider the relative complexity of notions that are of interest in descriptive set theory. In particular, we examine the perfect set property, determinacy, the Baire property, and Lebesgue measurability. We demonstrate that there is a separation of descriptive complexity between the perfect set property and determinacy for analytic sets of reals; we also show that the Baire property and Lebesgue measurability are both equivalent in complexity to the property of simply being a Borel set, for $\boldsymbol {\Sigma ^{1}_{2}}$ sets of reals. [ABSTRACT FROM AUTHOR]
- Subjects :
- RECURSION theory
SET theory
BOREL sets
LEBESGUE measure
LOGIC
COMPUTABLE functions
Subjects
Details
- Language :
- English
- ISSN :
- 00224812
- Volume :
- 87
- Issue :
- 3
- Database :
- Supplemental Index
- Journal :
- Journal of Symbolic Logic
- Publication Type :
- Academic Journal
- Accession number :
- 159744586
- Full Text :
- https://doi.org/10.1017/jsl.2022.2