Pa Relative to an Enumeration Oracle

Journal of Symbolic Logic 88 (4):1497-1525 (2023)
  Copy   BIBTEX

Abstract

Recall that B is PA relative to A if B computes a member of every nonempty $\Pi ^0_1(A)$ class. This two-place relation is invariant under Turing equivalence and so can be thought of as a binary relation on Turing degrees. Miller and Soskova [23] introduced the notion of a $\Pi ^0_1$ class relative to an enumeration oracle A, which they called a $\Pi ^0_1{\left \langle {A}\right \rangle }$ class. We study the induced extension of the relation B is PA relative to A to enumeration oracles and hence enumeration degrees. We isolate several classes of enumeration degrees based on their behavior with respect to this relation: the PA bounded degrees, the degrees that have a universal class, the low for PA degrees, and the ${\left \langle {\text {self}\kern1pt}\right \rangle }$ -PA degrees. We study the relationship between these classes and other known classes of enumeration degrees. We also investigate a group of classes of enumeration degrees that were introduced by Kalimullin and Puzarenko [14] based on properties that are commonly studied in descriptive set theory. As part of this investigation, we give characterizations of three of their classes in terms of a special sub-collection of relativized $\Pi ^0_1$ classes—the separating classes. These three can then be seen to be direct analogues of three of our classes. We completely determine the relative position of all classes in question.

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 98,316

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

On the Symmetric Enumeration Degrees.Charles M. Harris - 2007 - Notre Dame Journal of Formal Logic 48 (2):175-204.
Goodness in the enumeration and singleton degrees.Charles M. Harris - 2010 - Archive for Mathematical Logic 49 (6):673-691.
On Nondeterminism, Enumeration Reducibility and Polynomial Bounds.Kate Copestake - 1997 - Mathematical Logic Quarterly 43 (3):287-310.
Introenumerability, Autoreducibility, and Randomness.L. I. Ang - forthcoming - Journal of Symbolic Logic.
On the jump classes of noncuppable enumeration degrees.Charles M. Harris - 2011 - Journal of Symbolic Logic 76 (1):177 - 197.
The jump operator on the ω-enumeration degrees.Hristo Ganchev & Ivan N. Soskov - 2009 - Annals of Pure and Applied Logic 160 (3):289-301.

Analytics

Added to PP
2022-07-18

Downloads
35 (#520,475)

6 months
6 (#740,620)

Historical graph of downloads
How can I increase my downloads?

Author Profiles

Citations of this work

No citations found.

Add more citations

References found in this work

Reducibility and Completeness for Sets of Integers.Richard M. Friedberg & Hartley Rogers - 1959 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 5 (7-13):117-125.
Reducibility and Completeness for Sets of Integers.Richard M. Friedberg & Hartley Rogers - 1959 - Mathematical Logic Quarterly 5 (7‐13):117-125.
Creative sets.John Myhill - 1955 - Mathematical Logic Quarterly 1 (2):97-108.
Creative sets.John Myhill - 1955 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 1 (2):97-108.

View all 15 references / Add more references