Logical Approaches to Computational Barriers

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 |