We show that for every intermediate $Sigma^0_2$ $s$-degree (i.e. a nonzero $s$-degree strictly below the $s$-degree of the complement of the halting set) there exists an incomparable $Pi^0_1$ $s$-degree. (The same proof yields a similar result for other positive reducibilities as well, including enumeration reducibility.) As a consequence, for every intermediate $Pi^0_2$ $Q$-degree (i.e. a nonzero $Q$-degree strictly below the $Q$-degree of the halting set) there exists an incomparable $Sigma^0_1$ $Q$-degree. We also show how these results can be applied to provide proofs or new proofs (essentially already known, although some of them not explicitly noted in the literature) of upper density results in local structures of $s$-degrees and $Q$-degrees.

Chitaia, I., Ng Keng, M., Sorbi, A., Yang, Y. (2020). Incomparability in local structures of $s$-degrees and $Q$-degrees. ARCHIVE FOR MATHEMATICAL LOGIC, 59(7-8), 777-791 [10.1007/s00153-020-00714-x].

Incomparability in local structures of $s$-degrees and $Q$-degrees

Sorbi Andrea
;
2020-01-01

Abstract

We show that for every intermediate $Sigma^0_2$ $s$-degree (i.e. a nonzero $s$-degree strictly below the $s$-degree of the complement of the halting set) there exists an incomparable $Pi^0_1$ $s$-degree. (The same proof yields a similar result for other positive reducibilities as well, including enumeration reducibility.) As a consequence, for every intermediate $Pi^0_2$ $Q$-degree (i.e. a nonzero $Q$-degree strictly below the $Q$-degree of the halting set) there exists an incomparable $Sigma^0_1$ $Q$-degree. We also show how these results can be applied to provide proofs or new proofs (essentially already known, although some of them not explicitly noted in the literature) of upper density results in local structures of $s$-degrees and $Q$-degrees.
2020
Chitaia, I., Ng Keng, M., Sorbi, A., Yang, Y. (2020). Incomparability in local structures of $s$-degrees and $Q$-degrees. ARCHIVE FOR MATHEMATICAL LOGIC, 59(7-8), 777-791 [10.1007/s00153-020-00714-x].
File in questo prodotto:
File Dimensione Formato  
Chitaia2020_Article_IncomparabilityInLocalStructur.pdf

non disponibili

Tipologia: PDF editoriale
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 322.9 kB
Formato Adobe PDF
322.9 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/1110356