On the definable ideal generated by the plus cupping c.e. degrees

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).     

On a Conjecture of Kleene and Post

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.     

Non‐isolated quasi‐degrees

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)     

Pseudo-jump inversion,upper cone avoidance,and strong jump-traceability

There are noncomputable c.e. sets, computable from every c.e. set relative to which ∅^′${\varnothing }^{\prime }$ 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.     

An Interval of Computably Enumerable Isolating Degrees

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.     

Complete Distributivity of Lattice Ordered Groups and of Vector Lattices

In this paper we investigate the possibility of a regular embedding of a lattice ordered group into a completely distributive vector lattice.     

On Genericity and Ershov's Hierarchy

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 Δ₂ 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 Δ⁰₂ 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.     

On Lachlan’s major sub-degree problem

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).     

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.

     

Regular reals

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 Sⁿ 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: S¹ ? S² ? · · · ? Sⁿ ? · · · ? ? 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)     

A Splitting with Infimum in the d‐c. e. Degrees

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.     

幂格与商格的关系

该文在文［1］中幂格概念的基础上,得到了幂格的一个充要条件,给出了正则幂格、相对幂格的概念,并讨论了商格与正则幂格、相对幂格的关系.〖HT5”H〗关键词:〖HT5”SS〗格;幂格;商格;正则幂格;相对幂格.     

幂格与幂集格的关系

由幂格的定义知 ,幂格与幂集格是不同的 ,然而它们却有一定的联系 .本文在幂格概念的基础上 ,进一步地讨论幂格和幂集格在一定条件下的联系 .     

Exponentially many maximum genus embeddings and genus embeddings for complete graphs

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)     

On the Universal Splitting Property

We prove that if an incomplete computably enumerable set has the the universal splitting property then it is low₂. This solves a question from Ambos-Spies and Fejer [1] and Downey and Stob [7]. Some technical improvements are discussed.     

Isolation and the Jump Operator

We show the existence of a high d. c. e. degree d and a low₂ c.e. degree a such that d is isolated by a .     

Minimal full polarized embeddings of dual polar spaces

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 ²) 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 ²) 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.