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.
2023
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].
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11365/1218654