\(\Sigma_1^0\) and \(\Pi_1^0\) equivalence structures (Q639658): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 01:50, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | \(\Sigma_1^0\) and \(\Pi_1^0\) equivalence structures |
scientific article |
Statements
\(\Sigma_1^0\) and \(\Pi_1^0\) equivalence structures (English)
0 references
22 September 2011
0 references
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})\).
0 references
computability theory
0 references
equivalence structures
0 references
effective categoricity
0 references
computable model theory
0 references
decidable structures
0 references
positive structures
0 references
negative structures
0 references