Complexity of Index Sets of Descriptive Set-Theoretic Notions

Journal of Symbolic Logic 87 (3):894-911 (2022)
  Copy   BIBTEX

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.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,873

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Abstract complexity theory and the Δ20 degrees.Benjamin Schaeffer - 2002 - Annals of Pure and Applied Logic 115 (1-3):195-231.
Index sets and parametric reductions.Rod G. Downey & Michael R. Fellows - 2001 - Archive for Mathematical Logic 40 (5):329-348.
Index sets for Π01 classes.Douglas Cenzer & Jeffrey Remmel - 1998 - Annals of Pure and Applied Logic 93 (1-3):3-61.
Index sets in the arithmetical Hierarchy.Ulrike Brandt - 1988 - Annals of Pure and Applied Logic 37 (2):101-110.
Index sets for computable differential equations.Douglas Cenzer & Jeffrey B. Remmel - 2004 - Mathematical Logic Quarterly 50 (4-5):329-344.
On some sets of dictionaries whose ω ‐powers have a given.Olivier Finkel - 2010 - Mathematical Logic Quarterly 56 (5):452-460.
On one-sided versus two-sided classification.Stephan Frank - 2001 - Archive for Mathematical Logic 40 (7):489-513.
The graph-theoretic approach to descriptive set theory.Benjamin D. Miller - 2012 - Bulletin of Symbolic Logic 18 (4):554-575.
Immunity and Hyperimmunity for Sets of Minimal Indices.Frank Stephan & Jason Teutsch - 2008 - Notre Dame Journal of Formal Logic 49 (2):107-125.
Sets and Point-Sets: Five Grades of Set-Theoretic Involvement in Geometry.John P. Burgess - 1988 - PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association 1988:456 - 463.
Index sets for ω‐languages.Douglas Czenzer & Jeffrey B. Remmel - 2003 - Mathematical Logic Quarterly 49 (1):22-33.
Edge distribution and density in the characteristic sequence.M. E. Malliaris - 2010 - Annals of Pure and Applied Logic 162 (1):1-19.

Analytics

Added to PP
2022-04-08

Downloads
11 (#1,161,724)

6 months
8 (#411,508)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Infinite combinatorics and definability.Arnold W. Miller - 1989 - Annals of Pure and Applied Logic 41 (2):179-203.

Add more references