Algebra i logika
General information
Latest issue
Impact factor

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Algebra Logika:

Personal entry:
Save password
Forgotten password?

Algebra Logika, 2014, Volume 53, Number 1, Pages 60–108 (Mi al624)  

This article is cited in 6 scientific papers (total in 6 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.

Full text: PDF file (415 kB)
References: PDF file   HTML file

English version:
Algebra and Logic, 2014, 53:1, 39–69

Bibliographic databases:

UDC: 510.5
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

Citation in format AMSBIB
\by D.~Cenzer, V.~Harizanov, J.~B.~Remmel
\paper Computability-theoretic properties of injection structures
\jour Algebra Logika
\yr 2014
\vol 53
\issue 1
\pages 60--108
\jour Algebra and Logic
\yr 2014
\vol 53
\issue 1
\pages 39--69

Linking options:

    SHARE: FaceBook Twitter Livejournal

    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. E. B. Fokina, V. Harizanov, A. Melnikov, “Computable model theory”, Turing's Legacy: Developments From Turing's Ideas in Logic, Lecture Notes in Logic, 42, ed. R. Downey, Cambridge Univ Press, 2014, 124–194  mathscinet  isi
    2. F. Adams, D. Cenzer, “Computability and categoricity of weakly ultrahomogeneous structures”, Computability, 6:4 (2017), 365–389  crossref  mathscinet  zmath  isi  scopus
    3. H. J. Walker, “Computable isomorphisms for certain classes of infinite graphs”, J. Knot Theory Ramifications, 27:7, SI (2018), 1841012  crossref  mathscinet  zmath  isi  scopus
    4. N. A. Bazhenov, “Spektry kategorichnosti vychislimykh struktur”, Trudy seminara kafedry algebry i matematicheskoi logiki Kazanskogo (Privolzhskogo) federalnogo universiteta, Itogi nauki i tekhn. Ser. Sovrem. mat. i ee pril. Temat. obz., 157, VINITI RAN, M., 2018, 42–58  mathnet  mathscinet
    5. S. Boyadzhiyska, K. Lange, A. Raz, R. Scanlon, J. Wallbaum, X. Zhang, “Classifications of definable subsets”, Algebra and Logic, 58:5 (2019), 383–404  mathnet  crossref  crossref  isi
    6. E. Fokina, V. Harizanov, D. Turetsky, “Computability-theoretic categoricity and Scott families”, Ann. Pure Appl. Log., 170:6 (2019), 699–717  crossref  mathscinet  zmath  isi  scopus
  • Алгебра и логика Algebra and Logic
    Number of views:
    This page:172
    Full text:43
    First page:12

    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021