Computability in Europe 2006
Logical Approaches to Computational Barriers


Regular Talk:
Extensions of the semi-lattice of the enumeration degrees


Speaker: Ivan N. Soskov
Slot: Array, 14:30-14:50, col. 1

Abstract

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