Linear orderings. Coding theorems

A. N. Frolov

Učënye zapiski Kazanskogo universiteta. Seriâ Fiziko-matematičeskie nauki, Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, Tome 154 (2012) no. 2, pp. 142-151

Résumé

In this paper, we consider $\mathbf0'$- and $\mathbf0''$-coding theorems. We obtain two general theorems which generalize all $\mathbf0'$- and $\mathbf0''$-coding theorems known at this moment. Using one $\mathbf0'$-coding theorem, we describe ranges of $\eta$-functions of $\eta$-like linear orderings with no computable representations.

Détail

Keywords: linear orderings, computable representations, coding theorems.

Bibliographie

[1] Ash C. J., Knight J., Computable structures and the hyperarithmetical hierarchy, North-Holland Pub. Co., Amsterdam, 2000, XVI+346 pp. | MR

[2] Downey R. G., “Computability theory and linear orders”, Handbook of Recursive Mathematics, v. 1, eds. Ershov Yu. L., Goncharov S. S., Nerode A., Remmel J. B., Elsevier, 1988, 823–976 | MR

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

[4] Downey R. G., Knight J. F., “Orderings with $\alpha$-th jump degree $\mathbf 0^{(\alpha)}$”, Proc. Amer. Math. Soc., 114:2 (1992), 545–552 | MR | Zbl

[5] Downey R. G., Moses M. F., “On choice sets and strongly nontrivial self-embeddings of recursive linear orderings”, Zeitschr. f. Math. Logik und Grundlagen d. Math., 35:3 (1989), 237–246 | DOI | MR | Zbl

[6] Feiner L. J., Orderings and Boolean Algebras not isomorphic to recursive ones, Ph D Thesis, MIT, Cambridge, MA, 1967, 89 pp. URL http://dspace.mit.edu/bitstream/handle/1721.1/60738/29976019.pdf?sequence=1 | MR

[7] Feiner L. J., “The strong homogeneity conjecture”, J. Symb. Logic, 35:3 (1970), 373–377 | MR

[8] Fellner S., Recursive and finite axiomatizability of linear orderings, Ph D Thesis, Rutgers Univ., New Brundswick, N.J., 1976 | MR

[9] Frolov A., Zubkov M., “Increasing $\eta$-representable degrees”, Math. Log. Quart., 55:6 (2009), 633–636 | DOI | MR | Zbl

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

[11] Lerman M., Rosenstein J. R., “Recursive linear orderings”, Patras Logic Symposion, Proc. (Patras, Greece, Aug. 18–22, 1980), Stud. Logic Found. Math., 109, 1982, 123–136 | DOI | MR | Zbl

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

[13] Montalban A., “Notes on the jump of a structure”, Mathematical Theory and Computational Practice, Springer-Verlag, Berlin–Heidelberg, 2009, 372–378 | DOI | MR | Zbl

[14] Rosenstein J. R., Linear orderings, Pure and Applied Mathematics, 98, Acad. Press Inc., Hartcourt Brace Jovanovich Publ., N.Y.–London, 1982, 487 pp. | MR | Zbl

[15] Watnik R., “A generalization of Tennenbaum's Theorem on effectively finite recursive linear orderings”, J. Symb. Logic, 49:2 (1984), 563–569 | DOI | MR

[16] Soar R. I., Vychislimo perechislimye mnozhestva i stepeni, Kazan. matem. o-vo, Kazan, 2000, 576 pp. | MR | Zbl

[17] Alaev P., Tërber Dzh., Frolov A., “Vychislimost na lineinykh poryadkakh, obogaschënnykh predikatami”, Algebra i logika, 48:5 (2009), 549–563 | MR | Zbl

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

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

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