Decidability and Definability in the 0 -Enumeration Degrees
Thomas F. Kent · 2005
Enumeration reducibility was introduced by Friedberg and Rogers in 1959 as a positive reducibility between sets. The enumeration degrees provide a wider context in which to view the Turing degrees by allowing us to use any set as an oracle instead of just total functions. However, in spite of the fact that there are several applications of enumeration reducibility in computable mathematics, until recently relatively little research had been done in this area. In Chapter 2 of my thesis, I show that the ∀∃∀-fragment of the first order theory of the Σ2-enumeration degrees is undecidable. I then show how this result actually demonstrates that the ∀∃∀-theory of any substructure of the enumeration degrees which contains the ∆2-degrees is undecidable. In Chapter 3, I present current research that Andrea Sorbi and I are engaged in, in regards to classifying properties of non-splitting Σ2-degrees. In particular I give proofs that there is a properly Σ2-enumeration degree and that every ∆ 0 2-enumeration degree bounds a non-splitting ∆2-degree. Advisor: Prof. Steffen Lempp