Geodesic
Computable linear orders and limitwise monotonic functions
Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory, Proceedings of the Seminar on Algebra and Mathematical Logic of the Kazan (Volga Region) Federal University, Tome 157 (2018), pp. 70-105.

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper, we describe the technique of extremely monotonic functions in the theory of computable linear orders. The main definitions of extremely monotonic functions and their generalizations are given, as well as a number of their basic properties and applications.
Keywords: computable linear orders, limitwise monotonic functions, effective presentations, low degrees, self-embeddings, automorphisms. 
@article{INTO_2018_157_a4,
     author = {M. V. Zubkov and A. N. Frolov},
     title = {Computable linear orders and limitwise monotonic functions},
     journal = {Itogi nauki i tehniki. Sovremenna\^a matematika i e\"e prilo\v{z}eni\^a. Temati\v{c}eskie obzory},
     pages = {70--105},
     publisher = {mathdoc},
     volume = {157},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/INTO_2018_157_a4/}
}
TY  - JOUR
AU  - M. V. Zubkov
AU  - A. N. Frolov
TI  - Computable linear orders and limitwise monotonic functions
JO  - Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory
PY  - 2018
SP  - 70
EP  - 105
VL  - 157
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/INTO_2018_157_a4/
LA  - ru
ID  - INTO_2018_157_a4
ER  - 
%0 Journal Article
%A M. V. Zubkov
%A A. N. Frolov
%T Computable linear orders and limitwise monotonic functions
%J Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory
%D 2018
%P 70-105
%V 157
%I mathdoc
%U http://geodesic.mathdoc.fr/item/INTO_2018_157_a4/
%G ru
%F INTO_2018_157_a4
M. V. Zubkov; A. N. Frolov. Computable linear orders and limitwise monotonic functions. Itogi nauki i tehniki. Sovremennaâ matematika i eë priloženiâ. Tematičeskie obzory, Proceedings of the Seminar on Algebra and Mathematical Logic of the Kazan (Volga Region) Federal University, Tome 157 (2018), pp. 70-105. http://geodesic.mathdoc.fr/item/INTO_2018_157_a4/

[1] Alaev P. E., Terber Dzh., Frolov A. N., “Vychislimost na lineinykh poryadkakh, obogaschennykh predikatami”, Algebra i logika, 48:5 (2009), 549–563 | MR | Zbl

[2] Arslanov M. M., Ierarkhiya Ershova, Kazan. gos. un-t, Kazan, 2007

[3] Zubkov M. V., “Dostatochnye usloviya suschestvovaniya $\boldsymbol{0}'$-predelno monotonnykh funktsii dlya vychislimykh $\eta$-skhozhikh lineinykh poryadkov”, Sib. mat. zh., 58:1 (2017), 107–121 | MR | Zbl

[4] Zubkov M. V., Vychislimye lineinye poryadki i $\eta$-predstavimost, Diss. na soisk. uch. step. kand. fiz.-mat. nauk, Kazan. gos. un-t, Kazan, 2009

[5] Zubkov M. V., “Silno $\eta$-predstavimye stepeni i predelno monotonnye funktsii”, Algebra i logika, 50:4 (2011), 504–520 | MR | Zbl

[6] Zubkov M. V., “Odna teorema o silno $\eta$-predstavimykh mnozhestvakh”, Izv. vuzov. Mat., 2009, no. 7, 77–81 | Zbl

[7] Zubkov M. V., “O nachalnykh segmentakh vychislimykh lineinykh poryadkov s dopolnitelnymi vychislimymi predikatami”, Algebra i logika, 48:5 (2009), 564-579 | MR | Zbl

[8] Rodzhers Kh., Teoriya rekursivnykh funktsii i effektivnaya vychislimost, Mir, M., 1972

[9] Frolov A. N., “Vychislimaya predstavimost schetnykh lineinykh poryadkov”, Itogi nauki i tekhn., Temat. obzory, Sovr. mat. prilozheniya, 158, 2018

[10] Frolov A. N., “$\Delta_2^0$-Kopii lineinykh poryadkov”, Algebra i logika, 45:3 (2006), 354–370 | MR | Zbl

