On the C.E. degrees realizable in II⁰₁ classes
We study for each computably bounded Π01 class P the set of degrees of c.e. paths in P. We show, amongst other results, that for every c.e. degree a there is a perfect Π01 class where all c.e. members have degree a. We also show that every Σ03 set of c.e. indices is realized in some perfect Π01 clas...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/171806 |
| _version_ | 1824455882162831360 |
|---|---|
| author | Csima, Barbara F. Downey, Rod Ng, Keng Meng |
| author2 | School of Physical and Mathematical Sciences |
| author_facet | School of Physical and Mathematical Sciences Csima, Barbara F. Downey, Rod Ng, Keng Meng |
| author_sort | Csima, Barbara F. |
| collection | NTU |
| description | We study for each computably bounded Π01 class P the set of degrees of c.e. paths in P. We show, amongst other results, that for every c.e. degree a there is a perfect Π01 class where all c.e. members have degree a. We also show that every Σ03 set of c.e. indices is realized in some perfect Π01 class, and classify the sets of c.e. degrees which can be realized in some Π01 class as exactly those with a computable representation. |
| first_indexed | 2025-02-19T03:45:16Z |
| format | Journal Article |
| id | ntu-10356/171806 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2025-02-19T03:45:16Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | ntu-10356/1718062023-11-08T04:50:18Z On the C.E. degrees realizable in II⁰₁ classes Csima, Barbara F. Downey, Rod Ng, Keng Meng School of Physical and Mathematical Sciences Science::Mathematics Effectively Closed Sets Computably Enumerable Degrees We study for each computably bounded Π01 class P the set of degrees of c.e. paths in P. We show, amongst other results, that for every c.e. degree a there is a perfect Π01 class where all c.e. members have degree a. We also show that every Σ03 set of c.e. indices is realized in some perfect Π01 class, and classify the sets of c.e. degrees which can be realized in some Π01 class as exactly those with a computable representation. Ministry of Education (MOE) Csima is partially supported by an NSERC Discovery Grant. Downey is partially supported by Marsden Fund of New Zealand. Ng is partially supported by the grants MOE2015-T2-2-055 and RG131/17. 2023-11-08T04:50:17Z 2023-11-08T04:50:17Z 2023 Journal Article Csima, B. F., Downey, R. & Ng, K. M. (2023). On the C.E. degrees realizable in II⁰₁ classes. Journal of Symbolic Logic, 1-26. https://dx.doi.org/10.1017/jsl.2023.26 0022-4812 https://hdl.handle.net/10356/171806 10.1017/jsl.2023.26 2-s2.0-85156239675 1 26 en MOE2015-T2-2-055 RG131/17 Journal of Symbolic Logic © The Author(s) 2023. Published by Cambridge University Press on behalf of The Association for Symbolic Logic. All rights reserved. |
| spellingShingle | Science::Mathematics Effectively Closed Sets Computably Enumerable Degrees Csima, Barbara F. Downey, Rod Ng, Keng Meng On the C.E. degrees realizable in II⁰₁ classes |
| title | On the C.E. degrees realizable in II⁰₁ classes |
| title_full | On the C.E. degrees realizable in II⁰₁ classes |
| title_fullStr | On the C.E. degrees realizable in II⁰₁ classes |
| title_full_unstemmed | On the C.E. degrees realizable in II⁰₁ classes |
| title_short | On the C.E. degrees realizable in II⁰₁ classes |
| title_sort | on the c e degrees realizable in ii⁰₁ classes |
| topic | Science::Mathematics Effectively Closed Sets Computably Enumerable Degrees |
| url | https://hdl.handle.net/10356/171806 |
| work_keys_str_mv | AT csimabarbaraf onthecedegreesrealizableinii01classes AT downeyrod onthecedegreesrealizableinii01classes AT ngkengmeng onthecedegreesrealizableinii01classes |