共查询到20条相似文献,搜索用时 15 毫秒
1.
In this paper, we will prove that the plus cupping degrees generate a definable ideal on c.e. degrees different from other
ones known so far, thus answering a question asked by Li and Yang (Proceedings of the 7th and the 8th Asian Logic Conferences.
World Scientific Press, Singapore, 2003). 相似文献
2.
S. Barry Cooper 《Mathematical Logic Quarterly》2001,47(1):3-33
A proof is given that 0 ′ (the argest Turing degree containing a computably enumerable set) is definable in the structure of the degrees of unsolvability. This answers a long‐standing question of Kleene and Post, and has a number of corollaries including the definability of the jump operator. 相似文献
3.
Ilnur I. Batyrshin 《Mathematical Logic Quarterly》2009,55(6):587-597
We show that non‐isolated from below 2‐c.e. Q ‐degrees are dense in the structure of c.e. Q ‐degrees. We construct a 2‐c.e. Q ‐degree, which can't be isolated from below not only by c.e. Q ‐degrees, but by any Q ‐degree. We also prove that below any c.e. Q ‐degree there is a 2‐c.e. Q ‐degree, which is non‐isolated from below and from above (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim) 相似文献
4.
There are noncomputable c.e. sets, computable from every c.e. set relative to which ∅′ is strongly jump-traceable. This yields a natural pseudo-jump operator, increasing on all sets, which cannot be inverted back to a minimal pair or even avoiding an upper cone. 相似文献
5.
Matthew C. Salts 《Mathematical Logic Quarterly》1999,45(1):59-72
We construct computably enumerable degrees a < b such that all computably enumerable degrees c with a < c < b isolate some d. c. e. degree d. 相似文献
6.
Jan Jakubik 《Czechoslovak Mathematical Journal》2001,51(4):889-896
In this paper we investigate the possibility of a regular embedding of a lattice ordered group into a completely distributive vector lattice. 相似文献
7.
8.
It is natural to wish to study miniaturisations of Cohen forcing suitable to sets of low arithmetic complexity. We consider extensions of the work of Schaeffer [9] and Jockusch and Posner [6] by looking at genericity notions within the Δ2 sets. Different equivalent characterisations of 1‐genericity suggest different ways in which the definition might be generalised. There are two natural ways of casting the notion of 1‐genericity: in terms of sets of strings and in terms of density functions, as we will see here. While these definitions coincide at the first level of the difference hierarchy, they turn out to differ at other levels. Furthermore, these differences remain when the remainder of the Δ02 sets are considered. While the string characterization of 1‐genericity collapses at the second level of the difference hierarchy to 2‐genericity, the density function definition gives a very interesting hierarchy at level w and above. Both of these results point towards the deep similarities exhibited by the n‐c.e. degrees for n ≥ 2. 相似文献
9.
The Major Sub-degree Problem of A. H. Lachlan (first posed in 1967) has become a long-standing open question concerning the structure of the computably
enumerable (c.e.) degrees. Its solution has important implications for Turing definability and for the ongoing programme of
fully characterising the theory of the c.e. Turing degrees. A c.e. degree a is a major subdegree of a c.e. degree b > a if for any c.e. degree x, if and only if . In this paper, we show that every c.e. degree b ≠ 0 or 0′ has a major sub-degree, answering Lachlan’s question affirmatively.
Both authors were funded by EPSRC Research Grant no. GR/M 91419, “Turing Definability”, by INTAS-RFBR Research Grant no. 97-0139,
“Computability and Models”, and by an NSFC Grand International Joint Project Grant no. 60310213, “New Directions in Theory
and Applications of Models of Computation”. Both authors are grateful to Andrew Lewis for helpful suggestions regarding presentation,
technical aspects of the proof, and verification. A. Li is partially supported by National Distinguished Young Investigator
Award no. 60325206 (People’s Republic of China). 相似文献
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.
Guohua Wu 《Mathematical Logic Quarterly》2005,51(2):111-119
Say that α is an n‐strongly c. e. (n‐strongly computably enumerable) real if α is a sum of n many strongly c. e. reals, and that α is regular if α is n‐strongly c. e. for some n. Let Sn be the set of all n‐strongly c. e. reals, Reg be the set of regular reals and CE be the set of c. e. reals. Then we have: S1 ? S2 ? · · · ? Sn ? · · · ? ? Reg ? CE . This gives a hierarchy of the c. e. reals. We also study the regularity of the d. c. e. reals. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim) 相似文献
12.
In this paper we prove that any c. e. degree is splittable with an c. e. infimum over any lesser c. e. degree in the class of d‐c. e. degrees. 相似文献
13.
明平华 《数学物理学报(A辑)》2004,24(4):491-495
该文在文[1]中幂格概念的基础上,得到了幂格的一个充要条件,给出了正则幂格、相对幂格的概念,并讨论了商格与正则幂格、相对幂格的关系.〖HT5”H〗关键词:〖HT5”SS〗格;幂格;商格;正则幂格;相对幂格. 相似文献
14.
明平华 《数学的实践与认识》2004,34(6):159-161
由幂格的定义知 ,幂格与幂集格是不同的 ,然而它们却有一定的联系 .本文在幂格概念的基础上 ,进一步地讨论幂格和幂集格在一定条件下的联系 . 相似文献
15.
There are many results on the maximum genus, among which most are written for the existence of values of such embeddings,
and few attention has been paid to the estimation of such embeddings and their applications. In this paper we study the number
of maximum genus embeddings for a graph and find an exponential lower bound for such numbers. Our results show that in general
case, a simple connected graph has exponentially many distinct maximum genus embeddings. In particular, a connected cubic
graph G of order n always has at least distinct maximum genus embeddings, where α and m denote, respectively, the number of inner vertices and odd components of an optimal tree T. What surprise us most is that such two extremal embeddings (i.e., the maximum genus embeddings and the genus embeddings)
are sometimes closely related with each other. In fact, as applications, we show that for a sufficient large natural number
n, there are at least many genus embeddings for complete graph K
n
with n ≡ 4, 7, 10 (mod12), where C is a constance depending on the value of n of residue 12. These results improve the bounds obtained by Korzhik and Voss and the methods used here are much simpler and
straight.
This work was supported by the National Natural Science Foundation of China (Grant No. 10671073), Science and Technology commission
of Shanghai Municipality (Grant No. 07XD14011) and Shanghai Leading Academic Discipline Project (Grant No. B407) 相似文献
16.
17.
Rod Downey 《Mathematical Logic Quarterly》1997,43(3):311-320
We prove that if an incomplete computably enumerable set has the the universal splitting property then it is low2. This solves a question from Ambos-Spies and Fejer [1] and Downey and Stob [7]. Some technical improvements are discussed. 相似文献
18.
Guohua Wu 《Mathematical Logic Quarterly》2001,47(4):525-534
We show the existence of a high d. c. e. degree d and a low2 c.e. degree a such that d is isolated by a . 相似文献
20.
Let Δ be a thick dual polar space of rank n ≥ 2 admitting a full polarized embedding e in a finite-dimensional projective space Σ, i.e., for every point x of Δ, e maps the set of points of Δ at non-maximal distance from x into a hyperplane e∗(x) of Σ. Using a result of Kasikova and Shult [11], we are able the show that there exists up to isomorphisms a unique full polarized embedding of Δ of minimal dimension. We also show that e∗ realizes a full polarized embedding of Δ into a subspace of the dual of Σ, and that e∗ is isomorphic to the minimal full polarized embedding of Δ. In the final section, we will determine the minimal full polarized embeddings of the finite dual polar spaces DQ(2n,q), DQ
−(2n+1,q), DH(2n−1,q
2) and DW(2n−1,q) (q odd), but the latter only for n≤ 5. We shall prove that the minimal full polarized embeddings of DQ(2n,q), DQ
−(2n+1,q) and DH(2n−1,q
2) are the `natural' ones, whereas this is not always the case for DW(2n−1, q).B. De Bruyn: Postdoctoral Fellow of the Research Foundation - Flanders. 相似文献