Algebraic structure and computable structure
Wesley Calvert, Julia F. Knight · 2005
The problem often arises, given some class of objects, to classify its members up to isomorphism. The goal of classification theory is to determine whether there is a satisfactory classification, and, if so, to give it. For instance, vector spaces over a fixed field are classified by the dimension. We will consider computable structures, i.e. structures with computable atomic diagram. We write Ae for the computable structure with index e. If K is a class of structures, we write IK=ev Ae∈K and define the isomorphism problem for K to be EK= a,ba,b∈IK andAa sAb . For some classes (graphs, linear orders, Abelian p-groups, etc.), it is known that the isomorphism problem is m-complete S11 . This thesis describes the addition of new items to this list, and gives the precise complexity for many simpler classes. Theorem. (1) If K is the set of computable members of either of the following, then E(K) is m-complete S11 : (a) Fields of any fixed characteristic; (b) Real closed ordered fields. (2) If K is the set of computable members of either of the following, then E(K) is m-complete P03 : (a) The class of models of a first-order strongly minimal theory which is not a0 -categorical but which has effective elimination of quantifiers and a computable model. (b) Archimedean real closed ordered fields. (3) Let α be a computable limit ordinal, and let ad=sup wdg<a (2γ + 3). If Kα is the class of reduced Abelian p-groups of length at most α then E(Kα) is P0ad complete. (4) The isomorphism problem for computable torsion-free Abelian groups is not hyperarithmetical. We will also describe related collaborative work in which the author is involved. This includes a different notion of classification, as well as preliminary results on the following: the complexity of the index sets of particular structures, a calculation of the complexity of the set of indices for structures with Scott rank α, where α is either wCK1 or wCK1 + 1, and the construction of a structure of Scott rank wCK1 with a strong approximability property.