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.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.
https://hdl.handle.net/11365/1110356