Logical Approaches to Computational Barriers

Extensions of the semi-lattice of the enumeration degrees

Speaker:
| Ivan N. Soskov |

Slot: |
Array, 14:30-14:50, col. 1 |

For every recursive ordinal $\alpha$ a reducibility on all sequences of sets of natural numbers of length $\alpha$ is defined. The induced equivalence classes are called $\alpha$-enumeration degrees. The 1-enumeration degrees coincide with the enumeration degrees and for all $\alpha < \beta$ there exists a natural embedding of the $\alpha$-enumeration degrees into the $\beta$-enumeration degrees which is proper. In the talk we discuss several properties of the $\alpha$-enumeration degrees. Analogues of the Selman's Theorem, The Minimal Pair Theorem, The Exact Pair Theorem and the existence of Quasi-minimal degrees are demonstrated. A jump operation on $\alpha$-enumeration degrees is defined and the respective Jump inversion theorem is proved. We show also that the $\Sigma^0_2$, $\omega$-enumeration degrees are dense.

websites: Arnold Beckmann | 2006-05-02 |