Switch to: Citations

Add references

You must login to add references.
  1. Corrigendum To: "On the Strength of Ramsey's Theorem for Pairs".Peter A. Cholak, Carl G. Jockusch & Theodore A. Slaman - 2009 - Journal of Symbolic Logic 74 (4):1438 - 1439.
  • The Alpha-Finite Injury Method.G. E. Sacks - 1972 - Annals of Mathematical Logic 4 (4):343.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   36 citations  
  • The Fine Structure of the Constructible Hierarchy.R. Björn Jensen - 1972 - Annals of Mathematical Logic 4 (3):229.
  • A Recursively Enumerable Degree Which Will Not Split Over All Lesser Ones.Alistair H. Lachlan - 1976 - Annals of Mathematical Logic 9 (4):307.
  • Friedberg Numbering in Fragments of Peano Arithmetic and Α-Recursion Theory.Wei Li - 2013 - Journal of Symbolic Logic 78 (4):1135-1163.
  • Combinatorial Principles Weaker Than Ramsey's Theorem for Pairs.Denis R. Hirschfeldt & Richard A. Shore - 2007 - Journal of Symbolic Logic 72 (1):171-206.
    We investigate the complexity of various combinatorial theorems about linear and partial orders, from the points of view of computability theory and reverse mathematics. We focus in particular on the principles ADS (Ascending or Descending Sequence), which states that every infinite linear order has either an infinite descending sequence or an infinite ascending sequence, and CAC (Chain-AntiChain), which states that every infinite partial order has either an infinite chain or an infinite antichain. It is well-known that Ramsey's Theorem for pairs (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   23 citations  
  • On the Strength of Ramsey's Theorem.David Seetapun & Theodore A. Slaman - 1995 - 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)  
     
    Export citation  
     
    Bookmark   30 citations  
  • Separating Principles Below Ramsey's Theorem for Pairs.Manuel Lerman, Reed Solomon & Henry Towsner - 2013 - Journal of Mathematical Logic 13 (2):1350007.
    In recent years, there has been a substantial amount of work in reverse mathematics concerning natural mathematical principles that are provable from RT, Ramsey's Theorem for Pairs. These principles tend to fall outside of the "big five" systems of reverse mathematics and a complicated picture of subsystems below RT has emerged. In this paper, we answer two open questions concerning these subsystems, specifically that ADS is not equivalent to CAC and that EM is not equivalent to RT.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   11 citations  
  • On Suborderings of the Alpha-Recursively Enumerable Alpha-Degrees.Manuel Lerman - 1972 - Annals of Mathematical Logic 4 (4):369.
  • Ramsey's Theorem and Recursion Theory.Carl G. Jockusch - 1972 - Journal of Symbolic Logic 37 (2):268-280.
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   29 citations  
  • Bounding Minimal Pairs.A. H. Lachlan - 1979 - Journal of Symbolic Logic 44 (4):626-642.
  • Recursively Enumerable Generic Sets.Wolfgang Maass - 1982 - Journal of Symbolic Logic 47 (4):809-823.
    We show that one can solve Post's Problem by constructing generic sets in the usual set theoretic framework applied to tiny universes. This method leads to a new class of recursively enumerable sets: r.e. generic sets. All r.e. generic sets are low and simple and therefore of Turing degree strictly between 0 and 0'. Further they supply the first example of a class of low recursively enumerable sets which are automorphic in the lattice E of recursively enumerable sets with inclusion. (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   13 citations  
  • Working Below a High Recursively Enumerable Degree.Richard A. Shore & Theodore A. Slaman - 1993 - Journal of Symbolic Logic 58 (3):824-859.
  • The Strength of the Rainbow Ramsey Theorem.Barbara F. Csima & Joseph R. Mileti - 2009 - Journal of Symbolic Logic 74 (4):1310 - 1324.
    The Rainbow Ramsey Theorem is essentially an "anti-Ramsey" theorem which states that certain types of colorings must be injective on a large subset (rather than constant on a large subset). Surprisingly, this version follows easily from Ramsey's Theorem, even in the weak system RCA₀ of reverse mathematics. We answer the question of the converse implication for pairs, showing that the Rainbow Ramsey Theorem for pairs is in fact strictly weaker than Ramsey's Theorem for pairs over RCA₀. The separation involves techniques (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  • Reverse Mathematics and Ramsey's Property for Trees.Jared Corduan, Marcia J. Groszek & Joseph R. Mileti - 2010 - Journal of Symbolic Logic 75 (3):945-954.
    We show, relative to the base theory RCA₀: A nontrivial tree satisfies Ramsey's Theorem only if it is biembeddable with the complete binary tree. There is a class of partial orderings for which Ramsey's Theorem for pairs is equivalent to ACA₀. Ramsey's Theorem for singletons for the complete binary tree is stronger than $B\sum_{2}^{0}$ , hence stronger than Ramsey's Theorem for singletons for ω. These results lead to extensions of results, or answers to questions, of Chubb, Hirst, and McNicholl [3].
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  • Random Reals, the Rainbow Ramsey Theorem, and Arithmetic Conservation.Chris J. Conidis & Theodore A. Slaman - 2013 - 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)  
     
    Export citation  
     
    Bookmark   3 citations  
  • The Density of Infima in the Recursively Enumerable Degrees.Theodore A. Slaman - 1991 - Annals of Pure and Applied Logic 52 (1-2):155-179.
    We show that every nontrivial interval in the recursively enumerable degrees contains an incomparable pair which have an infimum in the recursively enumerable degrees.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   16 citations  
  • Preface.Juichi Shinoda & Tosiyuki Tugué - 1991 - Annals of Pure and Applied Logic 52 (1-2):1.
  • On the Strength of Ramsey's Theorem for Pairs.Peter A. Cholak, Carl G. Jockusch & Theodore A. Slaman - 2001 - 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 (9 more)  
     
    Export citation  
     
    Bookmark   38 citations  
  • Reverse Mathematics, Computability, and Partitions of Trees.Jennifer Chubb, Jeffry L. Hirst & Timothy H. McNicholl - 2009 - Journal of Symbolic Logic 74 (1):201-215.
    We examine the reverse mathematics and computability theory of a form of Ramsey's theorem in which the linear n-tuples of a binary tree are colored.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  • A Cohesive Set Which is Not High.Carl Jockusch & Frank Stephan - 1993 - Mathematical Logic Quarterly 39 (1):515-530.
    We study the degrees of unsolvability of sets which are cohesive . We answer a question raised by the first author in 1972 by showing that there is a cohesive set A whose degree a satisfies a' = 0″ and hence is not high. We characterize the jumps of the degrees of r-cohesive sets, and we show that the degrees of r-cohesive sets coincide with those of the cohesive sets. We obtain analogous results for strongly hyperimmune and strongly hyperhyperimmune sets (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   24 citations