Degree spectra of the block relation of $1$-computable linear orders

R. I. Bikmukhametov ; M. S. Eryashkin ; A. N. Frolov

Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 159 (2017) no. 3, pp. 296-305

Résumé

In this paper, we study the intrinsically computably enumerable relations on linear orderings, such as the successor relation on computable linear orderings and the block relation on $1$-computable linear orderings. For ease of reading, the linear ordering , in which the signature is enriched with the successor relation, is called $1$-computable linear ordering. This notion is consistent with the known results. We have proved that for any $\mathbf0'$-computable linear ordering $L$ there exists a $1$-computable linear ordering, in which the degree spectrum of the block relation coincides with the $\Sigma_1^0$-spectrum of the linear ordering $L$. The degree spectrum of the block relation of a linear ordering $R$ is called the class of Turing degrees of the images of the block relation on computable presentations of $R$; and $\Sigma_1^0$-spectrum of a linear ordering $L$ is called the class of Turing enumerable degrees of $L$. This obtained result provides a number of examples of the spectra of the block relation of $1$-computable linear orderings. In particular, the class of all enumerable high$_n$ degrees and the class of all enumerable non-low$_n$ degrees are realized by the spectra of the block relation of some $1$-computable linear orderings.

Détail

Keywords: linear orders, $1$-computability, block relation, successivity relation, intrinsically computably enumerable relations.
Mots-clés : spectra of relations

Bibliographie

[1] Ash C. J., Nerode A., “Intrinsically recursive relations”, Aspects of Effective Algebra, ed. Crossley J. N., U.D.A. Book Co., Steel's Greek, Australia, 1981, 26–41 | MR

[2] Hirschfeldt D. R., “Degree spectra of intrinsically c.e. relations”, J. Symb. Logic, 66:2 (2001), 441–469 | DOI | MR

[3] Frolov A. N., “Linear orderings of low degrees”, Sib. Math. J., 51:5 (2010), 913–925 | DOI | MR

[4] Montalban A., “Notes on the jump of a structure”, Mathematical Theory and Computational Practice, 5th Conf. on Computability in Europe (CiE 2009), Lecture Notes in Computer Science, 5635, eds. K. Ambos-Spies, B. Löwe, W. Merkle, Springer-Verlag, Berlin, 2009, 372–378 | DOI | MR

[5] Remmel J. B., “Recursively categorical linear orderings”, Proc. Am. Math. Soc., 83:2 (1981), 387–391 | DOI | MR

[6] Moses M., “Relations intrinsically recursive in linear orders”, Z. Math. Logik Grundlag. Math., 32 (1986), 467–472 | DOI | MR

[7] Hirschfeldt D. R., “Degree spectra of relations on computable structures in the presence of $\Delta^0_2$ isomorphisms”, J. Symb. Logic, 67:2 (2002), 697–720 | DOI | MR

[8] Frolov A. N., “Presentations of the successor relation of computable linear orderings”, Russ. Math., 2010, no. 7, 64–74 | DOI | MR

[9] Chubb J., Frolov A., Harizanov V., “Degree spectra of successivities of linear orderings”, Arch. Math. Logic, 48:1 (2009), 7–13 | DOI | MR

[10] Harizanov V., Degree spectrum of a recursive relation on a recursive structure, Ph. D. Thesis, University of Wisconsin, Madison, USA, 1987, 170 pp. | MR

[11] Moses M., “Recursive linear orders with recursive successivities”, Ann. Pure Appl. Logic, 27:3 (1984), 253–264 | DOI | MR

[12] Frolov A. N., “Low linear orderings”, J. Logic Comput., 22:4 (2012), 745–754 | DOI | MR

[13] Alaev P. E., Frolov A. N., Thurber J., “Computability on linear orderings enriched with predicates”, Algebra Logic, 48:5 (2009), 313–320 | DOI | MR | Zbl

[14] Frolov A. N., “Scattered linear orderings with no computable presentation”, Lobachevskii J. Math., 35:1 (2014), 19–22 | DOI | MR

[15] Zubkov M. V., “Initial segments of computable linear orders with additional computable predicates”, Algebra Logic, 48:5 (2009), 321–329 | DOI | MR | Zbl

[16] Turner W. P., Computable linear orders and Turing reductions, Master's Thesis, University of Connecticut, 2012

[17] Bikmukhametov R. I., “Initial segments of computable linear orders with computable natural relations”, Russ. Math., 60:6 (2016), 12–20 | DOI | MR

[18] Bikmukhametov R. I., “$\Sigma^0_2$-initial segments of computable linear orders”, Algebra Logic, 53:3 (2014), 266–267 | DOI | MR

[19] Bikmukhametov R. I., “Codings on linear orders and algorithmic independence of natural relations”, Lobachevskii J. Math., 35:4 (2014), 326–331 | DOI | MR

[20] Bikmukhametov R. I., “Algorithmic independence of natural relations on computable linear orders”, Uchenye Zapiski Kazanskogo Universiteta, Seriya Fiziko-Matematicheskie Nauki, 155, no. 3, 2013, 80–90 (In Russian) | MR

[21] Miller R., “The $\Delta_2^0$ spectrum of a linear ordering”, J. Symb. Logic, 66 (2001), 470–486 | DOI | MR

[22] Frolov A. N., “$\Delta_2^0$-copies of linear orderings”, Algebra logic, 45:3 (2006), 201–209 | DOI | MR | Zbl

[23] Frolov A. N., “A note on $\Delta^0_2$-spectra of linear orderings and degree spectra of the successor relation”, Russ. Math., 57:11 (2013), 65–68 | DOI | MR

[24] Frolov A., Harizanov V., Kalimullin I., Kudinov O., Miller R., “Spectra of high$_n$ and non-low$_n$ degrees”, J. Logic Comput., 22:4 (2012), 745–754 | DOI | MR