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     

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.     

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 .

     

Recursively compressible sets

Classes of recursively compressible and incompressible sets as well as some other classes emerging in connection with a simple recursive-theory model of data array packing are studied. Some new completeness criteria for sets are obtained.Translated fromMatematicheskie Zametki, Vol. 64, No. 1, pp. 9–16, July, 1998.     

Recursively enumerable sets of polynomials over a finite field

We prove that a relation over is recursively enumerable if and only if it is Diophantine over . We do this by first constructing a model of in , where n is represented by Zⁿ. In a second step, we show that it suffices to eliminate a bounded universal quantifier. Then finally, the hardest part of the proof is to show that we can eliminate this quantifier.     

Evaluating the Complexity of Index Sets for Families of General Recursive Functions in the Arithmetic Hierarchy

The complexity of index sets of families of general recursive functions is evaluated in the Kleene–Mostowski arithmetic hierarchy.     

On existence of complete sets for bounded reducibilities

Classical reducibilities have complete sets U that any recursively enumerable set can be reduced to U. This paper investigates existence of complete sets for reducibilities with limited oracle access. Three characteristics of classical complete sets are selected and a natural hierarchy of the bounds on oracle access is built. As the bounds become stricter, complete sets lose certain characteristics and eventually vanish. (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

The complexity of recursion theoretic games

We show that some natural games introduced by Lachlan in 1970 as a model of recursion theoretic constructions are undecidable, contrary to what was previously conjectured. Several consequences are pointed out; for instance, the set of all -sentences that are uniformly valid in the lattice of recursively enumerable sets is undecidable. Furthermore we show that these games are equivalent to natural subclasses of effectively presented Borel games.

     

The -theory of the computably enumerable Turing degrees is undecidable

We show the undecidability of the -theory of the partial order of computably enumerable Turing degrees.

     

A nonlow2 R. E. Degree with the Extension of Embeddings Properties of a low2 Degree

We construct a nonlow₂ r.e. degree d such that every positive extension of embeddings property that holds below every low₂ degree holds below d . Indeed, we can also guarantee the converse so that there is a low r.e. degree c such that that the extension of embeddings properties true below c are exactly the ones true belowd.Moreover, we can also guarantee that no b ≤ d is the base of a nonsplitting pair.     

On a Class of Recursively Enumerable Sets

We define a class of so-called ∑(n)-sets as a natural closure of recursively enumerable sets W_n under the relation “∈” and study its properties.     

On effective linearly ordered sets of comparison functions

Both the existence and the nonexistence of a linearly ordered (by certain natural order relations) effective set of comparison functions (=dense comparison class) are compatible with the ZFC axioms of set theory. Translated fromMaternaticheskie Zametki, Vol. 67, No. 4, pp. 629–637, April, 2000.     

Undecidability of the word problem in relatively free rings

An example of a series of varieties of rings with the finite basis property is constructed for which the word problem in the relatively free ring of rankn in the variety is decidable if and only ifn <p. Translated fromMatematicheskie Zametki, Vol. 67, No. 4, pp. 582–594, April, 2000.     

A generalization of the Keisler‐Morley theorem to recursively saturated ordered structures

We prove a model theoretic generalization of an extension of the Keisler‐Morley theorem for countable recursively saturated models of theories having a κ ‐like model, where κ is an inaccessible cardinal. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Boolean Hierarchies of Partitions over a Reducible Base

The Boolean hierarchy of partitions was introduced and studied by Kosub and Wagner, primarily over the lattice of NP-sets. Here, this hierarchy is treated over lattices with the reduction property, showing that it has a much simpler structure in this instance. A complete characterization is given for the hierarchy over some important lattices, in particular, over the lattices of recursively enumerable sets and of open sets in the Baire space.     

Isomorphism of the Index Sets of Discrete Families of General Recursive Functions

We establish isomorphism between the index set of an arbitrary computable family of general recursive functions and the index set of a certain computable discrete family of general recursive functions.     

Low sets without subsets of higher many‐one degree

Given a reducibility ?_r, we say that an infinite set A is r‐introimmune if A is not r‐reducible to any of its subsets B with |A\B| = ∞. We consider the many‐one reducibility ?_m and we prove the existence of a low₁ m‐introimmune set in Π⁰₁ and the existence of a low₁ bi‐m‐introimmune set.