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

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.
Omanadze, R.S.h., & Sorbi, A. (2006). Strong enumeration reducibilities. ARCHIVE FOR MATHEMATICAL LOGIC, 45(7), 869-912 [10.1007/s00153-006-0012-4].
File in questo prodotto:
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.

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