Decidability and Undecidability in the Enumeration Degrees

Abstract: For most “natural” degree structures, the full first-order theory (in the language of partial ordering) is as complicated full first or second-order arithmetic, so it is natural to try to determine the quantifier level at which undecidability starts. For most “natural” degree structures, this seems to happen when we move from the AE-theory to the EAE-theory. I will survey some of the results from the past fifty years in this area and then focus on a new joint result with Slaman and M. Soskova on the degree structure of the enumeration degrees: By proving a strong embedding result for finite distributive lattices into intervals of the enumeration degrees, we obtain the undecidability of the EAE-theory, and a partial decidability result for the AE-theory, namely, for the extension of embeddings problem.

logic

Audience: researchers in the topic

Computability theory and applications

Series comments: Description: Computability theory, logic

The goal of this endeavor is to run a seminar on the platform Zoom on a weekly basis, perhaps with alternating time slots each of which covers at least three out of four of Europe, North America, Asia, and New Zealand/Australia. While the meetings are always scheduled for Tuesdays, the timezone varies, so please refer to the calendar on the website for details about individual seminars.