{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,2,13]],"date-time":"2024-02-13T06:10:23Z","timestamp":1707804623023},"reference-count":29,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2022,7,18]],"date-time":"2022-07-18T00:00:00Z","timestamp":1658102400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2023,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Recall that <jats:italic>B<\/jats:italic> is <jats:italic>PA relative to A<\/jats:italic> if <jats:italic>B<\/jats:italic> computes a member of every nonempty <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"https:\/\/2.zoppoz.workers.dev:443\/http\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S002248122200055X_inline1.png\" \/><jats:tex-math>\n$\\Pi ^0_1(A)$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> 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 <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"https:\/\/2.zoppoz.workers.dev:443\/http\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S002248122200055X_inline2.png\" \/><jats:tex-math>\n$\\Pi ^0_1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> class relative to an enumeration oracle <jats:italic>A<\/jats:italic>, which they called a <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"https:\/\/2.zoppoz.workers.dev:443\/http\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S002248122200055X_inline3.png\" \/><jats:tex-math>\n$\\Pi ^0_1{\\left \\langle {A}\\right \\rangle }$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> class. We study the induced extension of the relation <jats:italic>B<\/jats:italic> is PA relative to <jats:italic>A<\/jats:italic> 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 <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"https:\/\/2.zoppoz.workers.dev:443\/http\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S002248122200055X_inline4.png\" \/><jats:tex-math>\n${\\left \\langle {\\text {self}\\kern1pt}\\right \\rangle }$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-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 <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"https:\/\/2.zoppoz.workers.dev:443\/http\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S002248122200055X_inline5.png\" \/><jats:tex-math>\n$\\Pi ^0_1$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> classes\u2014the 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.<\/jats:p>","DOI":"10.1017\/jsl.2022.55","type":"journal-article","created":{"date-parts":[[2022,7,18]],"date-time":"2022-07-18T01:34:05Z","timestamp":1658108045000},"page":"1497-1525","update-policy":"https:\/\/2.zoppoz.workers.dev:443\/http\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["PA RELATIVE TO AN ENUMERATION ORACLE"],"prefix":"10.1017","volume":"88","author":[{"given":"JUN LE","family":"GOH","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ISKANDER SH.","family":"KALIMULLIN","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JOSEPH S.","family":"MILLER","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MARIYA I.","family":"SOSKOVA","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2022,7,18]]},"reference":[{"key":"S002248122200055X_r2","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-019-1943-x"},{"key":"S002248122200055X_r17","doi-asserted-by":"publisher","DOI":"10.1093\/bjps\/IV.14.107"},{"key":"S002248122200055X_r24","unstructured":"[24] Miller, J. S. and Soskova, M. I. , Randomness relative to an enumeration oracle, unpublished."},{"key":"S002248122200055X_r11","doi-asserted-by":"crossref","unstructured":"[11] Ganchev, H. A. , Kalimullin, I. S. , Miller, J. S. , and Soskova, M. I. , A structural dichotomy in the enumeration degrees, this Journal, vol. 87 (2022), pp. 527\u2013544.","DOI":"10.1017\/jsl.2019.72"},{"key":"S002248122200055X_r21","first-page":"501","article-title":"Degrees of difficulty of the mass problem","volume":"104","author":"Medvedev","year":"1955","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"S002248122200055X_r12","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2017.8005086"},{"key":"S002248122200055X_r23","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2018.01.001"},{"key":"S002248122200055X_r7","doi-asserted-by":"crossref","unstructured":"[7] Cooper, S. B. , Partial degrees and the density problem. II. The enumeration degrees of the ${\\varSigma}_2$ sets are dense, this Journal, vol. 49 (1984), no. 2, pp. 503\u2013513.","DOI":"10.2307\/2274181"},{"key":"S002248122200055X_r3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29952-0_56"},{"key":"S002248122200055X_r10","doi-asserted-by":"crossref","unstructured":"[10] Friedberg, R. M. and Rogers, H. , Jr., Reducibility and completeness for sets of integers. Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik, vol. 5 (1959), pp. 117\u2013125.","DOI":"10.1002\/malq.19590050703"},{"key":"S002248122200055X_r15","first-page":"35","article-title":"Computability principles on admissible sets","volume":"7","author":"Kalimullin","year":"2004","journal-title":"Matematicheskie Trudy"},{"key":"S002248122200055X_r6","doi-asserted-by":"publisher","DOI":"10.1090\/jams\/848"},{"key":"S002248122200055X_r16","unstructured":"[16] Kihara, T. , Ng, K. M. , and Pauly, A. , Enumeration degrees and non-metrizable topology, preprint, 2020, arXiv:1904.04107."},{"key":"S002248122200055X_r18","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0076224"},{"key":"S002248122200055X_r26","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2015-06184-4"},{"key":"S002248122200055X_r22","doi-asserted-by":"crossref","unstructured":"[22] Miller, J. S. , Degrees of unsolvability of continuous functions, this Journal, vol. 69 (2004), no. 2, pp. 555\u2013584.","DOI":"10.2178\/jsl\/1082418543"},{"key":"S002248122200055X_r5","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exm033"},{"key":"S002248122200055X_r29","first-page":"775","article-title":"On computable operations","volume":"103","author":"Uspensky","year":"1955","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"S002248122200055X_r14","doi-asserted-by":"publisher","DOI":"10.1142\/S0219061303000285"},{"key":"S002248122200055X_r13","first-page":"33","article-title":"${\\varPi}_1^0$\n\n\n classes and degrees of theories","volume":"173","author":"Jockusch","year":"1972","journal-title":"Transactions of the American Mathematical Society"},{"key":"S002248122200055X_r27","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19710170139"},{"key":"S002248122200055X_r20","doi-asserted-by":"publisher","DOI":"10.1090\/proc\/13783"},{"key":"S002248122200055X_r28","first-page":"56","article-title":"Total and co-total enumeration degrees","volume":"49","author":"Solon","year":"2005","journal-title":"Russian Mathematics"},{"key":"S002248122200055X_r8","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2011.06.010"},{"key":"S002248122200055X_r9","doi-asserted-by":"publisher","DOI":"10.1142\/S0219061305000468"},{"key":"S002248122200055X_r19","unstructured":"[19] Lagemann, J. , Embedding theorems in the reducibility ordering of the partial degrees . Ph.D. thesis, Massachusetts Institute of Technology, 1971."},{"key":"S002248122200055X_r1","doi-asserted-by":"publisher","DOI":"10.1090\/tran\/7604"},{"key":"S002248122200055X_r4","doi-asserted-by":"publisher","DOI":"10.1215\/00294527-2018-0008"},{"key":"S002248122200055X_r25","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19550010205"}],"container-title":["The Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S002248122200055X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,13]],"date-time":"2024-02-13T05:32:20Z","timestamp":1707802340000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/www.cambridge.org\/core\/product\/identifier\/S002248122200055X\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,18]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["S002248122200055X"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1017\/jsl.2022.55","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7,18]]},"assertion":[{"value":"\u00a9 The Author(s), 2022. Published by Cambridge University Press on behalf of The Association for Symbolic Logic","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}