Soare and Simpson considered sets without subsets of higher Turing degree. In this paper we consider sets which are not many-one reducible to any of their subsets, which are set without subsets without subsets of higher many-one degree, and examine how structurally easy can be such sets. In other words, we ask what is the smallest class of the Kleenes Hierarchy containing such sets. We prove that the smallets such class is the class of the co-r.e. sets.

Sets without subsets of higher many-one degree

CINTIOLI, Patrizio
2005-01-01

Abstract

Soare and Simpson considered sets without subsets of higher Turing degree. In this paper we consider sets which are not many-one reducible to any of their subsets, which are set without subsets without subsets of higher many-one degree, and examine how structurally easy can be such sets. In other words, we ask what is the smallest class of the Kleenes Hierarchy containing such sets. We prove that the smallets such class is the class of the co-r.e. sets.
2005
262
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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: https://hdl.handle.net/11581/202733
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact