10 found
Order:
  1.  17
    Degrees of Relative Provability.Mingzhong Cai - 2012 - Notre Dame Journal of Formal Logic 53 (4):479-489.
    There are many classical connections between the proof-theoretic strength of systems of arithmetic and the provable totality of recursive functions. In this paper we study the provability strength of the totality of recursive functions by investigating the degree structure induced by the relative provability order of recursive algorithms. We prove several results about this proof-theoretic degree structure using recursion-theoretic techniques such as diagonalization and the Recursion Theorem.
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  2.  3
    Unprovability and Proving Unprovability.Mingzhong Cai - 2015 - Studia Logica 103 (3):559-578.
    We investigate the “unprovability of unprovability”. Given a sentence P and a fixed base theory T, the unprovability of P is the sentence “\ ”. We show that the unprovability of an unprovable true sentence can be “hard to prove”.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  3.  8
    A 2-Minimal Non-Gl2degree.Mingzhong Cai - 2010 - Journal of Mathematical Logic 10 (1):1-30.
  4.  11
    A Hyperimmune Minimal Degree and an ANR 2-Minimal Degree.Mingzhong Cai - 2010 - Notre Dame Journal of Formal Logic 51 (4):443-455.
    We develop a new method for constructing hyperimmune minimal degrees and construct an ANR degree which is a minimal cover of a minimal degree.
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  5.  55
    The N-R.E. Degrees: Undecidability and Σ1substructures.Mingzhong Cai, Richard A. Shore & Theodore A. Slaman - 2012 - Journal of Mathematical Logic 12 (1):1250005-.
  6.  21
    On the Existence of a Strong Minimal Pair.George Barmpalias, Mingzhong Cai, Steffen Lempp & Theodore A. Slaman - 2015 - Journal of Mathematical Logic 15 (1):1550003.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  7.  16
    2-Minimality, Jump Classes and a Note on Natural Definability.Mingzhong Cai - 2014 - Annals of Pure and Applied Logic 165 (2):724-741.
    We show that there is a generalized high degree which is a minimal cover of a minimal degree. This is the highest jump class one can reach by finite iterations of minimality. This result also answers an old question by Lerman.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  8.  8
    Domination, Forcing, Array Nonrecursiveness and Relative Recursive Enumerability.Mingzhong Cai & Richard A. Shore - 2012 - Journal of Symbolic Logic 77 (1):33-48.
    We present some abstract theorems showing how domination properties equivalent to being $\overline{GL}_{2}$ or array nonrecursive can be used to construct sets generic for different notions of forcing. These theorems are then applied to give simple proofs of some known results. We also give a direct uniform proof of a recent result of Ambos-Spies, Ding, Wang, and Yu [2009] that every degree above any in $\overline{GL}_{2}$ is recursively enumerable in a 1-generic degree strictly below it. Our major new result is (...)
    Direct download (6 more)  
     
    Export citation  
     
    My bibliography  
  9.  9
    Array Nonrecursiveness and Relative Recursive Enumerability.Mingzhong Cai - 2012 - Journal of Symbolic Logic 77 (1):21-32.
    In this paper we prove that a degree a is array nonrecursive (ANR) if and only if every degree b ≥ a is r.e. in and strictly above another degree (RRE). This result will answer some questions in [ASDWY]. We also deduce an interesting corollary that every n-REA degree has a strong minimal cover if and only if it is array recursive.
    Direct download (5 more)  
     
    Export citation  
     
    My bibliography  
  10.  1
    Low Level Nondefinability Results: Domination and Recursive Enumeration.Mingzhong Cai & Richard A. Shore - 2013 - Journal of Symbolic Logic 78 (3):1005-1024.