Computability in Europe 2006
Logical Approaches to Computational Barriers

Regular Talk:
Genericity and Nonbounding

Speaker: Mariya Ivanova Soskova
Slot: Array, 10:30-10:50, col. 1


The structure of the semi lattice of the enumeration degrees has been
investigated from many aspects. One aspect is the bounding and
nonbounding properties of the enumeration degrees. Cooper, Sorbi, Lee
and Yang proved that every $\Delta^0_2$ degree bounds a minimal pair,
but there exists a $\Sigma^0_2$ degree that does not bound a minimal
pair. Copestake on the other hand proved that the degree of every
2-generic set bounds a minimal pair and conjectured that there is a
1-generic set whose degree does not bound a minimal pair. Using the
infinite injury priority method we
construct a $\Sigma^0_2$ 1-generic set, whose enumeration degree does
not bound a minimal pair, generalizing the former result and proving
Copestake's longstanding conjecture.

websites: Arnold Beckmann 2006-04-28