Isolation: motivations and applications

G. Wu   ; M. M. Yamaleev

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

Résumé

In this paper, we briefly review the origins of the isolation phenomenon and its applications. We discuss a stronger notion of double bubbles. We also show recent achievements in the study of lattice embeddings with the help of the isolation property.

Détail

Keywords: Turing degrees, Ershov hierarchy, isolated degrees, lattice embeddings.

Bibliographie

[1] Cooper S. B., Yi X., Isolated d. r. e. degrees, Preprint series, No 17, University of Leeds, Dept. of Pure Math., 1995, 25 pp.

[2] LaForte G., “Isolation in the $CEA$ hierarchy”, Arch. Math. Logic, 44:2 (2005), 227–244 | DOI | MR | Zbl

[3] Arslanov M., Kalimullin I., Lempp S., “On Downey's conjecture”, J. Symbolic Logic, 75:2 (2010), 401–441 | DOI | MR | Zbl

[4] Cai M., Shore R. A., Slaman T. A., “The $n$-r. e. degrees: undecidability and $\Sigma_1$ substructures”, J. Math. Logic, 12:1 (2012), 1250005-1–1250005-30 | DOI | MR | Zbl

[5] Wu G., Structural Properties of d. c. e. degrees and presentations of c. e. reals, Ph D Thesis, Victoria University of Wellington, Wellington, 2002

[6] Fang C., Liu J., Wu G., “Cupping and diamond embeddings: a unifying approach”, Lecture Notes in Computer Science, 6735, 2011, 71–80 | DOI | MR | Zbl

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

[8] Cooper S. B., “Local degree theory”, Handbook of Computability Theory, Studies in Logic and the Foundations of Mathematics, 140, ed. E. R. Griffor, North-Holland, Amsterdam, 1999, 121–153 | DOI | MR

[9] Arslanov M., “Open questions about the $n$-c. e. degrees”, Computability Theory and Its Applications: Current Trends and Open Problems, Proc. 1999 AMS-IMS-SIAM Joint Summer Res. Conf., Contemporary Mathematics, 257, eds. M. Lerman, P. A. Cholak, S. Lempp, R. A. Shore, Amer. Math. Soc., Providence, RI, 2000, 15–22 | DOI | MR | Zbl

[10] Cooper S. B., Degrees of Unsolvability, Ph D Thesis, University of Leicester, Leicester, 1971

[11] Cooper S. B., Harrington L., Lachlan A. H., Lempp S., Soare R. I., “The d. r. e. degrees are not dense”, Ann. Pure Appl. Logic, 55:2 (1991), 125–151 | DOI | MR | Zbl

[12] Arslanov M., “Structural properties of the degrees below $0'$”, Dokl. Acad. Nauk SSSR, 283:2 (1985), 270–273 | MR | Zbl

[13] Downey R., “D. r. e. degrees and the nondiamond theorem”, Bull. London Math. Soc., 21 (1989), 43–50 | DOI | MR | Zbl

[14] Ishmukhametov Sh., D. r. e. sets, their degrees and index sets, Ph D Thesis, Novosibirsk, 1986

[15] Kaddah D., “Infima in the d. r. e. degrees”, Ann. Pure Appl. Logic, 62 (1993), 207–263 | DOI | MR | Zbl

[16] Ding D., Qian L., “Isolated d. r. e. degrees are dense in r. e. degree structure”, Arch. Math. Logic, 36:1 (1996), 1–10 | DOI | MR | Zbl

[17] LaForte G., “The isolated d. r. e. degrees are dense in the r. e. degrees”, Math. Logic Quart., 42 (1996), 83–103 | DOI | MR | Zbl

[18] Arslanov M. M., Lempp S., Shore R. A., “On isolating r. e. and isolated d-r. e. degrees”, Computability, enumerability, unsolvability, London Mathematical Society, Lecture Note Series, 224, eds. S. B. Cooper, T. A. Slaman, S. S. Wainer, Cambridge Univ. Press, Cambridge, 1996, 61–80 | MR | Zbl

[19] Ishmukhametov Sh., Wu G., “Isolation and the high/low hierarchy”, Arch. Math. Logic, 41:3 (2002), 259–266 | DOI | MR | Zbl

[20] Li A., Wu G., Yang Y., “Bounding computably enumerable degrees in the Ershov hierarchy”, Ann. Pure Appl. Logic, 141:1–2 (2006), 79–88 | MR | Zbl

[21] Cooper S. B., “Minimal pairs and high recursively enumerable degrees”, J. Symbolic Logic, 39:4 (1974), 655–660 | DOI | MR

[22] Chong C. T., Li A., Yang Y., “The existence of high nonbounding degrees in the difference hierarchy”, Ann. Pure Appl. Logic, 138:1–3 (2006), 31–51 | DOI | MR | Zbl

[23] Cooper S. B., Salts M. C., Wu G., “The non-isolating degrees are upwards dense in the computably enumerable degrees”, Theory and Applications of Models of Computation, Proc. 5th Int. Conf. TAMC 2008, Lecture Notes in Computer Science, 4978, Springer-Verlag, Berlin–Heidelberg, 2008, 588–596 | DOI | MR | Zbl

[24] Salts M., “An interval of computably enumerable isolating degrees”, Math. Logic Quart., 45 (1999), 59–72 | DOI | MR | Zbl

[25] Lachlan A. H., “Lower bounds for pairs of recursively enumerable degrees”, Proc. London Math. Soc., 16 (1966), 537–569 | DOI | MR | Zbl

[26] Yang Y., Yu L., “On $\Sigma_1$-structural differences among finite levels of the Ershov hierarchy”, J. Symbolic Logic, 71:4 (2006), 1223–1236 | DOI | MR | Zbl

[27] Wu G., “On the density of the pseudo-isolated degrees”, Proc. London Math. Soc., 88:2 (2004), 273–288 | DOI | MR | Zbl

[28] Ishmukhametov Sh., “On the r. e. predecessors of d. r. e. degrees”, Arch. Math. Logic, 38:6 (1999), 373–386 | DOI | MR | Zbl

[29] Wu G., “Isolation and lattice embeddings”, J. Symbolic Logic, 67:3 (2002), 1055–1064 | DOI | MR | Zbl

[30] Liu J., Wu G., “An almost-universal cupping degree”, J. Symbolic Logic, 76:4 (2011), 1137–1152 | DOI | MR | Zbl

[31] Cooper S. B., Li A., “Splitting and cone avoidance in the d. c. e. degrees”, Sci. China Ser. A, 45:9 (2002), 1135–1146 | MR | Zbl

[32] Yamaleev M. M., “Splitting in 2-computably enumerable degrees with avoiding cones”, Russian Mathematics (Izv. Vuz. Mat.), 53:6 (2009), 63–66 | DOI | MR | Zbl

[33] Arslanov M., LaForte G., Slaman T., “Relative enumerability in the difference hierarchy”, J. Symbolic Logic, 63:2 (1998), 411–420 | DOI | MR | Zbl

[34] Li A., Song Y., Wu G., “Universal cupping degrees”, Theory and Applications of Models of Computation, Proc. 3rd Int. Conf. TAMC 2006, Lecture Notes in Computer Science, 3959, Springer-Verlag, Berlin–Heidelberg, 2006, 721–730 | DOI | MR | Zbl

[35] Downey R. G., Li A., Wu G., “Complementing cappable degrees in the difference hierarchy”, Ann. Pure Appl. Logic, 125:1–3 (2004), 101–118 | DOI | MR | Zbl