Computability in Europe 2006
Logical Approaches to Computational Barriers

Regular Talk:
Embedding the enumeration degrees in the omega-enumeration degrees

Speaker: Hristo Ganchev
Slot: Array, 11:00-11:20, col. 3


We are concerned with embeddings of the structure of
the enumeration degrees ${\mathcal D}_e=({\bf D}_e,\leq)$ in the
structure of the $\omega$-enumeration degrees ${\mathcal
D}_\omega=({\bf D}_\omega,\leq_\omega)$, not realizable as the
composition of an endomorphism of ${\mathcal D}_e$ with the
natural embedding of ${\mathcal D}_e$ in ${\mathcal D}_\omega$.
We prove that there are at least $2^{\aleph_0}$ different
embeddings, preserving the least upper bound operation, and at
least $\aleph_0$ --- preserving the jump operation. We prove a
necessary and sufficient condition for the existence of an
embedding preserving both operations. From it, we conclude that
the algebraic closure of $({\mathcal D}_e;\cup;\,')$, with respect
to the least jump-invert operation, is only emebeddable in the
algebraic closure $\bigcup{\mathcal D}_n$ of $({\bf
D}_1;\leq_\omega;\cup;\,')$. So, $\bigcup{\mathcal D}_n$ may play
an important role in the structural properties of ${\mathcal
D}_\omega$. Finally, we show that $\bigcup{\mathcal D}_n$ is first
order definable substructure of $({\mathcal D}_\omega;\cup;\,')$.

websites: Arnold Beckmann 2008-05-19