We consider three strong reducibilities, s_1, s_2, Q_1. 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 that s_1 is properly included in s_2, and s_2 is properly included in 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 Δ^0_2 s_2-degrees and minimal Δ^0_2 s_1-degrees. On the other hand, both the Π^0_1 s_2-degrees and the Π^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 Δ^0_2 Q_1-degrees, but the c.e. Q_1-degrees are downwards dense.
Chitaia, I., Meng Ng, K., Sorbi, A., Yang, Y. (2023). Minimal degrees and downwards density in some strong positive reducibilities and quasi-reducibilities. JOURNAL OF LOGIC AND COMPUTATION, 33(5), 1060-1088 [10.1093/logcom/exac044].
Minimal degrees and downwards density in some strong positive reducibilities and quasi-reducibilities
Andrea Sorbi
;
2023-01-01
Abstract
We consider three strong reducibilities, s_1, s_2, Q_1. 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 that s_1 is properly included in s_2, and s_2 is properly included in 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 Δ^0_2 s_2-degrees and minimal Δ^0_2 s_1-degrees. On the other hand, both the Π^0_1 s_2-degrees and the Π^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 Δ^0_2 Q_1-degrees, but the c.e. Q_1-degrees are downwards dense.File | Dimensione | Formato | |
---|---|---|---|
exac044.pdf
non disponibili
Tipologia:
PDF editoriale
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
427.51 kB
Formato
Adobe PDF
|
427.51 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11365/1218654