39 found
Sort by:
  1. Chris J. Conidis & Theodore A. Slaman (2013). Random Reals, the Rainbow Ramsey Theorem, and Arithmetic Conservation. Journal of Symbolic Logic 78 (1):195-206.
    We investigate the question “To what extent can random reals be used as a tool to establish number theoretic facts?” Let $\text{2-\textit{RAN\/}}$ be the principle that for every real $X$ there is a real $R$ which is 2-random relative to $X$. In Section 2, we observe that the arguments of Csima and Mileti [3] can be implemented in the base theory $\text{\textit{RCA}}_0$ and so $\text{\textit{RCA}}_0+\text{2-\textit{RAN\/}}$ implies the Rainbow Ramsey Theorem. In Section 3, we show that the Rainbow Ramsey Theorem is (...)
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  2. Noam Greenberg, Antonio Montalbán & Theodore A. Slaman (2013). Relative to Any Non-Hyperarithmetic Set. Journal of Mathematical Logic 13 (1):1250007.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  3. Mingzhong Cai, Richard A. Shore & Theodore A. Slaman (2012). The N-R.E. Degrees: Undecidability and Σ1substructures. Journal of Mathematical Logic 12 (01):1250005-.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  4. Peter A. Cholak, Carl G. Jockusch & Theodore A. Slaman (2009). Corrigendum To: "On the Strength of Ramsey's Theorem for Pairs". Journal of Symbolic Logic 74 (4):1438 - 1439.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  5. Peter Cholak, Jr} {Jockusch & Theodore A. Slaman (2009). Corrigendum To: “On the Strength of Ramsey's Theorem for Pairs”. Journal of Symbolic Logic 74 (4):1438-1439.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  6. Antonín Kučera & Theodore A. Slaman (2009). Low Upper Bounds of Ideals. Journal of Symbolic Logic 74 (2):517-534.
    We show that there is a low T-upper bound for the class of K-trivial sets, namely those which are weak from the point of view of algorithmic randomness. This result is a special case of a more general characterization of ideals in $\Delta _2^0 $ T-degrees for which there is a low T-upper bound.
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  7. Noam Greenberg, Richard A. Shore & Theodore A. Slaman (2006). The Theory of the Metarecursively Enumerable Degrees. Journal of Mathematical Logic 6 (01):49-68.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  8. Steffen Lempp, Theodore A. Slaman & Andrea Sorbi (2005). On Extensions of Embeddings Into the Enumeration Degrees of the -Sets. Journal of Mathematical Logic 5 (02):247-298.
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  9. Klaus Ambos-Spies, Bj�Rn Kjos-Hanssen, Steffen Lempp & Theodore A. Slaman (2004). Comparing DNR and WWKL. Journal of Symbolic Logic 69 (4):1089 - 1104.
    In Reverse Mathematics, the axiom system DNR, asserting the existence of diagonally nonrecursive functions, is strictly weaker than WWKL₀ (weak weak König's Lemma).
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  10. Scot Adams, Shaughan Lavine, Zlil Sela, Natarajan Shankar, Stephen Simpson, Stevo Todorcevic & Theodore A. Slaman (2003). University of Nevada, Las Vegas, Las Vegas, Nevada June 1–4, 2002. Bulletin of Symbolic Logic 9 (1).
    Direct download  
     
    My bibliography  
     
    Export citation  
  11. 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  
  12. 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  
  13. Peter A. Cholak, Carl G. Jockusch & Theodore A. Slaman (2001). On the Strength of Ramsey's Theorem for Pairs. Journal of Symbolic Logic 66 (1):1-55.
    We study the proof-theoretic strength and effective content of the infinite form of Ramsey's theorem for pairs. Let RT n k denote Ramsey's theorem for k-colorings of n-element sets, and let RT $^n_{ denote (∀ k)RT n k . Our main result on computability is: For any n ≥ 2 and any computable (recursive) k-coloring of the n-element sets of natural numbers, there is an infinite homogeneous set X with X'' ≤ T 0 (n) . Let IΣ n and BΣ (...)
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  14. Juichi Shinoda & Theodore A. Slaman (2000). Recursive in a Generic Real. Journal of Symbolic Logic 65 (1):164-172.
    There is a comeager set C contained in the set of 1-generic reals and a first order structure M such that for any real number X, there is an element of C which is recursive in X if and only if there is a presentation of M which is recursive in X.
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  15. Klaus Ambos-Spies, Theodore A. Slaman & Robert I. Soare (1998). Preface. Annals of Pure and Applied Logic 94 (1-3):1.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  16. Marat M. Arslanov, Geoffrey L. Laforte & Theodore A. Slaman (1998). Relative Enumerability in the Difference Hierarchy. Journal of Symbolic Logic 63 (2):411-420.
    We show that the intersection of the class of 2-REA degrees with that of the ω-r.e. degrees consists precisely of the class of d.r.e. degrees. We also include some applications and show that there is no natural generalization of this result to higher levels of the REA hierarchy.
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  17. Marcia J. Groszek & Theodore A. Slaman (1998). A Basis Theorem for Perfect Sets. Bulletin of Symbolic Logic 4 (2):204-209.
    We show that if there is a nonconstructible real, then every perfect set has a nonconstructible element, answering a question of K. Prikry. This is a specific instance of a more general theorem giving a sufficient condition on a pair $M\subset N$ of models of set theory implying that every perfect set in N has an element in N which is not in M.
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  18. Theodore A. Slaman (1998). Mathematical Definability. In H. G. Dales & Gianluigi Oliveri (eds.), Truth in Mathematics. Oxford University Press, Usa. 233.
    No categories
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  19. Theodore A. Slaman & W. Hugh Woodin (1998). Extending Partial Orders to Dense Linear Orders. Annals of Pure and Applied Logic 94 (1-3):253-261.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  20. Marcia J. Groszek & Theodore A. Slaman (1997). Π10 Classes and Minimal Degrees. Annals of Pure and Applied Logic 87 (2):117-144.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  21. Marcia J. Groszek & Theodore A. Slaman (1997). < I> Π_< Sub> 1< Sup> 0 Classes and Minimal Degrees. Annals of Pure and Applied Logic 87 (2):117-144.
    Direct download  
     
    My bibliography  
     
    Export citation  
  22. Christine Ann Haught & Theodore A. Slaman (1997). Automorphisms in the PTIME-Turing Degrees of Recursive Sets. Annals of Pure and Applied Logic 84 (1):139-152.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  23. Theodore A. Slaman & W. Hugh Woodin (1997). Definability in the Enumeration Degrees. Archive for Mathematical Logic 36 (4-5):255-267.
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  24. William C. Calhoun & Theodore A. Slaman (1996). The Π02 Enumeration Degrees Are Not Dense. Journal of Symbolic Logic 61 (4):1364 - 1379.
    We show that the Π 0 2 enumeration degrees are not dense. This answers a question posed by Cooper.
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  25. 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  
  26. André Nies, Richard A. Shore & Theodore A. Slaman (1996). Definability in the Recursively Enumerable Degrees. Bulletin of Symbolic Logic 2 (4):392-404.
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  27. David Seetapun & Theodore A. Slaman (1995). On the Strength of Ramsey's Theorem. Notre Dame Journal of Formal Logic 36 (4):570-582.
    We show that, for every partition F of the pairs of natural numbers and for every set C, if C is not recursive in F then there is an infinite set H, such that H is homogeneous for F and C is not recursive in H. We conclude that the formal statement of Ramsey's Theorem for Pairs is not strong enough to prove , the comprehension scheme for arithmetical formulas, within the base theory , the comprehension scheme for recursive formulas. (...)
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  28. Carl G. Jockusch Jr & Theodore A. Slaman (1993). On the Σ2-Theory of the Upper Semilattice of Turing Degrees. Journal of Symbolic Logic 58 (1):193 - 204.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  29. Richard A. Shore & Theodore A. Slaman (1993). Working Below a High Recursively Enumerable Degree. Journal of Symbolic Logic 58 (3):824-859.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  30. Rod Downey & Theodore A. Slaman (1992). On Co-Simple Isols and Their Intersection Types. Annals of Pure and Applied Logic 56 (1-3):221-237.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  31. Peter G. Hinman & Theodore A. Slaman (1991). Jump Embeddings in the Turing Degrees. Journal of Symbolic Logic 56 (2):563-591.
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  32. Theodore A. Slaman (1991). The Density of Infima in the Recursively Enumerable Degrees. Annals of Pure and Applied Logic 52 (1-2):155-179.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  33. Richard A. Shore & Theodore A. Slaman (1990). Working Below a Low2 Recursively Enumerably Degree. Archive for Mathematical Logic 29 (3):201-211.
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  34. Steffen Lempp & Theodore A. Slaman (1989). A Limit on Relative Genericity in the Recursively Enumerable Sets. Journal of Symbolic Logic 54 (2):376-395.
    Work in the setting of the recursively enumerable sets and their Turing degrees. A set X is low if X', its Turning jump, is recursive in $\varnothing'$ and high if X' computes $\varnothing''$ . Attempting to find a property between being low and being recursive, Bickford and Mills produced the following definition. W is deep, if for each recursively enumerable set A, the jump of $A \bigoplus W$ is recursive in the jump of A. We prove that there are no (...)
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  35. Theodore A. Slaman & John R. Steel (1989). Complementation in the Turing Degrees. Journal of Symbolic Logic 54 (1):160-176.
    Posner [6] has shown, by a nonuniform proof, that every ▵ 0 2 degree has a complement below 0'. We show that a 1-generic complement for each ▵ 0 2 set of degree between 0 and 0' can be found uniformly. Moreover, the methods just as easily can be used to produce a complement whose jump has the degree of any real recursively enumerable in and above $\varnothing'$ . In the second half of the paper, we show that the complementation (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  36. 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  
  37. Theodore A. Slaman (1986). On the Kleene Degrees of Π11 Sets. Journal of Symbolic Logic 51 (2):352 - 359.
    Let A and B be subsets of the reals. Say that A κ ≥ B, if there is a real a such that the relation "x ∈ B" is uniformly Δ 1 (a, A) in L[ ω x,a,A 1 , x,a,A]. This reducibility induces an equivalence relation $\equiv_\kappa$ on the sets of reals; the $\equiv_\kappa$ -equivalence class of a set is called its Kleene degree. Let K be the structure that consists of the Kleene degrees and the induced partial order (...)
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  38. Theodore A. Slaman (1985). Are Dense. In Anil Nerode & Richard A. Shore (eds.), Recursion Theory. American Mathematical Society. 42--195.
    No categories
    Direct download  
     
    My bibliography  
     
    Export citation  
  39. Theodore A. Slaman (1985). Reflection and Forcing in< I> E_-Recursion Theory. Annals of Pure and Applied Logic 29 (1):79-106.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation