5 found
Sort by:
  1. Michael E. Mytilinaios & Theodore A. Slaman (2003). Differences Between Resource Bounded Degree Structures. Notre Dame Journal of Formal Logic 44 (1):1-12.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  2. Theodore A. Slaman & Michael~E. Mytilinaios (2003). Differences Between Resource Bounded Degree Structures. Notre Dame Journal of Formal Logic 44 (1):1-12.
    We exhibit a structural difference between the truth-table degrees of the sets which are truth-table above 0′ and the PTIME-Turing degrees of all sets. Though the structures do not have the same isomorphism type, demonstrating this fact relies on developing their common theory.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  3. Marcia J. Groszek, Michael E. Mytilinaios & Theodore A. Slaman (1996). The Sacks Density Theorem and Σ2-Bounding. Journal of Symbolic Logic 61 (2):450 - 467.
    The Sacks Density Theorem [7] states that the Turing degrees of the recursively enumerable sets are dense. We show that the Density Theorem holds in every model of P - + BΣ 2 . The proof has two components: a lemma that in any model of P - + BΣ 2 , if B is recursively enumerable and incomplete then IΣ 1 holds relative to B and an adaptation of Shore's [9] blocking technique in α-recursion theory to models of arithmetic.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  4. Michael Mytilinaios (1989). Finite Injury and ∑1-Induction. Journal of Symbolic Logic 54 (1):38 - 49.
    Working in the language of first-order arithmetic we consider models of the base theory P - . Suppose M is a model of P - and let M satisfy induction for σ 1 -formulas. First it is shown that the Friedberg-Muchnik finite injury argument can be performed inside M, and then, using a blocking method for the requirements, we prove that the Sacks splitting construction can be done in M. So, the "amount" of induction needed to perform the known finite (...)
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  5. Michael E. Mytilinaios & Theodore A. Slaman (1988). Σ2-Collection and the Infinite Injury Priority Method. Journal of Symbolic Logic 53 (1):212 - 221.
    We show that the existence of a recursively enumerable set whose Turing degree is neither low nor complete cannot be proven from the basic axioms of first order arithmetic (P -) together with Σ 2 -collection (BΣ 2 ). In contrast, a high (hence, not low) incomplete recursively enumerable set can be assembled by a standard application of the infinite injury priority method. Similarly, for each n, the existence of an incomplete recursively enumerable set that is neither low n nor (...)
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation