Algebra i logika
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Subscription Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Algebra Logika: Year: Volume: Issue: Page: Find

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

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
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
\Bibitem{CenHarRem14} \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 \mathnet{http://mi.mathnet.ru/al624} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=3237623} \transl \jour Algebra and Logic \yr 2014 \vol 53 \issue 1 \pages 39--69 \crossref{https://doi.org/10.1007/s10469-014-9270-0} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000337279400005} \scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84902345752} 

• http://mi.mathnet.ru/eng/al624
• http://mi.mathnet.ru/eng/al/v53/i1/p60

 SHARE:

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
2. F. Adams, D. Cenzer, “Computability and categoricity of weakly ultrahomogeneous structures”, Computability, 6:4 (2017), 365–389
3. H. J. Walker, “Computable isomorphisms for certain classes of infinite graphs”, J. Knot Theory Ramifications, 27:7, SI (2018), 1841012
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
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
6. E. Fokina, V. Harizanov, D. Turetsky, “Computability-theoretic categoricity and Scott families”, Ann. Pure Appl. Log., 170:6 (2019), 699–717
•  Number of views: This page: 172 Full text: 43 References: 33 First page: 12