In this article we define and study the notion of a (c,c_1)-cylinder, which turns out to be very useful instrument for investigating the relationships between conjunctive reducibility (c-reducibility) and its injective version c_1-reducibility. Using this notion we prove the following results: (1) Neither hypersimple sets nor hemimaximal sets can be (c,c_1)-cylinders; (2) The c-degree of a noncomputable c.e. set contains either only one or infinitely many noncomputable c_1-degrees; (3) the c-degree of either a hemimaximal set or a hypersimple set contains infinitely many noncomputable c_1-degrees.
Chitaia, I., Omanadze, R., Sorbi, A. (2023). Conjunctive degrees and cylinders. JOURNAL OF LOGIC AND COMPUTATION [10.1093/logcom/exad064].
Conjunctive degrees and cylinders
Andrea Sorbi
2023-01-01
Abstract
In this article we define and study the notion of a (c,c_1)-cylinder, which turns out to be very useful instrument for investigating the relationships between conjunctive reducibility (c-reducibility) and its injective version c_1-reducibility. Using this notion we prove the following results: (1) Neither hypersimple sets nor hemimaximal sets can be (c,c_1)-cylinders; (2) The c-degree of a noncomputable c.e. set contains either only one or infinitely many noncomputable c_1-degrees; (3) the c-degree of either a hemimaximal set or a hypersimple set contains infinitely many noncomputable c_1-degrees.File | Dimensione | Formato | |
---|---|---|---|
conjunctive.pdf
non disponibili
Tipologia:
PDF editoriale
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
245.04 kB
Formato
Adobe PDF
|
245.04 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Conjunctive-file.pdf
Open Access dal 26/10/2024
Tipologia:
Post-print
Licenza:
PUBBLICO - Pubblico con Copyright
Dimensione
312.04 kB
Formato
Adobe PDF
|
312.04 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11365/1251874