2012 | OriginalPaper | Buchkapitel
An Application of 1-Genericity in the Enumeration Degrees
verfasst von : Liliana Badillo, Charles M. Harris
Erschienen in: Theory and Applications of Models of Computation
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Using results from the local structure of the enumeration degrees we show the existence of prime ideals of
enumeration degrees. We begin by showing that there exists a 1-generic enumeration degree
which is noncuppable—and so properly downwards
$\Sigma^0_2$
—and low
2
. The notion of
enumeration
1
-genericity
appropriate to positive reducibilities is introduced and a set
A
is defined to be
symmetric enumeration
1
-generic
if both
A
and
$\ensuremath{\overline{A}} $
are enumeration 1-generic. We show that, if a set is 1-generic then it is symmetric enumeration 1-generic, and we prove that for any
enumeration 1-generic set
B
the class
$\{\, X \,\mid \, \;\ensuremath{\negmedspace\leq_{\ensuremath{\mathrm{e}} }\negmedspace}\; B \,\}$
is uniform
. Thus, picking 1-generic
(from above) and defining
it follows that every
only contains
sets. Since
is properly
$\Sigma^0_2$
we deduce that
contains no
$\Delta^0_2$
sets and so is itself properly
.