Geodesic
On ways of characterizing complete sets
Izvestiya. Mathematics , Tome 38 (1992) no. 2, pp. 225-249.

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

The traditional method for constructing criteria for completeness with respect to reducibility is by describing the property of (in general, weakened) productiveness satisfied by the complement of a set which is complete with respect to the given reducibility. Originally this property was tied to the reducibility of a creative set to the complete set. Such a method appeals directly to the universality of the creative set in the class of all recursively enumerable sets. However, for several reducibilities it is possible to determine the completeness of a recursively enumerable set from the fact that a certain set of degree below the degree of the creative sets is reducible to the given set. This second, “test” set is, of course, not recursively enumerable. In addition, in place of the property of effective nonrecursive enumerability which productive sets have, it is possible to substitute variants of the property of diagonal nonrecursiveness, although not for all reducibilities. In this paper we examine the connection between these two approaches – specifically, between different weakenings of the property of productiveness on the one hand, and diagonal nonrecursiveness on the other – and we present results obtained by these methods for Turing and truth-table reducibilities. 
@article{IM2_1992_38_2_a0,
     author = {V. K. Bulitko},
     title = {On ways of characterizing complete sets},
     journal = {Izvestiya. Mathematics },
     pages = {225--249},
     publisher = {mathdoc},
     volume = {38},
     number = {2},
     year = {1992},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IM2_1992_38_2_a0/}
}
TY  - JOUR
AU  - V. K. Bulitko
TI  - On ways of characterizing complete sets
JO  - Izvestiya. Mathematics 
PY  - 1992
SP  - 225
EP  - 249
VL  - 38
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IM2_1992_38_2_a0/
LA  - en
ID  - IM2_1992_38_2_a0
ER  - 
%0 Journal Article
%A V. K. Bulitko
%T On ways of characterizing complete sets
%J Izvestiya. Mathematics 
%D 1992
%P 225-249
%V 38
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IM2_1992_38_2_a0/
%G en
%F IM2_1992_38_2_a0
V. K. Bulitko. On ways of characterizing complete sets. Izvestiya. Mathematics , Tome 38 (1992) no. 2, pp. 225-249. http://geodesic.mathdoc.fr/item/IM2_1992_38_2_a0/

[1] Rodzhers X., Teoriya rekursivnykh funktsii i effektivnaya vychislimost, Mir, M., 1972, 624 pp. | MR

[2] Bulitko V. K., “Svodimost lineinymi po Zhegalkinu tablitsami”, Sib. matem. zhurn., 21:3 (1980), 23–31 | MR | Zbl

[3] Bulitko V. K., “Bulevy klassy tyuringovykh svedenii”, Izv. AN SSSR. Ser. matem., 49:1 (1985), 3–31 | MR

[4] Lachlan A. H., “Complete recursively enumerable sets”, Proc. Amer. Math. Soc., 19 (1966), 99–102 | DOI | MR

[5] Arslanov M. M., “O nekotorykh obobscheniyakh teoremy i nepodvizhnoi tochke”, Izv. vuzov. Matematika, 1981, no. 5, 9–16 | MR | Zbl

[6] Arslanov M. M., Lokalnaya teoriya stepenei nerazreshimosti i $\Delta^0_2$-mnozhestva, Izd-vo KGU, Kazan, 1987, 139 pp. | Zbl

[7] Shoenfield J. R., “Quasicreative sets”, Proc. Amer. Math. Soc., 8 (1957), 964–967 | DOI | MR | Zbl

[8] Eits K. E. M., “Tri teoremy o stepenyakh rekursivno perechislimykh mnozhestv”, Stepeni nerazreshimosti, Nauka, M., 1977, 97–108

[9] Gill J. T., Morris P. H., “On subcreative sets and $s$-reducibility”, J. of Symb. Logic., 39 (1974), 669–677 | DOI | MR

[10] Bulitko V. K., “O kriteriyakh polnoty dlya tyuringovykh svodimostei”, VII Vsesoyuznaya konf. po matem. logike: Tezisy dokladov, Novosibirsk, 1984, 24 pp.

[11] Bulitko V. K., “O nekotorykh formakh kriteriev polnoty mnozhestv”, VIII Vsesoyuznaya konf. po matem. logike: Tezisy dokladov, Moskva, 1986, 23 pp. | Zbl

[12] Jockusch S. G., Soare R. I., “$\Pi^0_1$-classes and degrees of theories”, Trans. of the Amer. Math. Soc., 173 (1972), 33–56 | DOI | MR | Zbl