التفاصيل البيبلوغرافية
العنوان: |
Minimal degrees and downwards density in some strong positive reducibilities and quasi-reducibilities. |
المؤلفون: |
Chitaia, Irakli, Ng, Keng Meng, Sorbi, Andrea, Yang, Yue |
المصدر: |
Journal of Logic & Computation; Jul2023, Vol. 33 Issue 5, p1060-1088, 29p |
مصطلحات موضوعية: |
ISOMORPHISM (Mathematics) |
مستخلص: |
We consider three strong reducibilities, |$s_{1}, s_{2}, Q_{1}$| (where we identify a reducibility |$\leqslant _r$| with its index |$r$|). The first two reducibilities can be viewed as injective versions of |$s$| -reducibility, whereas |$Q_1$| -reducibility can be viewed as an injective version of |$Q$| -reducibility. We have, with proper inclusions, |$s_{1} \subset s_{2} \subset s$|. It is well known that there is no minimal |$s$| -degree, and there is no minimal |$Q$| -degree. We show on the contrary that there exist minimal |$\varDelta ^{0}_{2}$| |$s_{2}$| -degrees and minimal |$\varDelta ^{0}_{2}$| |$s_{1}$| -degrees. On the other hand, both the |$\varPi ^{0}_{1}$| |$s_{2}$| -degrees and the |$\varPi ^{0}_{1}$| |$s_{1}$| -degrees are downwards dense. By the isomorphism of the |$s_1$| -degrees with the |$Q_1$| -degrees induced by complementation of sets, it follows that there exist minimal |$\varDelta ^0_2$| |$Q_1$| -degrees, but the c.e. |$Q_{1}$| -degrees are downwards dense. [ABSTRACT FROM AUTHOR] |
|
Copyright of Journal of Logic & Computation is the property of Oxford University Press / USA and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
قاعدة البيانات: |
Complementary Index |