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

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.
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 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.

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