Abstract
In this paper we provide corrections of an inaccuracy made in our previous paper. Namely, we correctly prove that there exists a computable linear order and a series of natural relations on it, the spectrum of which consist of exactly all n-c.e. degrees (for any natural number n).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
REFERENCES
Ya. A. Mikhailovskaya and A. N. Frolov, “Computable linear orders and the Ershov hierarchy,” Russ. Math. 62 (1), 58–64 (2018). https://doi.org/10.3103/S1066369X18010085
M. Moses, “Recursive linear orders with recursive successivities,” Ann. Pure Appl. Logic 27 (3), 253–264 (1984). https://doi.org/10.1016/0168-0072(84)90028-9
M. Moses, “Recursive properties of isomophism types,” PhD Thesis (Monash Univ., Clayton, Victoria, Australia, 1983).
M. Moses, “Relations intrinsically recursive in linear orders,” Z. Math. Logik Grundlagen Math. 32 (5), 467–472 (1986). https://doi.org/10.1002/malq.19860322514
J. Chubb, A. Frolov, and V. Harizanov, “Degree spectra of the successor relation of computable linear orderings,” Arch. Math. Logic 48 (1), 7–13 (2009). https://doi.org/10.1007/s00153-008-0110-6
A. N. Frolov, “Presentations of the successor relation of computable linear ordering,” Russ. Math. 54 (7), 64–74 (2010). https://doi.org/10.3103/S1066369X10070078
A. N. Frolov, “A note on \(\Delta _{2}^{0}\)-spectra of linear orderings and degree spectra of the successor relation,” Russ. Math. 57 (11), 65–68 (2013). https://doi.org/10.3103/S1066369X13110078
M. V. Zubkov, “Initial segments of computable linear orders with additional computable predicates,” Algebra Logic 48 (5), 321–329 (2009). https://doi.org/10.1007/s10469-009-9068-7
W. P. Turner, “Computable linear orders and turing reductions,” Master’s Thesis (Univ. of Connecticut, Mansfield, Conn., 2012).
R. I. Bikmukhametov, “Initial segments of computable linear orders with computable natural relations,” Russ. Math. 60 (6), 12–20 (2016). https://doi.org/10.3103/S1066369X16060025
R. I. Bikmukhametov, “\(\Sigma _{2}^{0}\)-Initial segments of computable linear orders,” Algebra Logic, 53 (3), 266–267 (2014). https://doi.org/10.1007/s10469-014-9288-3
R. I. Bikmukhametov, “Codings on linear orders and algorithmic independence of natural relations,” Lobachevskii J. Math. 35 (4), 327–332 (2014). https://doi.org/10.1134/S1995080214040131
R. I. Bikmukhametov, “Algorithmic independence of natural relations on computable linear orders,” Uch. Zap. Kazan. Univ., Ser. Fiz.-Mat. Nauki 155 (3), 80–90 (2013).
R. I. Bikmukhametov, M. S. Eryashkin, and A. N. Frolov, “Degree spectra of the block relation of 1-computable linear orders,” Uch. Zap. Kazan. Univ., Ser. Fiz.-Mat. Nauki 159 (3), 296–305 (2017).
J. B. Remmel, “Recursively categorical linear orderings,” Proc. Am. Math. Soc. 83 (2), 387–391 (1981). https://doi.org/10.1090/S0002-9939-1981-0624937-1
R. G. Downey and C. G. Jockusch, “Every low Boolean algebra is isomorphic to a recursive one,” Proc. Am. Math. Soc. 122 (3), 871–880 (1994). https://doi.org/10.1090/S0002-9939-1994-1203984-4
J. J. Thurber, “Every low2 Boolean algebra has a recursive copy,” Proc. Am. Math. Soc. 123 (12), 3859–3866 (1995). https://doi.org/10.1090/S0002-9939-1995-1283564-6
J. F. Knight and M. Stob, “Computable Boolean algebras,” J. Symbolic Logic 65 (4), 1605–1623 (2000). https://doi.org/10.2307/2695066
A. Montalbán, “Notes on the jump of a structure,” in Mathematical Theory and Computational Practice, CiE 2009, Ed. by K. Ambos-Spies, B. Löwe, and W. Merkle, Lecture Notes in Computer Science, Vol. 5635 (Springer, Berlin, 2009), pp. 372–378. https://doi.org/10.1007/978-3-642-03073-4_38
A. N. Frolov, “\(\Delta _{2}^{0}\)-copies of linear orderings,” Algebra Logic 45 (3), 201–209 (2006). https://doi.org/10.1007/s10469-006-0017-4
A. N. Frolov, “Linear orderings of low degree,” Sib. Math. J. 51 (5), 913–925 (2010). https://doi.org/10.1007/s11202-010-0091-7
A. N. Frolov, “Low linear orderings,” J. Logic Comput. 22 (4), 745–754 (2012). https://doi.org/10.1093/logcom/exq040
A. N. Frolov, “Scattered linear orderings with no computable presentation,” Lobachevskii J. Math. 35 (1), 19–22 (2014). https://doi.org/10.1134/S199508021401003X
A. N. Frolov, “Computable presentability of countable linear orders,” J. Math. Sci. 256 (2), 199–233 (2021). https://doi.org/10.1007/s10958-021-05426-y
P. E. Alaev, J. Thurber, and A. N. Frolov, “Computability on linear orderings enriched with predicates,” Algebra Logic 48 (5), 313–320 (2009). https://doi.org/10.1007/s10469-009-9067-8
D. R. Hirschfeldt, “Degree spectra of intrinsically c.e. relations,” J. Symbolic Logic 66 (2), 441–469 (2001). https://doi.org/10.2307/2695024
Funding
The work of the first author was carried out as part of the implementation of the development program of the Scientific and Educational Mathematical Center of the Volga Federal District, agreement no. 075-02-2021-1393. The work of the second author was supported by the Russian Foundation for Basic Research, project no. 20-31-70012.
Author information
Authors and Affiliations
Corresponding authors
Ethics declarations
The authors declare that they have no conflicts of interest.
Additional information
Translated by E. Seifina
About this article
Cite this article
Michailovskaya, Y.A., Frolov, A.N. Computable Linear Orders and the Ershov Hierarchy. Russ Math. 66, 71–74 (2022). https://doi.org/10.3103/S1066369X22010066
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.3103/S1066369X22010066