共查询到20条相似文献,搜索用时 31 毫秒
1.
R. Sh. Omanadze 《Mathematical Notes》1997,62(3):356-359
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 相似文献
2.
R. Sh. Omanadze 《Mathematical Notes》1999,66(2):174-180
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. 相似文献
3.
Todd Hammond 《Transactions of the American Mathematical Society》1997,349(7):2699-2719
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 .
4.
V. K. Bulitko 《Mathematical Notes》1998,64(1):8-14
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. 相似文献
5.
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 Zn. 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. 相似文献
6.
Yu. D. Korol'kov 《Algebra and Logic》2002,41(2):87-92
The complexity of index sets of families of general recursive functions is evaluated in the Kleene–Mostowski arithmetic hierarchy. 相似文献
7.
8.
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) 相似文献
9.
Martin Kummer 《Transactions of the American Mathematical Society》2006,358(1):59-86
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.
10.
Steffen Lempp André Nies Theodore A. Slaman 《Transactions of the American Mathematical Society》1998,350(7):2719-2736
We show the undecidability of the -theory of the partial order of computably enumerable Turing degrees.
11.
We construct a nonlow2 r.e. degree d such that every positive extension of embeddings property that holds below every low2 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. 相似文献
12.
Farzad Didehvar 《Mathematical Logic Quarterly》1999,45(4):467-470
We define a class of so-called ∑(n)-sets as a natural closure of recursively enumerable sets Wn under the relation “∈” and study its properties. 相似文献
13.
V. D. Solov'ev 《Mathematical Notes》1997,61(6):793-795
14.
S. A. Shkarin 《Mathematical Notes》2000,67(4):534-540
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. 相似文献
15.
V. Yu. Popov 《Mathematical Notes》2000,67(4):495-504
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. 相似文献
16.
Shahram Mohsenipour 《Mathematical Logic Quarterly》2007,53(3):289-294
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) 相似文献
17.
V. L. Selivanov 《Algebra and Logic》2004,43(1):44-61
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. 相似文献
18.
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. 相似文献
19.
20.
Patrizio Cintioli 《Mathematical Logic Quarterly》2011,57(5):517-523
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 low1 m‐introimmune set in Π01 and the existence of a low1 bi‐m‐introimmune set. 相似文献