[11] Frolov A. N., “Lineinye poryadki nizkoi stepeni”, Sib. mat. zh., 51:5 (2010), 1147–1162 | MR | Zbl

[12] Frolov A. N., “Predstavleniya otnosheniya sosedstva vychislimogo lineinogo poryadka”, Izv. vuzov. Mat., 2010, no. 7, 73–85 | Zbl

[13] Frolov A. N., “Problemy Rozenshteina”, Tr. Mezhdunar. nauch. konf. «Vychislimost i modeli» (30 avgusta–1 sentyabrya 2009, Ust-Kamenogorsk, VKGTU), 2010, 103–114

[14] Frolov A. N., “Rangi $\eta$-funktsii $\eta$-skhozhikh lineinykh poryadkov”, Izv. vuzov. Mat., 2012, no. 3, 96–99 | Zbl

[15] Khisamiev N. G., “Kriterii konstruktiviziruemosti pryamoi summy tsiklicheskikh $p$-grupp”, Izv. AN Kaz. SSR. Ser. fiz.-mat., 98:1 (1981), 51–55

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

[17] Church A., “The constructive second order number class”, Bull. Am. Math. Soc., 44 (1938), 224–232 | DOI | MR

[18] Church A., Kleene S. C., “Formal definitions in the theory of ordinal numbers”, Fund. Math., 28 (1937), 224–232

[19] Coles R. J., Downey R., Khoussainov B., “On initial segments of computable linear orders”, Order, 14 (1997/98), 107–124 | DOI | MR

[20] Downey R. G., “Computability Theory and Linear Orderings”, Handbook of Recursive Mathematics, v. 2, Stud. Logic Found. Math., 139, eds. Ershov Yu. L., Goncharov S. S., Nerode A., Remmel J. B., Elsevier, Amsterdam, 1998, 823–976 | DOI | MR | Zbl

[21] Downey R. G., Jockusch C. G., “Every low Boolean algebra is isomorphic to a recursive one”, Proc. Am. Math. Soc., 122:3 (1994), 871–880 | DOI | MR | Zbl

[22] Downey R. G., Kach A. M., Turetsky D., “Limitwise monotonic functions and their applications”, Proc. 11 Asian Logic Conf (2012), 59–85 | MR | Zbl

[23] Downey R. G., Kastermans B., Lempp S., “On computable self-embeddings of computable linear orderings”, J. Symb. Logic, 74:4 (2009), 1352–1366 | DOI | MR | Zbl

[24] Downey R., Lempp S., Wu G., “On the complexity of the successivity relation in computable linear orderings”, J. Math. Logic, 83:10 (2010), 83–99 | DOI | MR | Zbl

[25] Downey R., Lempp S., Wu G., “Corrigendum: “On the complexity of the successivity relation in computable linear orderings””, J. Math. Logic, 17:2 (2017), 1792002-1–1792002-4 | DOI | MR | Zbl

[26] Downey R. G., Moses M. F., “On choice sets and strongly nontrivial self-embeddings of recursive linear orders”, Math. Logic Q., 35 (1989), 237–246 | DOI | MR | Zbl

[27] Downey R., Moses M., “Recursive linear orders with incomplete successivities”, Trans. Am. Math. Soc., 326 (1991), 653–668 | DOI | MR | Zbl

[28] Dushnik B., Miller E. W., “Partially ordered sets”, Am. J. Math., 63 (1941), 600–610 | DOI | MR

[29] Feiner L. J., “Hierarchies of Boolean algebras”, J. Symb. Logic, 35 (1970), 365–374 | DOI | MR

[30] Fellner S., Recursive and finite axiomatizability of linear orderings, Ph.D. thesis, Rutgers Univ., New Brunswick–New Jersey, 1976 | MR

[31] Frolov A. N., “Low linear orderings”, J. Log. Comp., 22:4 (2012), 745–754 | DOI | MR | Zbl

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

