Classes of recursively enumerable sets and Q-reducibility

Translated from Matematicheskie Zametki, Vol. 45, No. 2, pp. 79–82, February, 1989.     

Isomorphism of lattices of recursively enumerable sets

Let , and for , let be the lattice of subsets of which are recursively enumerable relative to the ``oracle' . Let be , where is the ideal of finite subsets of . It is established that for any , is effectively isomorphic to if and only if , where is the Turing jump of . A consequence is that if , then . A second consequence is that can be effectively embedded into preserving least and greatest elements if and only if .

     

Complexity properties of recursively enumerable sets andbsQ-completeness

The notions of boundedly strongly effectively speedable set and boundedly effectively speedable set are introduced. It is proved that the notions of boundedly strongly effectively speedable set, boundedly effectively speedable set, creative set, andbsQ-complete recursively enumerable set are equivalent. Translated fromMatematicheskie Zametki, Vol. 68, No. 4, pp. 554–559, October, 2000.     

Complexity properties of recursively enumerable sets andsQ-completeness

The notions of effectively subcreative set and strongly effectively acceleratable set are introduced. It is proved that the notions of effectively subcreative set, strongly effectively acceleratable set, andsQ-complete recursively enumerable set are equivalent. Translated fromMatematicheskie Zametki, Vol. 62, No. 3, pp. 425–429, September, 1997. Translated by V. N. Dubrovsky     

Truth tabular degrees of recursively enumerable sets

The upper semilattice of truth tabular degrees of recursively enumerable (r.e.) sets is studied. It is shown that there exists an infinite set of pairwise tabularly incomparable truth tabular degrees higher than any tabularly incomplete r.e. truth tabular degree. A similar assertion holds also for r.e. m-degrees. Hence follows that a complete truth tabular degree contains an infinite antichain of r.e. m-degrees.Translated from Matematicheskie Zametki, Vol. 14, No. 5, pp. 697–702, November, 1973.     

Some reducibilities and splittings of recursively enumerable sets

The existence of a recursively enumerable (RE)T-degreea that does not contain an RE semirecursive setA ∈a with theQ-universal splitting property is proved. Each nonrecursive RE contiguous degree contains an RE setA with the universalT-Q-reduction property, butA is notT-Q-maximal. Each nonrecursive REW-degree contains an RE setA with the universalW-sQ-reduction property, butA is notW-sQ-maximal. Each creative set is partially semimaximal. Translated fromMatematicheskie Zametki, Vol. 66, No. 2, pp. 220–230, August, 1999.