Equivalence Relations on Classes of Computable Structures

摘要

If L is a finite relational language then all computable L-structures can be effectively enumerated in a sequence {A_n}_(n∈ω) in such a way that for every computable L-structure B an index n of its iso-morphic copy An can be found effectively and uniformly. Having such a universal computable numbering, we can identify computable structures with their indices in this numbering. If K is a class of L-structures closed under isomorphism we denote by K~c the set of all computable members of K. We measure the complexity of a description of K~c or of an equivalence relation on K~c via the complexity of the corresponding sets of indices. If the index set of K~c is hyperarithmetical then (the index sets of) such natural equivalence relations as the isomorphism or bi-embeddability relation are ∑~1_1. In the present paper we study the status of these ∑~1_1 equivalence relations (on classes of computable structures with hyperarithmetical index set) within the class of ∑~1_1 equivalence relations as a whole, using a natural notion of hyperarithmetic reducibility.