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...
Saved in:
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
2023
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/171806 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Nanyang Technological University |
| Language: | English |
| id |
sg-ntu-dr.10356-171806 |
|---|---|
| record_format |
dspace |
| spelling |
sg-ntu-dr.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. |
| institution |
Nanyang Technological University |
| building |
NTU Library |
| continent |
Asia |
| country |
Singapore Singapore |
| content_provider |
NTU Library |
| collection |
DR-NTU |
| language |
English |
| topic |
Science::Mathematics Effectively Closed Sets Computably Enumerable Degrees |
| 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 |
| 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. |
| author2 |
School of Physical and Mathematical Sciences |
| author_facet |
School of Physical and Mathematical Sciences Csima, Barbara F. Downey, Rod Ng, Keng Meng |
| format |
Article |
| author |
Csima, Barbara F. Downey, Rod Ng, Keng Meng |
| author_sort |
Csima, Barbara F. |
| title |
On the C.E. degrees realizable in II⁰₁ classes |
| title_short |
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_sort |
on the c.e. degrees realizable in ii⁰₁ classes |
| publishDate |
2023 |
| url |
https://hdl.handle.net/10356/171806 |
| _version_ |
1783955639914987520 |