Abstract
We study an algorithmic dependence of natural relations on linear orders relative to the class of their computable presentations. We give complete description of possible combinations of natural relations for which there is a computable linear order such that in any of its computable presentation a given combination of relations is not computable.
Similar content being viewed by others
References
R. I. Soare, Recursively Enumerable Sets and Degrees (Springer-Verlag, Berlin, 1987).
J. G. Rosenstein, Linear Orderings (Acad. Press, New York, 1982).
R. I. Bikmukhametov, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki 155(3), 80 (2013).
M. Moses, Ann. Pure Appl. Logic 27, 253 (1984).
J. B. Remmel, Proc. Am. Math. Soc. 83, 387 (1981).
R. G. Downey, S. Lempp, and G. Wu, Journal of Mathematical Logic 10(1–2), 83 (2010).
A. N. Frolov, Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika, No. 7, 73 (2010).
P. E. Alaev, J. J. Thurber, and A. N. Frolov, Algebra i Logika 48(5), 549 (2009).
J. J. Thurber, Proc. Am. Math. Soc. 123(12), 3859 (1995).
A. N. Frolov, Journal of Logic and Computation 22(4), 745 (2010).
M. V. Zubkov, Algebra and Logic 48(5), 564 (2009).
R. G. Downey, in Handbook of Recursive Mathematics (Elsevier, Amsterdam, 1998), Vol. 2, pp. 823–976.
A. N. Frolov, Algebra and Logic 45(3), 354 (2006).
A. N. Frolov, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki 154(2), 142 (2012).
M. Moses, PhD Thesis (Monash Univ., Clayton, Australia, 1983).
R. Watnick, Journal of Symbolic Logic 49, 563 (1984).
M. J. S. Raw, PhD Thesis (University of Wisconsin-Madison, Madison, 1995).
Author information
Authors and Affiliations
Corresponding author
Additional information
Submitted by M. M. Arslanov
Rights and permissions
About this article
Cite this article
Bikmukhametov, R.I. Codings on linear orders and algorithmic independence of natural relations. Lobachevskii J Math 35, 327–332 (2014). https://doi.org/10.1134/S1995080214040131
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S1995080214040131