QuinnS042008.pdf (269.53 kB)
Algorithmic Complexity of Algebraic Structures
thesis
posted on 2008-04-18, 00:00 authored by Sara B. QuinnIn mathematics, one often tries to classify some collection of objects up to isomorphism. In mathematical logic, we can explore the complexity of that classification. A structure consists of a universe and an interpretation of a language, where the language has symbols representing constants, operations, and relations. We consider only structures whose universe is a subset of $omega$, and we define a class as a collection of structures all with the same language and closed under isomorphism. One way that the complexity of the classification problem can be explored is by looking at the index set for a computable structure. We consider indices for computable structures, and write $mathcal{A}e$ where $varphi_e = chi{d(mathcal{A})}$. The index set for $mathcal{A}$ is the set of all indices for computable isomorphic copies of $mathcal{A}$. We write[I(mathcal{A}) = { e : mathcal{A}e cong mathcal{A}}.]In the present work, the relationship between the complexity of the index set for a structure and the complexity of a sentence describing the structure (called a Scott sentence) is explored. We find an example of a structure for which there is not a match between the complexity of the index set and the complexity of a Scott sentence. We also examine the possible complexities of an index set, and give results characterizing when a particular class will have an index set that is $m$-complete at a certain complexity level.Another idea explored in the present work is that of comparing the complexity of the classification problem for various classes of structures, using the notion of a Turing computable embedding.oindent extbf{Definition}.A Turing computable embedding of $K$ into $K'$ is an operator $Phi = varphi_e$ such that egin{enumerate}item for each $mathcal{A}in K$, there exists $mathcal{B}in K'$ such that $varphi_e^{D(mathcal{A})} = chi{D(mathcal{B})}$, anditem if $mathcal{A},mathcal{A}‘in K$ correspond, respectively, to $mathcal{B},mathcal{B}'in K’$, then $mathcal{A}congmathcal{A}‘$ if and only if $mathcal{B}congmathcal{B}’$. end{enumerate}oindentThe ordering of classes of structures that arises from this embedding allows us to compare the complexity of the classification problem for those classes.In the present work, we give characterizations for the classes of structures that embed into the class of equivalence structures, as well as into the class of reduced Abelian $p$-groups of various lengths.
History
Date Modified
2017-06-02Defense Date
2008-04-04Research Director(s)
Julia KnightCommittee Members
Sergei Starchenko Peter Cholak Valentina HarizanovDegree
- Doctor of Philosophy
Degree Level
- Doctoral Dissertation
Language
- English
Alternate Identifier
etd-04182008-120411Publisher
University of Notre DameProgram Name
- Mathematics
Usage metrics
Categories
No categories selectedLicence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC