On a question of Kalimullin

Downey, Rod; Igusa, Gregory; Melnikov, Alexander

doi:10.1090/proc/13954

On a question of Kalimullin
HTML articles powered by AMS MathViewer

by Rod Downey, Gregory Igusa and Alexander Melnikov PDF

Proc. Amer. Math. Soc. 146 (2018), 3553-3563 Request permission

Abstract:

We prove that for every computable limit ordinal $\alpha$ there exists a computable structure $\mathcal {A}$ which is $\Delta ^0_\alpha$-categorical and $\alpha$ is smallest such, but nonetheless for every isomorphic computable copy $\mathcal {B}$ of $\mathcal {A}$ there exists a $\beta < \alpha$ such that $\mathcal {A} \cong _{\Delta ^0_\beta } \mathcal {B}$. This answers a question raised by Kalimullin in personal communication with the third author.

References

C. J. Ash and J. Knight, Computable structures and the hyperarithmetical hierarchy, Studies in Logic and the Foundations of Mathematics, vol. 144, North-Holland Publishing Co., Amsterdam, 2000. MR 1767842
C. J. Ash, Recursive labelling systems and stability of recursive structures in hyperarithmetical degrees, Trans. Amer. Math. Soc. 298 (1986), no. 2, 497–514. MR 860377, DOI 10.1090/S0002-9947-1986-0860377-7
Rodney G. Downey, Asher M. Kach, Steffen Lempp, Andrew E. M. Lewis-Pye, Antonio Montalbán, and Daniel D. Turetsky, The complexity of computable categoricity, Adv. Math. 268 (2015), 423–466. MR 3276601, DOI 10.1016/j.aim.2014.09.022
Rodney Downey and Alexander G. Melnikov, Effectively categorical abelian groups, J. Algebra 373 (2013), 223–248. MR 2995024, DOI 10.1016/j.jalgebra.2012.09.020
Yuri L. Ershov and Sergei S. Goncharov, Constructive models, Siberian School of Algebra and Logic, Consultants Bureau, New York, 2000. MR 1749622, DOI 10.1007/978-1-4615-4305-3
S. S. Gončarov, The problem of the number of nonautoequivalent constructivizations, Algebra i Logika 19 (1980), no. 6, 621–639, 745 (Russian). MR 622606
S. S. Gončarov, Groups with a finite number of constructivizations, Dokl. Akad. Nauk SSSR 256 (1981), no. 2, 269–272 (Russian). MR 600943
Sergei S. Goncharov, Countable Boolean algebras and decidability, Siberian School of Algebra and Logic, Consultants Bureau, New York, 1997. MR 1444819
Denis R. Hirschfeldt, Degree spectra of intrinsically c.e. relations, J. Symbolic Logic 66 (2001), no. 2, 441–469. MR 1833490, DOI 10.2307/2695024
P. LaRoche, Recursively presented Boolean algebras, Notices AMS, 24:552–553, 1977.
Steffen Lempp and Manuel Lerman, Iterated trees of strategies and priority arguments, Arch. Math. Logic 36 (1997), no. 4-5, 297–312. Sacks Symposium (Cambridge, MA, 1993). MR 1473027, DOI 10.1007/s001530050067
A. I. Mal′cev, Constructive algebras. I, Uspehi Mat. Nauk 16 (1961), no. 3 (99), 3–60 (Russian). MR 0151377
Antonio Montalbán, A computability theoretic equivalent to Vaught’s conjecture, Adv. Math. 235 (2013), 56–73. MR 3010050, DOI 10.1016/j.aim.2012.11.012
Antonio Montalbán, Priority arguments via true stages, J. Symb. Log. 79 (2014), no. 4, 1315–1335. MR 3343540, DOI 10.1017/jsl.2014.11
Antonio Montalbán, Analytic equivalence relations satisfying hyperarithmetic-is-recursive, Forum Math. Sigma 3 (2015), Paper No. e8, 11. MR 3376734, DOI 10.1017/fms.2015.5
A. Nurtazin. Computable classes and algebraic criteria of autostability. Summary of Scientific Schools, Math. Inst. SB USSRAS, Novosibirsk, 1974.