Antonio Montalban

Abstract: Various results in different areas of Computability Theory are proved. First we work with the Turing degree structure, proving some embeddablity and decidability results. To cite a few: we show that every countable upper semilattice containing a jump operation can be embedded into the Turing degrees, of course, preserving jump and join; we show that every finite partial ordering labeled with the classes in the generalized high/low hierarchy can be embedded into the Turing degrees; we show that every generalized high degree has the complementation property; and we show that if a Turing degree a is either 1-generic and delta-zero-one, 2-generic and arithmetic, n-REA, or arithmetically generic, then the theory of the partial ordering of the Turing degrees below a is recursively isomorphic to true first order arithmetic.

Second, we work with equimorphism types of linear orderings from the viewpoints of Computable Mathematics and Reverse Mathematics. (Two linear orderings are equimorphic if they can be embedded in each other.) Spector proved in 1955 that every hyperarithmetic ordinal is isomorphic to a recursive one. We extend his result and prove that every hyperarithmetic linear ordering is equimorphic to a recursive one. From the viewpoint of Reverse Mathematics, we look at the strength of Fraïssé's conjecture. From our results, we deduce that Fraïssé's conjecture is sufficient and necessary to develop a reasonable theory of equimorphism types of linear orderings. Other topics we include in this thesis are the following: we look at structures for which Arithmetic Transfinite Recursion is the natural system to study them; we study theories of hyperarithmetic analysis and present a new natural example; we look at the complexity of the elementary equivalence problem for Boolean algebras; and we prove that there is a minimal pair of Kolmogorov-degrees.