On Embeddings of Computable Structures, Classes of Structures and Computable Isomorphism

Mathematicians of all sorts participate in the search to classify structures and characterize the structures which belong to a class. Logicians have worked on finding the complexity of the isomorphism relation on a class of structures, the “classification problem,” and categorizing the relative complexity of the isomorphism relation on different classes of structures. One way of comparing the complexity of the classification problem for different classes of structures uses the notion of a Turing computable embedding.This notion allows us to compare the complexity of the classification problem for certain classes of structures, and make some distinctions that cannot be made under the notion of Borel embedding. The main tool in making those distinctions, i.e. in showing non-embeddability between one class of structures and another, is the Pull-back Theorem. The Pull-back theorem for Turing computable embeddings says that if there is a Turing computable embedding between K and K', then anything you can say in the language of K' you can “pull back” and say in the language of K, with the same complexity. In this work, I consider classes of structures with countable universe, develop more general notions of embeddings between these classes, and prove corresponding Pull-back theorems.I also present a result on the complexity of computable isomorphism on the class of Boolean algebras, and joint work on the computable embedding problem, considering how hard it is to tell if one structure in a class is isomorphic to a substructure of another structure in the class.