Abstract:
The categoricity spectrum of a computable structure S is the set of all Turing degrees capable of computing isomorphisms among arbitrary computable presentations of S. The degree of categoricity of S is the least degree in the categoricity spectrum of S. The paper gives a survey of results on categoricity spectra and degrees of categoricity for computable structures. We focus on the results about degrees of categoricity for linear orders and Boolean algebras. We build a new series of examples of degrees of categoricity for linear orders.
Keywords:
computable categoricity, categoricity spectrum, degree of categoricity, computable structure, linear order, Boolean algebra, decidable categoricity, autostability, autostability relative to strong constructivizations, index set.
Citation:
N. A. Bazhenov, “Categoricity spectra of computable structures”, Proceedings of the Seminar on Algebra and Mathematical Logic of the Kazan (Volga Region) Federal University, Itogi Nauki i Tekhniki. Sovrem. Mat. Pril. Temat. Obz., 157, VINITI, Moscow, 2018, 42–58; J. Math. Sci. (N. Y.), 256:1 (2021), 34–50
\Bibitem{Baz18}
\by N.~A.~Bazhenov
\paper Categoricity spectra of computable structures
\inbook Proceedings of the Seminar on Algebra and Mathematical Logic of the Kazan (Volga Region) Federal University
\serial Itogi Nauki i Tekhniki. Sovrem. Mat. Pril. Temat. Obz.
\yr 2018
\vol 157
\pages 42--58
\publ VINITI
\publaddr Moscow
\mathnet{http://mi.mathnet.ru/into406}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=3940082}
\transl
\jour J. Math. Sci. (N. Y.)
\yr 2021
\vol 256
\issue 1
\pages 34--50
\crossref{https://doi.org/10.1007/s10958-021-05419-x}
Linking options:
https://www.mathnet.ru/eng/into406
https://www.mathnet.ru/eng/into/v157/p42
This publication is cited in the following 2 articles:
Nikolay Bazhenov, “Computable Heyting Algebras with Distinguished Atoms and Coatoms”, J of Log Lang and Inf, 32:1 (2023), 3
N. A. Bazhenov, M. I. Marchuk, “On categoricity spectra for locally finite graphs”, Siberian Math. J., 62:5 (2021), 796–804
Citation in format AMSBIB
Contact us: