|
This article is cited in 14 scientific papers (total in 14 papers)
Computability-theoretic properties of injection structures
D. Cenzera, V. Harizanovb, J. B. Remmelc a Dep. Math., Univ. Florida, Gainesville, FL 32611 USA
b Dep. Math., George Washington Univ., Washington, DC 20052 USA
c Dep. Math., Univ. California-San Diego, La Jolla, CA 92093 USA
Abstract:
We study computability-theoretic properties of computable injection structures and the complexity of isomorphisms between these structures. It is proved that a computable injection structure is computably categorical iff it has finitely many infinite orbits. Again, a computable injection structure is $\Delta^0_2$-categorical iff it has finitely many orbits of type $\omega$ or finitely many orbits of type $Z$. Furthermore, every computably categorical injection structure is relatively computably categorical, and every $\Delta^0_2$-categorical injection structure is $\Delta^0_2$-categorical. Analogs of these results are investigated for $\Sigma^0_1$-, $\Pi^0_1$-, and $n$-c.e. injection structures.
We study the complexity of the set of elements with orbits of a given type in computable injection structures. For example, it is proved that for every c.e. Turing degree $\mathbf b$, there is a computable injection structure $\mathcal A$ in which the set of all elements with finite orbits has degree $\mathbf b$, and for every $\Sigma^0_2$ Turing degree $\mathbf c$, there is a computable injection structure $\mathcal B$ in which the set of elements with orbits of type $\omega$ has degree $\mathbf c$. We also have various index set results for infinite computable injection structures. For example, the index set of infinite computably categorical injection structures is a $\Sigma^0_3$-complete set, and the index set of infinite $\Delta^0_2$-categorical injection structures is a $\Sigma^0_4$-complete set.
We explore the connection between the complexity of the character and the first-order theory of a computable injection structure. It is shown that for an injection structure with a computable character, there is a decidable structure isomorphic to it. However, there are computably categorical injection structures with undecidable theories.
Keywords:
computability theory, injections, permutations, effective categoricity, computable model theory.
Received: 27.11.2012 Revised: 27.07.2013
Citation:
D. Cenzer, V. Harizanov, J. B. Remmel, “Computability-theoretic properties of injection structures”, Algebra Logika, 53:1 (2014), 60–108; Algebra and Logic, 53:1 (2014), 39–69
Linking options:
https://www.mathnet.ru/eng/al624 https://www.mathnet.ru/eng/al/v53/i1/p60
|
Statistics & downloads: |
Abstract page: | 248 | Full-text PDF : | 77 | References: | 44 | First page: | 12 |
|