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

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.
Scheda breve Scheda completa Scheda completa (DC)
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].
File in questo prodotto:
File
fulltext-bounded.pdf

non disponibili

Descrizione: Articolo unico
Tipologia: PDF editoriale
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 300.45 kB
Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11365/23223