Degrees of enumerations of countable Wehner-like families

I. Sh. Kalimullin ; M. Kh. Faizrakhmanov

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. 59-69.

Résumé

The paper is a survey of results on countable families with natural degree spectra. These results were obtained by a modification of the methodology proposed by Wechner, who first found a family of sets with the spectrum consisting precisely of nonzero Turing degrees. Based on this method, many researchers obtained examples of families with another natural spectra. In addition, the paper extends these results presenting new examples of natural spectra. In particular, a family of finite sets with the spectrum consisting of exactly non-$K$-trivial degrees are constructed, and also we find new sufficient conditions on $\Delta^0_2$-degree $\mathbf{a}$ which guarantees that the class $\{\mathbf{x}: \mathbf{x}\not\leqslant\mathbf{a}\}$ is the degree spectrum of some family. Finally, we give a survey of our recent results on the degree spectra of $\alpha$-families, where $\alpha$ is an arbitrary computable ordinal.

Détail

Keywords: degree spectra, countable family, enumeration of family, $\alpha$-family.
Mots-clés : algebraic structure

Bibliographie

[1] Kalimullin I. Sh., “Spektry stepenei nekotorykh algebraicheskikh struktur”, Algebra i logika, 46 (2007), 729–744 | Zbl

[2] Kalimullin I. Sh., “Pochti vychislimo perechislimye semeistva mnozhestv”, Mat. sb., 199 (2008), 33–40 | DOI | Zbl

[3] Kalimullin I. Sh., Kach A., Montalban A., Puzarenko V. G., Faizrakhmanov M. Kh., “Obraschenie skachka algebraicheskikh struktur i $\Sigma$-opredelimost”, Algebra i logika, 57:2 (2018), 243–249 | MR | Zbl

[4] Kalimullin I. Sh., Faizrakhmanov M. Kh., “Ierarkhiya klassov semeistv i $n$-nizkie stepeni”, Algebra i logika, 54 (2015), 536–541 | Zbl

[5] Andrews U., Cai M. Kalimullin I., Lempp S., Miller J., Montalbán A., “The complements of lower cones of degrees and the degree spectra of structures”, J. Symb. Logic, 81 (2016), 997–1006 | DOI | MR | Zbl

[6] Ash C. J., Knight J. F., “Computable structures and the hyperarithmetical hierarchy”, Stud. Logic Found. Math., 144 (2000) | MR

[7] Carstens H. G., “$\Delta_2^0$-Mmengen”, Arch. Math. Log. Grundlag., 18 (1978), 55–65 | DOI | MR

[8] Csima B. F., Kalimullin I. S., “Degree spectra and immunity properties”, Math. Log. Q., 56 (2010), 67–77 | DOI | MR | Zbl

[9] Diamondstone D., Greenberg N., Turetsky D., “Natural large degree spectra”, Computability, 2 (2013), 1–8 | DOI | MR | Zbl

[10] Faizrahmanov M., Kalimullin I., “The enumeration spectrum hierarchy of $n$-families”, Math. Log. Q., 62 (2016), 420–426 | DOI | MR | Zbl

[11] Faizrahmanov M., Kalimullin I., “The enumeration spectrum hierarchy and low$_\alpha$ segrees”, J. Univ. Comp. Sci., 22 (2016), 943–955 | MR

[12] Goncharov S., Harizanov V., Knight J., McCoy C., Miller R., Solomon R., “Enumerations in computable structure theory”, Ann. Pure Appl. Logic, 136 (2005), 219–246 | DOI | MR | Zbl

[13] Greenberg N., Montalbán A., Slaman T., “The Slaman–Wehner theorem in higher recursion theory”, Proc. Am. Math. Soc., 139 (2011), 1865–1869 | DOI | MR | Zbl

[14] Kalimullin I. Sh., “Some notes on degree spectra of structures”, Computation and logic in the real world, Lect. Notes Comp. Sci., 4497, eds. Cooper S. B., Löwe B., Sorbi A., Springer, 2007, 389–397 | DOI | MR | Zbl

[15] Nies A., “Lowness properties and randomness”, Adv. Math., 197 (2005), 274–305 | DOI | MR | Zbl

[16] Richter L., “Degrees of structures”, J. Symb. Logic, 46 (1981), 723–731 | DOI | MR | Zbl

[17] Wehner S., “Enumerations, countable structures, and Turing degrees”, Proc. Am. Math. Soc., 126 (1998), 2131–2139 | DOI | MR | Zbl