University of Notre Dame
Browse
- No file added yet -

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

Download (274.67 kB)
thesis
posted on 2009-04-16, 00:00 authored by Christina M. Maher
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.

History

Date Modified

2017-06-05

Defense Date

2009-03-25

Research Director(s)

Julia Knight

Committee Members

Steven Buechler Sergei Starchenko Peter Cholak

Degree

  • Doctor of Philosophy

Degree Level

  • Doctoral Dissertation

Language

  • English

Alternate Identifier

etd-04162009-154120

Publisher

University of Notre Dame

Program Name

  • Mathematics

Usage metrics

    Dissertations

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC