Abstract
We study effective categoricity for linear orderings. For a computable structure \(\mathcal {S}\), the degree of categoricity of \(\mathcal {S}\) is the least Turing degree which is capable of computing isomorphisms among arbitrary computable copies of \(\mathcal {S}\).
We build new examples of degrees of categoricity for linear orderings. We show that for an infinite computable ordinal \(\alpha \), every Turing degree c.e. in and above \(\mathbf {0}^{(2\alpha + 2)}\) is the degree of categoricity for some linear ordering. We obtain similar results for linearly ordered abelian groups and decidable linear orderings.
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. Formal Logic. Advance Publication. doi: 10.1215/00294527-3496154
Ash, C., Knight, J., Manasse, M., Slaman, T.: Generic copies of countable structures. Ann. Pure Appl. Logic 42(3), 195–205 (1989)
Ash, C.J.: Recursive labelling systems and stability of recursive structures in hyperarithmetical degrees. Trans. Am. Math. Soc. 298, 497–514 (1986)
Ash, C.J.: Stability of recursive structures in arithmetical degrees. Ann. Pure Appl. Logic 32, 113–135 (1986)
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)
Ash, C.J., Knight, J.F.: Pairs of recursive structures. Ann. Pure Appl. Logic 46(3), 211–234 (1990)
Bazhenov, N.: Autostability spectra for decidable structures. Math. Struct. Comput. Sci. (accepted)
Bazhenov, N.A.: Autostability spectra for Boolean algebras. Algebra Logic 53(6), 502–505 (2015)
Bazhenov, N.A.: Degrees of autostability for linear orderings and linearly ordered abelian groups. Algebra Logic (accepted)
Chisholm, J.: Effective model theory vs. recursive model theory. J. Symbolic Logic 55(3), 1168–1191 (1990)
Chisholm, J., Fokina, E.B., Goncharov, S.S., Harizanov, V.S., Knight, J.F., Quinn, S.: Intrinsic bounds on complexity and definability at limit levels. J. Symbolic Logic 74(3), 1047–1060 (2009)
Csima, B.F., Franklin, J.N.Y., Shore, R.A.: Degrees of categoricity and the hyperarithmetic hierarchy. Notre Dame J. Formal Logic 54(2), 215–231 (2013)
Downey, R.G.: Computability theory and linear orderings. In: Ershov, Y., Goncharov, S.S., Nerode, A., Remmel, J.B. (eds.) Handbook of Recursive Mathematics, vol. 2, pp. 823–976. Elsevier Science B.V., Amsterdam (1998). Stud. Logic Found. Math., vol. 139
Downey, R.G., Kach, A.M., Lempp, S., Lewis-Pye, A.E.M., Montalbán, A., Turetsky, D.D.: The complexity of computable categoricity. Adv. Math. 268, 423–466 (2015)
Ershov, Y.L., Goncharov, S.S.: Constructive Models. Kluwer Academic/Plenum Publishers, New York (2000)
Fokina, E., Frolov, A., Kalimullin, I.: Categoricity spectra for rigid structures. Notre Dame J. Formal Logic 57(1), 45–57 (2016)
Fokina, E.B., Harizanov, V., Melnikov, A.: Computable model theory. In: Downey, R. (ed.) Turing’s Legacy: Developments from Turing Ideas in Logic. Lecture Notes in Logic, vol. 42, pp. 124–194. Cambridge University Press, Cambridge (2014)
Fokina, E.B., Kalimullin, I., Miller, R.: Degrees of categoricity of computable structures. Arch. Math. Logic 49(1), 51–67 (2010)
Fröhlich, A., Shepherdson, J.C.: Effective procedures in field theory. Philos. Trans. Roy. Soc. London Ser. A 248, 407–432 (1956)
Frolov, A.N.: Effective categoricity of computable linear orderings. Algebra Logic 54(5), 415–417 (2015)
Goncharov, S., Harizanov, V., Knight, J., McCoy, C., Miller, R., Solomon, R.: Enumerations in computable structure theory. Ann. Pure Appl. Logic 136(3), 219–246 (2005)
Goncharov, S.S.: Degrees of autostability relative to strong constructivizations. Proc. Steklov Inst. Math. 274, 105–115 (2011)
Goncharov, S.S.: The quantity of nonautoequivalent constructivizations. Algebra Logic 16(3), 169–185 (1977)
Goncharov, S.S., Dzgoev, V.D.: Autostability of models. Algebra Logic 19(1), 28–37 (1980)
Mal’tsev, A.I.: Constructive algebras I. Russ. Math. Surv. 16, 77–129 (1961)
Mal’tsev, A.I.: On recursive abelian groups. Sov. Math. Dokl. 32, 1431–1434 (1962)
Melnikov, A.G.: Computable ordered abelian groups and fields. In: Ferreira, F., Löwe, B., Mayordomo, E., Mendes Gomes, L. (eds.) CiE 2010. LNCS, vol. 6158, pp. 321–330. Springer, Heidelberg (2010). doi:10.1007/978-3-642-13962-8_36
Miller, R.: \(\mathbf{d}\)-computable categoricity for algebraic fields. J. Symb. Log. 74(4), 1325–1351 (2009)
Remmel, J.B.: Recursively categorical linear orderings. Proc. Am. Math. Soc. 83, 387–391 (1981)
Rosenstein, J.G.: Linear Orderings, vol. 98. Academic Press, New York (1982). Pure Appl. Math
Acknowledgements
The author is grateful to Sergey Goncharov for fruitful discussions on the subject. The reported study was funded by RFBR, according to the research project No. 16-31-60058 mol_a_dk.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
A Appendix: Proof of Proposition 2
A Appendix: Proof of Proposition 2
For a non-zero countable ordinal \(\alpha \), we define the auxiliary formula \(Ord_{\alpha }(x,y)\). Suppose that the Cantor normal form of \(\alpha \) is equal to
where \(\beta _0>\beta _1>\ldots >\beta _t\) and \(0<n_i<\omega \) for all i. We set:
It is not difficult to prove the following claim.
Lemma 6
Assume that \(\beta \) is a computable ordinal, and \(\omega ^{\beta }< \alpha <\omega ^{\beta +1}\). For a well-ordering \(\mathcal {A}\) and elements \(a,b\in \mathcal {A}\), we have \(\mathcal {A}\models Ord_{\alpha }(a,b)\) iff the interval \([a,b[_{\mathcal {A}}\) is isomorphic to \(\alpha \). Moreover, the formula \(Ord_{\alpha }\) is logically equivalent to a computable \(\varSigma _{2\beta +2}\) formula.
Now suppose that \(\mathcal {L}_0\) is a computable copy of the ordinal \(\omega ^{\beta }\) with the following property: given a pair of elements \(a<_{\mathcal {L}_0} b\), one can effectively find the Cantor normal form of the interval \([a,b[_{\mathcal {L}_0}\). We may assume that \(\mathcal {L} = \mathcal {L}_0\cdot (1+\eta )\).
We describe the formally \(\varSigma ^0_{2\beta +1}\) Scott family \(\varPhi \) for the structure \(\mathcal {L}\). Let
It is easy to show that \(\psi \) is equivalent to a computable \(\varPi _{2\beta }\) formula.
First, we define the Scott formula \(\phi _a\) for an element \(a\in \mathcal {L}\). If a is the least element in \(\mathcal {L}\), then set \(\phi _a(x) = \forall y (x\le y)\). If a is not the least element and \(\mathcal {L} \models \psi (a)\), then define \(\phi _a = \psi \). Now assume that \(\mathcal {L}\not \models \psi (a)\). We find the element b such that . Let \(\gamma \) be the ordinal such that the interval \([b,a[_{\mathcal {L}}\) is isomorphic to \(\gamma \). Set
Let \(\bar{a} = a_0, a_1, \ldots , a_n\) be a tuple from \(\mathcal {L}\) such that \(a_0<_{\mathcal {L}} a_1<_{\mathcal {L}} \ldots <_{\mathcal {L}} a_n\). For \(i<n\), we set
It is straightforward to prove that \(\mathcal {L}\models \phi _{\bar{a}}(\bar{a})\). Moreover, for a tuple \(\bar{b}\) from \(\mathcal {L}\), \(\mathcal {L}\models \phi _{\bar{a}}(\bar{b})\) implies that the tuple \(\bar{b}\) is automorphic to \(\bar{a}\). Furthermore, the formula \(\phi _{\bar{a}}\) is logically equivalent to a computable \(\varSigma _{2\beta + 1}\) formula. We use the effective procedure for calculating Cantor normal forms to construct the formulas \(\phi _{\bar{a}}\) and to build the desired c.e. Scott family \(\varPhi \) consisting of computable \(\varSigma _{2\beta +1}\) formulas. Note that the formulas have no parameters. Hence, by Corollary 2, the structure \(\mathcal {L}\) is uniformly relatively \(\varDelta ^0_{2\beta +1}\) categorical.
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Bazhenov, N. (2017). A Note on Effective Categoricity for Linear Orderings. In: Gopal, T., Jäger , G., Steila, S. (eds) Theory and Applications of Models of Computation. TAMC 2017. Lecture Notes in Computer Science(), vol 10185. Springer, Cham. https://doi.org/10.1007/978-3-319-55911-7_7
Download citation
DOI: https://doi.org/10.1007/978-3-319-55911-7_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-55910-0
Online ISBN: 978-3-319-55911-7
eBook Packages: Computer ScienceComputer Science (R0)