Computability-theoretic properties of injection structures

D. Cenzer ; V. Harizanov ; J. B. Remmel

Algebra i logika, Tome 53 (2014) no. 1, pp. 60-108.

Résumé

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.

Détail

Keywords: computability theory, effective categoricity, computable model theory.
Mots-clés : injections, permutations

Bibliographie

[1] E. B. Fokina, I. Kalimullin, R. Miller, “Degrees of categoricity of computable structures”, Arch. Math. Logic, 49:1 (2010), 51–67 | DOI | MR | Zbl

[2] B. F. Csima, J. N. Y. Franklin, R. A. Shore, “Degrees of categoricity and the hyperarithmetic hierarchy”, Notre Dame J. Formal Logic, 54:2 (2013), 215–231 | DOI | MR | Zbl

[3] R. Miller, “$\mathbf d$-computable categoricity for algebraic fields”, J. Symb. Log., 74:4 (2009), 1325–1351 | DOI | MR | Zbl

[4] W. Calvert, D. Cenzer, V. Harizanov, A. Morozov, “Effective categoricity of equivalence structures”, Ann. Pure Appl. Logic, 141:1/2 (2006), 61–78 | DOI | MR | Zbl

[5] D. Cenzer, G. LaForte, J. B. Remmel, “Equivalence structures and isomorphisms in the difference hierarchy”, J. Symb. Log., 74:2 (2009), 535–556 | DOI | MR | Zbl

[6] D. Cenzer, V. Harizanov, J. B. Remmel, “$\Sigma^0_1$ and $\Pi^0_1$ equivalence structures”, Ann. Pure Appl. Logic, 162:7 (2011), 490–503 | DOI | MR | Zbl

[7] N. G. Khisamiev, “Constructive abelian groups”, Handbook of recursive mathematics, v. 2, eds. Yu. L. Ershov, S. S. Goncharov, A. Nerode, J. B. Remmel, Elsevier, Amsterdam, 1998, 1177–1230 | MR

[8] C. J. Ash, J. F. Knight, Computable structures and the hyperarithmetical hierarchy, Stud. Logic Found. Math., 144, Elsevier Sci. B.V., Amsterdam etc., 2000 | MR | Zbl

[9] R. I. Soare, Recursively enumerable sets and degrees, Perspect. Math. Log., Omega Series, Springer-Verlag, Berlin etc., 1987 ; R. I. Soar, Vychislimo perechislimye mnozhestva i stepeni, Kazanskoe matem. ob-vo, Kazan, 2000 | DOI | MR | MR | Zbl

[10] S. S. Goncharov, Yu. L. Ershov, Konstruktivnye modeli, Sibirskaya shkola algebry i logiki, Nauchnaya kniga, Novosibirsk, 1999; Yu. L. Ershov, S. S. Goncharov, Constructive models, Sib. School Alg. Log., Consultants Bureau, New York, NY, 2000 | MR | Zbl