\(\Sigma_1^0\) and \(\Pi_1^0\) equivalence structures (Q639658)

Effective presentations of equivalence structures are discussed. The authors study algorithmic properties of positive (\(\Sigma_1^0\)), negative (\(\Pi_1^0\)), computable, and decidable equivalence structures and relations between them. Also, the authors investigate the complexity of isomorphisms between these structures. A preliminary version of this paper appeared in [Lect. Notes Comput. Sci. 5635, 99--108 (2009; Zbl 1239.03023)]. The notion of character plays a key role in this paper. Any set \(K\subseteq(\omega-\{0\})\times(\omega-\{0\})\) such that, for all \(n>0\) and \(k\), \(\langle k,n+1\rangle\in K\) implies \(\langle k,n\rangle\in K\), is called a character. Given an equivalence structure \(\mathcal{A}\), the character of \(\mathcal{A}\) is the set \[ \chi(\mathcal{A})=\{\langle k,n\rangle\mid n,k>0\,\&\,\mathcal{A} \text{ has at least \(n\) equivalence classes of size }k\}. \] In Section 1, it is proved that any \(\Sigma_2^0\) character corresponds to some positive equivalence structure. Conversely, if \(\mathcal{A}\) has a positive presentation, that its character belongs to \(\Sigma_2^0\). As a corollary of this assertion, together with previous results, there exists a positive structure which has no computable presentation. In Section 3, the relations between negative equivalence structures and structures from the remaining classes are discussed. In Section 5, it is proved that for any equivalence structure \(\mathcal{A}\), \(\mathrm{Th}(\mathcal{A})\) and \(\chi(\mathcal{A})\) have the same Turing degree. As a corollary, decidability of \(\mathrm{Th}(\mathcal{A})\) is equivalent to computability of \(\chi(\mathcal{A})\).