Splitting into degrees with low computational strength
We investigate the extent to which a c.e. degree can be split into two smaller c.e. degrees which are computationally weak. In contrast to a result of Bickford and Mills that 0′ can be split into two superlow c.e. degrees, we construct a SJT-hard c.e. degree which is not the join of two superlow c.e...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2020
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/142074 |
| _version_ | 1824455277729021952 |
|---|---|
| author | Downey, Rod Ng, Keng Meng |
| author2 | School of Physical and Mathematical Sciences |
| author_facet | School of Physical and Mathematical Sciences Downey, Rod Ng, Keng Meng |
| author_sort | Downey, Rod |
| collection | NTU |
| description | We investigate the extent to which a c.e. degree can be split into two smaller c.e. degrees which are computationally weak. In contrast to a result of Bickford and Mills that 0′ can be split into two superlow c.e. degrees, we construct a SJT-hard c.e. degree which is not the join of two superlow c.e. degrees. We also prove that every high c.e. degree is the join of two array computable c.e. degrees, and that not every high2 c.e. degree can be split in this way. Finally we extend a result of Downey, Jockusch and Stob by showing that no totally ω-c.a. wtt-degree can be cupped to the complete wtt-degree. |
| first_indexed | 2025-02-19T03:35:39Z |
| format | Journal Article |
| id | ntu-10356/142074 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2025-02-19T03:35:39Z |
| publishDate | 2020 |
| record_format | dspace |
| spelling | ntu-10356/1420742020-06-15T08:02:02Z Splitting into degrees with low computational strength Downey, Rod Ng, Keng Meng School of Physical and Mathematical Sciences Science::Mathematics Degree Splitting Lowness We investigate the extent to which a c.e. degree can be split into two smaller c.e. degrees which are computationally weak. In contrast to a result of Bickford and Mills that 0′ can be split into two superlow c.e. degrees, we construct a SJT-hard c.e. degree which is not the join of two superlow c.e. degrees. We also prove that every high c.e. degree is the join of two array computable c.e. degrees, and that not every high2 c.e. degree can be split in this way. Finally we extend a result of Downey, Jockusch and Stob by showing that no totally ω-c.a. wtt-degree can be cupped to the complete wtt-degree. MOE (Min. of Education, S’pore) 2020-06-15T08:02:02Z 2020-06-15T08:02:02Z 2018 Journal Article Downey, R. & Ng, K. M. (2018). Splitting into degrees with low computational strength. Annals of Pure and Applied Logic, 169(8), 803-834. doi:10.1016/j.apal.2018.04.004 0168-0072 https://hdl.handle.net/10356/142074 10.1016/j.apal.2018.04.004 2-s2.0-85045697374 8 169 803 834 en Annals of Pure and Applied Logic © 2018 Elsevier B.V. All rights reserved. |
| spellingShingle | Science::Mathematics Degree Splitting Lowness Downey, Rod Ng, Keng Meng Splitting into degrees with low computational strength |
| title | Splitting into degrees with low computational strength |
| title_full | Splitting into degrees with low computational strength |
| title_fullStr | Splitting into degrees with low computational strength |
| title_full_unstemmed | Splitting into degrees with low computational strength |
| title_short | Splitting into degrees with low computational strength |
| title_sort | splitting into degrees with low computational strength |
| topic | Science::Mathematics Degree Splitting Lowness |
| url | https://hdl.handle.net/10356/142074 |
| work_keys_str_mv | AT downeyrod splittingintodegreeswithlowcomputationalstrength AT ngkengmeng splittingintodegreeswithlowcomputationalstrength |