17 found
Order:
  1.  72
    Splitting and Nonsplitting II: A Low {\Sb 2$} C.E. Degree About Which ${\Bf 0}'$ is Not Splittable.S. Barry Cooper & Angsheng Li - 2002 - Journal of Symbolic Logic 67 (4):1391-1430.
    It is shown that there exists a low2 Harrington non-splitting base-that is, a low2 computably enumerable (c.e.) degree a such that for any c.e. degrees x, y, if $0' = x \vee y$ , then either $0' = x \vee a$ or $0' = y \vee a$ . Contrary to prior expectations, the standard Harrington non-splitting construction is incompatible with the $low_{2}-ness$ requirements to be satisfied, and the proof given involves new techniques with potentially wider application.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark  
  2.  28
    Bounding and Nonbounding Minimal Pairs in the Enumeration Degrees.S. Barry Cooper, Angsheng Li, Andrea Sorbi & Yue Yang - 2005 - Journal of Symbolic Logic 70 (3):741 - 766.
    We show that every nonzero $\Delta _{2}^{0}$ e-degree bounds a minimal pair. On the other hand, there exist $\Sigma _{2}^{0}$ e-degrees which bound no minimal pair.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  3.  23
    Bounding Computably Enumerable Degrees in the Ershov Hierarchy.Angsheng Li, Guohua Wu & Yue Yang - 2006 - Annals of Pure and Applied Logic 141 (1):79-88.
    Lachlan observed that any nonzero d.c.e. degree bounds a nonzero c.e. degree. In this paper, we study the c.e. predecessors of d.c.e. degrees, and prove that given a nonzero d.c.e. degree , there is a c.e. degree below and a high d.c.e. degree such that bounds all the c.e. degrees below . This result gives a unified approach to some seemingly unrelated results. In particular, it has the following two known theorems as corollaries: there is a low c.e. degree isolating (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  4.  31
    There is No Low Maximal D.C.E. Degree.Marat Arslanov, S. Barry Cooper & Angsheng Li - 2000 - Mathematical Logic Quarterly 46 (3):409-416.
    We show that for any computably enumerable set A and any equation image set L, if L is low and equation image, then there is a c.e. splitting equation image such that equation image. In Particular, if L is low and n-c.e., then equation image is n-c.e. and hence there is no low maximal n-c.e. degree.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  5.  6
    The Existence of High Nonbounding Degrees in the Difference Hierarchy.Chi Tat Chong, Angsheng Li & Yue Yang - 2006 - Annals of Pure and Applied Logic 138 (1):31-51.
    We study the jump hierarchy of d.c.e. Turing degrees and show that there exists a high d.c.e. degree d which does not bound any minimal pair of d.c.e. degrees.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  6.  16
    On the Distribution of Lachlan Nonsplitting Bases.S. Barry Cooper, Angsheng Li & Xiaoding Yi - 2002 - Archive for Mathematical Logic 41 (5):455-482.
    We say that a computably enumerable (c.e.) degree b is a Lachlan nonsplitting base (LNB), if there is a computably enumerable degree a such that a > b, and for any c.e. degrees w,v ≤ a, if a ≤ w or; v or; b then either a ≤ w or; b or a ≤ v or; b. In this paper we investigate the relationship between bounding and nonbounding of Lachlan nonsplitting bases and the high /low hierarchy. We prove that there (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  7.  6
    A Minimal Pair Joining to a Plus Cupping Turing Degree.Dengfeng Li & Angsheng Li - 2003 - Mathematical Logic Quarterly 49 (6):553-566.
    A computably enumerable degree a is called nonbounding, if it bounds no minimal pair, and plus cupping, if every nonzero c.e. degree x below a is cuppable. Let NB and PC be the sets of all nonbounding and plus cupping c.e. degrees, respectively. Both NB and PC are well understood, but it has not been possible so far to distinguish between the two classes. In the present paper, we investigate the relationship between the classes NB and PC, and show that (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  8.  26
    On Lachlan’s Major Sub-Degree Problem.S. Barry Cooper & Angsheng Li - 2008 - Archive for Mathematical Logic 47 (4):341-434.
    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, ${{\bf 0' = b \lor x}}$ if and only if (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  9.  5
    Continuity of Capping in C bT.Paul Brodhead, Angsheng Li & Weilin Li - 2008 - Annals of Pure and Applied Logic 155 (1):1-15.
    A set Asubset of or equal toω is called computably enumerable , if there is an algorithm to enumerate the elements of it. For sets A,Bsubset of or equal toω, we say that A is bounded Turing reducible to reducible to) B if there is a Turing functional, Φ say, with a computable bound of oracle query bits such that A is computed by Φ equipped with an oracle B, written image. Let image be the structure of the c.e. bT-degrees, (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  10.  10
    Bounding Cappable Degrees.Angsheng Li - 2000 - Archive for Mathematical Logic 39 (5):311-352.
    It will be shown that there exist computably enumerable degrees a and b such that a $>$ b, and for any computably enumerable degree u, if u $\leq$ a and u is cappable, then u $<$ b.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  11.  12
    On a Conjecture of Lempp.Angsheng Li - 2000 - Archive for Mathematical Logic 39 (4):281-309.
    In this paper, we first prove that there exist computably enumerable (c.e.) degrees a and b such that ${\bf a\not\leq b}$ , and for any c.e. degree u, if ${\bf u\leq a}$ and u is cappable, then ${\bf u\leq b}$ , so refuting a conjecture of Lempp (in Slaman [1996]); secondly, we prove that: (A. Li and D. Wang) there is no uniform construction to build nonzero cappable degree below a nonzero c.e. degree, that is, there is no computable function (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  12.  11
    Kolmogorov Complexity and Computably Enumerable Sets.George Barmpalias & Angsheng Li - 2013 - Annals of Pure and Applied Logic 164 (12):1187-1200.
  13.  17
    Bounding Minimal Degrees by Computably Enumerable Degrees.Angsheng Li & Dongping Yang - 1998 - Journal of Symbolic Logic 63 (4):1319-1347.
    In this paper, we prove that there exist computably enumerable degrees a and b such that $\mathbf{a} > \mathbf{b}$ and for any degree x, if x ≤ a and x is a minimal degree, then $\mathbf{x}.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark  
  14.  7
    There is No Low Maximal D. C. E. Degree– Corrigendum.Marat Arslanov, S. Barry Cooper & Angsheng Li - 2004 - Mathematical Logic Quarterly 50 (6):628-636.
    We give a corrected proof of an extension of the Robinson Splitting Theorem for the d. c. e. degrees.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  15.  4
    Bounding and Nonbounding Minimal Pairs in the Enumeration Degrees.S. Barry Cooper, Angsheng Li, Andrea Sorbi & Yue Yang - 2005 - Journal of Symbolic Logic 70 (3):741-766.
    We show that every nonzero Δ⁰₂ e-degree bounds a minimal pair. On the other hand, there exist Σ⁰₂ e-degrees which bound no minimal pair.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  16.  14
    A Hierarchy for the Plus Cupping Turing Degrees.Yong Wang & Angsheng Li - 2003 - Journal of Symbolic Logic 68 (3):972-988.
    We say that a computably enumerable (c. e.) degree a is plus-cupping, if for every c.e. degree x with $0 < x \leq a$ , there is a c. e. degree $y \not= 0'$ such that $x \vee y = 0/\'$ . We say that a is n-plus-cupping. if for every c. e. degree x, if $0 < x \leq a$ , then there is a $low_n$ c. e. degree 1 such that $x \vee l = 0'$ . Let PC (...)
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark  
  17.  6
    Complementing Cappable Degrees in the Difference Hierarchy.Rod Downey, Angsheng Li & Guohua Wu - 2004 - Annals of Pure and Applied Logic 125 (1-3):101-118.
    We prove that for any computably enumerable degree c, if it is cappable in the computably enumerable degrees, then there is a d.c.e. degree d such that c d = 0′ and c ∩ d = 0. Consequently, a computably enumerable degree is cappable if and only if it can be complemented by a nonzero d.c.e. degree. This gives a new characterization of the cappable degrees.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark