We investigate strong versions of enumeration reducibility, the most important one being s-reducibility. We prove that every countable distributive lattice is embeddable into the local structure L(D_s) of the s-degrees. However, L(D_s) is not distributive. We show that on \Delta^0_2 sets s-reducibility coincides with its finite branch version; the same holds of e-reducibility. We prove some density results for L(D_s). In particular L(D_s) is upwards dense. Among the results about reducibilities that are stronger than s-reducibility, we show that the structure of the \Delta^0_2 bs-degrees is dense. Many of these results on s-reducibility yield interesting corollaries for Q-reducibility as well.
Omanadze, R.S.h., Sorbi, A. (2006). Strong enumeration reducibilities. ARCHIVE FOR MATHEMATICAL LOGIC, 45(7), 869-912 [10.1007/s00153-006-0012-4].
Strong enumeration reducibilities
SORBI, ANDREA
2006-01-01
Abstract
We investigate strong versions of enumeration reducibility, the most important one being s-reducibility. We prove that every countable distributive lattice is embeddable into the local structure L(D_s) of the s-degrees. However, L(D_s) is not distributive. We show that on \Delta^0_2 sets s-reducibility coincides with its finite branch version; the same holds of e-reducibility. We prove some density results for L(D_s). In particular L(D_s) is upwards dense. Among the results about reducibilities that are stronger than s-reducibility, we show that the structure of the \Delta^0_2 bs-degrees is dense. Many of these results on s-reducibility yield interesting corollaries for Q-reducibility as well.File | Dimensione | Formato | |
---|---|---|---|
fulltext.pdf
non disponibili
Descrizione: Articolo unico
Tipologia:
PDF editoriale
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
514.53 kB
Formato
Adobe PDF
|
514.53 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/24435