The low<Subscript><Emphasis Type="Italic">n</Emphasis></Subscript> and low<Subscript><Emphasis Type="Italic">m</Emphasis></Subscript> r. e. degrees are not elementarily equivalent

Jockusch, Li and Yang showed that the Lown and Low1 r.e. degrees are not elementarily equivalent for n > 1. We answer a question they raise by using the results of Nies, Shore and Slaman to show that the Lown and Lowm r.e. degrees are not elementarily equivalent for n > m > 1.     

Discontinuity of Cappings in the Recursively Enumerable Degrees and Strongly Nonbranching Degrees

We construct an r. e. degree a which possesses a greatest a-minimal pair b₀, b₁, i.e., r. e. degrees b₀ and b₁ such that b₀, b₁ < a, b₀ ∩ b₁ = a, and, for any other pair c₀, c₁ with these properties, c₀ ≤ b_i and c₁ ≤ b_1-i for some i ≤ 1. By extending this result, we show that there are strongly nonbranching degrees which are not strongly noncappable. Finally, by introducing a new genericity concept for r. e. sets, we prove a jump theorem for the strongly nonbranching and strongly noncappable r. e. degrees. Mathematics Subject Classification : 03D25.     

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.     

Cupping the Recursively Enumerable Degrees by D.R.E. Degrees

We prove that there are two incomplete d.r.e. degrees (the Turingdegrees of differences of two recursively enumerable sets) suchthat every non-zero recursively enumerable degree cups at leastone of them to 0', the greatest recursively enumerable (Turing)degree. 1991 Mathematics Subject Classification: primary 03D25,03D30; secondary 03D35.     

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

Some New Lattice Constructions in High R. E. Degrees

A well-known theorem by Martin asserts that the degrees of maximal sets are precisely the high recursively enumerable (r. e.) degrees, and the same is true with ‘maximal’ replaced by ‘dense simple’, ‘r-maximal’, ‘strongly hypersimple’ or ‘finitely strongly hypersimple’. Many other constructions can also be carried out in any given high r. e. degree, for instance r-maximal or hyperhypersimple sets without maximal supersets (Lerman, Lachlan). In this paper questions of this type are considered systematically. Ultimately it is shown that every conjunction of simplicity- and non-extensibility properties can be accomplished, unless it is ruled out by well-known, elementary results. Moreover, each construction can be carried out in any given high r. e. degree, as might be expected. For instance, every high r. e. degree contains a dense simple, strongly hypersimple set A which is contained neither in a hyperhypersimple nor in an r-maximal set. The paper also contains some auxiliary results, for instance: every r. e. set B can be transformed into an r. e. set A such that (i) A has no dense simple superset, (ii) the transformation preserves simplicity- or non-extensibility properties as far as this is consistent with (i), and (iii) A ?_T B if B is high, and A ≥_T B otherwise. Several proofs involve refinements of known constructions; relationships to earlier results are discussed in detail.     

Splittings of 0' into the Recursively Enumerable Degrees

Lachlan [9] proved that there exists a non-recursive recursively enumerable (r. e.) degree such that every non-recursive r. e. degree below it bounds a minimal pair. In this paper we first prove the dual of this fact. Second, we answer a question of Jockusch by showing that there exists a pair of incomplete r. e. degrees a₀, a₁ such that for every non-recursive r. e. degree w, there is a pair of incomparable r. e. degrees b₀, b₂ such that w = b₀ V b₁ and b_i for i = 0, 1. Mathematics Subject Classification: 03D25, 03D30.     

Lattice Embeddings into the R.E. Degrees Preserving 0 and 1

We show that a finite distributive lattice can be embedded intothe r.e. degrees preserving least and greatest element if andonly if the lattice contains a join-irreducible noncappableelement.     

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.     

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.     

On the Density of the Pseudo-Isolated Degrees

A d.c.e. (2-computably enumerable) degree d is pseudo-isolatedif d itself is non-isolated (in the sense that no computablyenumerable (c.e.) degree below d can bound the c.e. degreesbelow d) and there is a d.c.e. degree b < d bounding allc.e. degrees below d. We prove in this paper that the pseudo-isolateddegrees are densely distributed in the c.e. degrees. 2000 MathematicsSubject Classification 03D25, 03D28.     

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)     

Graphs realised by r.e. equivalence relations

We investigate dependence of recursively enumerable graphs on the equality relation given by a specific r.e. equivalence relation on ω. In particular we compare r.e. equivalence relations in terms of graphs they permit to represent. This defines partially ordered sets that depend on classes of graphs under consideration. We investigate some algebraic properties of these partially ordered sets. For instance, we show that some of these partial ordered sets possess atoms, minimal and maximal elements. We also fully describe the isomorphism types of some of these partial orders.     

Modulo computably enumerable degrees by cupping partners

Cupping partners of an element in an upper semilattice with a greatest element 1 are those joining the element to 1. We define a congruence relation on such an upper semilattice by considering the elements having the same cupping partners as equivalent. It is interesting that this congruence relation induces a non-dense quotient structure of computably enumerable Turing degrees. Another main interesting phenomenon in this article is that on the computably enumerable degrees, this relation is different from that modulo the noncuppable ideal, though they define a same equivalent class for the computable Turing degree.     

Infimum Properties Differ in the Weak Truth-table Degrees and the Turing Degrees

Abstract We prove that there are non-recursive r.e. sets A and C with A < _T C such that for every set . Both authors are supported by “863” and the National Science Foundation of China     

Banach流形上映射度

本文讨论一种无限维流形上拓扑不变量，即具有可定向Ｆｒｅｄｈｏｌｍ结构的实Ｂａｎａｃｈ流形上　　Ｃｒ　　映射度．它是通常有限维流形上光滑映射度的一种自然推广．     

不可约特征标次数为等差数的有限可解群

设G为有限群,cd(G)表示G的所有复不可约特征标次数的集合.本文研究了不可约特征标次数为等差数的有限可解群,得到两个结果:如果cd(G)={1,1+d,1+2d,…,1+kd},则k≤2或cd(G)={1,2,3,4};如果cd(G)={1,a,a+d,a+2d,…,a+kd},|cd(G)|≥4,(a,d)=1,则cd(G)={1,2,2^e+1,2e+1,2^(e+1)},并给出了d>1时群的结构.     

Degrees of presentability of structures. I

Presentations of structures in admissible sets, as well as different relations of effective reducibility between the structures, are treated. Semilattices of degrees of Σ-definability are the main object of investigation. It is shown that the semilattice of degrees of Σ-definability of countable structures agrees well with semilattices of T-and e-degrees of subsets of natural numbers. Also an attempt is made to study properties of the structures that are inherited under various effective reducibilities and explore how degrees of presentability depend on choices of different admissible sets as domains for presentations. Supported by RFBR grant Nos. 05-0100481 and 06-0104002, by the Council for Grants (under RF President) for State Support of Young Candidates of Science and Their Supervisors via project MK-1239.2005.1, and via INTAS project YSF 04-83-3310. __________ Translated from Algebra i Logika, Vol. 46, No. 6, pp. 763–788, November–December, 2007.     

There is no degree invariant half-jump

We prove that there is no degree invariant solution to Post's problem that always gives an intermediate degree. In fact, assuming definable determinacy, if is any definable operator on degrees such that on a cone then is low or high on a cone of degrees, i.e., there is a degree such that for every or for every .