We study a strong enumeration reducibility, called bounded enumeration reducibility and denoted by $\leq_{be}$, which is a natural extension of $s$-reducibility $\leq_{s}$. We show that $\leq_{s}$, $\leq_{be}$, and enumeration reducibility do not coincide on the $\Pi^0_1$-sets, and the structure $\mathcal{D}_{be}$ of the $\be$-degrees is not elementarily equivalent to the structure of the $s$--degrees. We show also that the first order theory of $\mathcal{D}_{be}$ is computably isomorphic to true second order arithmetic: this answers an open question raised by Cooper.
Marsibilio, D., Sorbi, A. (2012). Bounded enumeration reducibility and its degree structure. ARCHIVE FOR MATHEMATICAL LOGIC, 51(1-2), 163-186 [10.1007/s00153-011-0259-2].
Bounded enumeration reducibility and its degree structure
SORBI, ANDREA
2012-01-01
Abstract
We study a strong enumeration reducibility, called bounded enumeration reducibility and denoted by $\leq_{be}$, which is a natural extension of $s$-reducibility $\leq_{s}$. We show that $\leq_{s}$, $\leq_{be}$, and enumeration reducibility do not coincide on the $\Pi^0_1$-sets, and the structure $\mathcal{D}_{be}$ of the $\be$-degrees is not elementarily equivalent to the structure of the $s$--degrees. We show also that the first order theory of $\mathcal{D}_{be}$ is computably isomorphic to true second order arithmetic: this answers an open question raised by Cooper.File | Dimensione | Formato | |
---|---|---|---|
fulltext-bounded.pdf
non disponibili
Descrizione: Articolo unico
Tipologia:
PDF editoriale
Licenza:
NON PUBBLICO - Accesso privato/ristretto
Dimensione
300.45 kB
Formato
Adobe PDF
|
300.45 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/23223