Abstract

In computable model theory, mathematical structures are studied on the basis of their computability or computational complexity. The degree spectrum DgSp([special characters omitted]) of a countable structure [special characters omitted] is one way to measure the computability of the structure. Given various classes of countable structures, such as linear orders, groups, and graphs, we separate two classes [special characters omitted] and [special characters omitted] in the following way: we say that [special characters omitted] is distinguished from [special characters omitted] with respect to degree spectrum if there is an [special characters omitted] ∈ [special characters omitted] such that for all [special characters omitted] ∈ [special characters omitted], DgSp([special characters omitted]) ≠ DgSp([special characters omitted]). In the dissertation, we will investigate this separation idea. We look at specific choices for [special characters omitted] and [special characters omitted]—for example, we show that linear orders are distinguished from finite-components graphs, equivalence structures, rank-1 torsion-free abelian groups, and daisy graphs with respect to degree spectrum. Out of these proofs, there comes a general pattern for the kinds of structures from which linear orders are distinguished with respect to degree spectrum. In the future, we may also replace linear orders with possibly more general kinds of structures.