Abstract
We study effective categoricity for homogeneous and prime models of a complete theory. For a computable structure \(\mathcal {S}\), the degree of categoricity of \(\mathcal {S}\) is the least Turing degree which can compute isomorphisms among arbitrary computable copies of \(\mathcal {S}\). We build new examples of degrees of categoricity for homogeneous models and for prime Heyting algebras, i.e. prime models of a complete extension of the theory of Heyting algebras. We show that \(\mathbf {0}^{(\omega +1)}\) is the degree of categoricity for a homogeneous model. We prove that any Turing degree which is d.c.e. in and above \(\mathbf {0}^{(n)}\), where \(3 \le n <\omega \), is the degree of categoricity for a prime Heyting algebra.
N. Bazhenov was supported by RFBR project No. 16-31-60058 mol_a_dk. M. Marchuk was supported by RFBR project No. 17-01-00247.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Anderson, B.A., Csima, B.F.: Degrees that are not degrees of categoricity. Notre Dame J. Form. Log. 57(3), 389–398 (2016). https://doi.org/10.1215/00294527-3496154
Ash, C.J.: Recursive labelling systems and stability of recursive structures in hyperarithmetical degrees. Trans. Am. Math. Soc. 298(2), 497–514 (1986). https://doi.org/10.1090/S0002-9947-1986-0860377-7
Ash, C.J., Knight, J.F.: Pairs of recursive structures. Ann. Pure Appl. Log. 46(3), 211–234 (1990). https://doi.org/10.1016/0168-0072(90)90004-L
Ash, C.J., Knight, J.F.: Computable Structures and the Hyperarithmetical Hierarchy. Studies in Logic and the Foundations of Mathematics, vol. 144. Elsevier Science B.V., Amsterdam (2000)
Bazhenov, N.: Autostability spectra for decidable structures. Math. Struct. Comput. Sci. 28(3), 392–411 (2018). https://doi.org/10.1017/S096012951600030X
Bazhenov, N.A.: Degrees of autostability for linear orders and linearly ordered abelian groups. Algebra Log. 55(4), 257–273 (2016). https://doi.org/10.1007/s10469-016-9395-4
Bazhenov, N.A.: Effective categoricity for distributive lattices and Heyting algebras. Lobachevskii J. Math. 38(4), 600–614 (2017). https://doi.org/10.1134/S1995080217040035
Bazhenov, N.A., Marchuk, M.I.: Degrees of autostability for prime Boolean algebras. Algebra Logic. To appear
Bazhenov, N.A., Yamaleev, M.M.: Degrees of categoricity of rigid structures. In: Kari, J., Manea, F., Petre, I. (eds.) CiE 2017. LNCS, vol. 10307, pp. 152–161. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-58741-7_16
Chang, C.C., Keisler, H.J.: Model Theory. North-Holland, Amsterdam (1973)
Csima, B.F., Franklin, J.N.Y., Shore, R.A.: Degrees of categoricity and the hyperarithmetic hierarchy. Notre Dame J. Form. Log. 54(2), 215–231 (2013). https://doi.org/10.1215/00294527-1960479
Fokina, E., Frolov, A., Kalimullin, I.: Categoricity spectra for rigid structures. Notre Dame J. Form. Log. 57(1), 45–57 (2016). https://doi.org/10.1215/00294527-3322017
Fokina, E.B., Harizanov, V., Melnikov, A.: Computable model theory. In: Downey, R. (ed.) Turing’s Legacy: Developments from Turing’s Ideas in Logic, Lect. Notes Logic, vol. 42, pp. 124–194. Cambridge University Press, Cambridge (2014). https://doi.org/10.1017/CBO9781107338579.006
Fokina, E.B., Kalimullin, I., Miller, R.: Degrees of categoricity of computable structures. Arch. Math. Log. 49(1), 51–67 (2010). https://doi.org/10.1007/s00153-009-0160-4
Fröhlich, A., Shepherdson, J.C.: Effective procedures in field theory. Philos. Trans. Roy. Soc. Lond. Ser. A 248, 407–432 (1956). https://doi.org/10.1098/rsta.1956.0003
Frolov, A.N.: Effective categoricity of computable linear orderings. Algebra Log. 54(5), 415–417 (2015). https://doi.org/10.1007/s10469-015-9362-5
Goncharov, S.S., Bazhenov, N.A., Marchuk, M.I.: Index set of linear orderings that are autostable relative to strong constructivizations. J. Math. Sci. 221(6), 840–848 (2017). https://doi.org/10.1007/s10958-017-3272-0
Mal’tsev, A.I.: Constructive algebras I. Russ. Math. Surv. 16, 77–129 (1961). https://doi.org/10.1070/RM1961v016n03ABEH001120
Mal’tsev, A.I.: On recursive abelian groups. Sov. Math. Dokl. 32, 1431–1434 (1962)
Miller, R.: d-computable categoricity for algebraic fields. J. Symb. Log. 74(4), 1325–1351 (2009). https://doi.org/10.2178/jsl/1254748694
Miller, R., Shlapentokh, A.: Computable categoricity for algebraic fields with splitting algorithms. Trans. Am. Math. Soc. 367(6), 3955–3980 (2015). https://doi.org/10.1090/S0002-9947-2014-06093-5
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Bazhenov, N., Marchuk, M. (2018). Degrees of Categoricity for Prime and Homogeneous Models. In: Manea, F., Miller, R., Nowotka, D. (eds) Sailing Routes in the World of Computation. CiE 2018. Lecture Notes in Computer Science(), vol 10936. Springer, Cham. https://doi.org/10.1007/978-3-319-94418-0_4
Download citation
DOI: https://doi.org/10.1007/978-3-319-94418-0_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-94417-3
Online ISBN: 978-3-319-94418-0
eBook Packages: Computer ScienceComputer Science (R0)