[33] Frolov A. N., Zubkov M. V., “Increasing $\eta$-representable degrees”, Math. Logic Q., 55 (2009), 633–636 | DOI | MR | Zbl

[34] Frolov A. N. Zubkov M. V., “Limitwise monotonic functions relative to the Kleene's ordinal notation system”, Lobachevskii J. Math., 35 (2014), 295–301 | DOI | MR | Zbl

[35] Harizanov V., Degree spectrum of a recursive relation on a recursive structure, Ph.D. thesis, Univ. of Wisconsin, Madison, 1987 | MR

[36] Harris K., “$\eta$-Representation of sets and degrees”, J. Symb. Logic, 73 (2018), 1097–1121 | DOI | MR

[37] Harris C. M., Lee K. I., Cooper S. B., “Automorphisms of $\eta$-like computable linear orderings and Kierstead's conjecture”, Math. Logic Q., 62:6 (2016), 481–506 | DOI | MR | Zbl

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

[39] Jockusch C. G., Soare R. I., “Degrees of orderings not isomorphic to recursive linear orderings”, Ann. Pure Appl. Logic, 52 (1991), 39–61 | DOI | MR

[40] Kach A. M., “Computable shuffle sums of ordinals”, Arch. Math. Logic., 47:3 (2008), 211–219 | DOI | MR | Zbl

[41] Kach A., Montalbán A., “Cuts of linear orders”, Order, 28 (2011), 593–600 | DOI | MR | Zbl

[42] Kach A. M., Turetsky D., “Limitwise monotonic fuctions, sets and degrees on computable domains”, J. Symb. Logic, 75 (2010), 131–154 | DOI | MR | Zbl

[43] Kierstead H. A., “On $\Pi^0_1$-automorphisms of recursive linear orders”, J. Symb. Logic, 52 (1987), 681–688 | MR | Zbl

[44] Khisamiev N. G., “Constructive abelian groups”, Handbook of Recursive Mathematics, v. 2, Stud. Logic Found. Math., 139, eds. Ershov Yu. L., Goncharov S. S., Nerode A., Remmel J. B., Elsevier, Amsterdam, 1998, 1177–1231 | DOI | MR | Zbl

[45] Kleene S. C., “On notation for ordinal numbers”, J. Symb. Logic, 3 (1938), 150–155 | DOI

[46] Lerman M., “On recursive linear orderings”, Lect. Notes Math., 859 (1981), 132–142 | DOI | MR | Zbl

[47] Lerman M., Rosenstein J. R., “Recursive linear orderings”, Stud. Logic Found. Math., Proc. Logic Symp. (Patras, Greece, August 18-22, 1980), v. 109, ed. G. Metakides, 1982, 123–136 | DOI | MR | Zbl

[48] Moses M., “The block relation in computable linear orders”, Notre Dame J. Formal Logic, 52:3 (2011), 289–305 | DOI | MR | Zbl

[49] Ng K. M., Zubkov M., “On Kierstead's conjecture”, Trans. Am. Math. Soc., 372:5 (2019), 3713–3753 | DOI | MR | Zbl

[50] Rosenstein J. G., Linear orderings, Academic Press, New York–London, 1982 | MR | Zbl

[51] Rosenstein J. G., “Recursive linear orderings”, Ann. Discr. Math., 23 (1984), 465–475 | MR | Zbl

[52] Schwarz S. T., Quotient lattices, index sets, and recursive linear orderings, Ph.D. thesis, Univ. of Chicago, 1982 | MR | Zbl

[53] Schwarz S. T., “Recursive automorphisms of recursive linear orderings”, Ann. Pure Appl. Logic, 26 (1984), 69–73 | DOI | MR | Zbl

[54] Soare R. I., Recursively enumerable sets and degrees, Springer-Verlag, Heidelberg, 1987 | MR

[55] Wu G., Zubkov M., “The Kierstead's conjecture and limitwise monotonic functions”, Ann. Pure Appl. Logic, 169:6 (2018), 467–486 | DOI | MR | Zbl

[56] Zubkov M., “On $\eta$-representable sets”, Bull. Symb. Logic, 15 (2009), 292–293