Abstract
In 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})}$, and
item 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}
oindent
The 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.
|
