Logical Approaches to Computational Barriers

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 |