Let K be a class of structures closed under isomorphism. In a meeting in Kazan in 1997, Goncharov gave a talk on computable structure theory. He stated a large number of problems calling for the classification of computable members of various classes. At the end of the talk, Shore asked what would convince Goncharov to give up. In model theory, there are ``many models'' theorems. In descriptive set theory, there are Borel completeness theorems. Goncharov and I considered different approaches to classification and non-classification for computable structures, eventually settling on one as most productive.
Let I(K) be the set of computable indices for members of K. Let E(K) be the set of pairs (a,b) such that a,b Î I(K), and the structures with indices a and b are isomorphic. Assuming that I(K) is D11, E(K) is always S11. If E(K) is not D11, then there cannot be simple invariants distinguishing among computable members of K. (It follows that there is no computable bound on Scott ranks of computable members of K, and there is no hyperarithmetical Friedberg enumeration of computable members of K, up to isomorphism.)
It is well-known that if K is the class of linear orderings, Boolean algebras, or Abelian p-groups, then E(K) is S11 complete. (Proofs may be extracted from a 1989 paper of Friedman and Stanley, but the results may be older.) Calvert has shown that for the class K of undirected graphs, fields of a fixed characteristic, or real-closed fields, E(K) is S11 complete. For the class K of vector spaces over a fixed infinite computable field, or algebraically closed fields of a fixed characteristic, E(K) is P03 complete.