Abstract

For a class K of structures, closed under isomorphism, the index set is the set I of all indices for computable members of K in a universal computable numbering of all computable structures for a fixed computable language. We study the complexity of the index set of class of structures with decidable theories. We first prove the result for the class of all structures in an arbitrary finite nontrivial language. After the complexity is found, we prove similar results for some well-known classes of structures, such as directed graphs, undirected graphs, partial orders and lattices