Switch to: References

Add citations

You must login to add citations.
  1. Stable Ramsey's Theorem and Measure.Damir D. Dzhafarov - 2011 - Notre Dame Journal of Formal Logic 52 (1):95-112.
    The stable Ramsey's theorem for pairs has been the subject of numerous investigations in mathematical logic. We introduce a weaker form of it by restricting from the class of all stable colorings to subclasses of it that are nonnull in a certain effective measure-theoretic sense. We show that the sets that can compute infinite homogeneous sets for nonnull many computable stable colorings and the sets that can compute infinite homogeneous sets for all computable stable colorings agree below $\emptyset'$ but not (...)
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • Effective Versions of Ramsey's Theorem: Avoiding the Cone Above $\mathbf{0}$'.Tamara Lakins Hummel - 1994 - Journal of Symbolic Logic 59 (4):1301-1325.
    Ramsey's Theorem states that if $P$ is a partition of $\lbrack\omega\rbrack^\kappa$ into finitely many partition classes, then there exists an infinite set of natural numbers which is homogeneous for $P$. We consider the degrees of unsolvability and arithmetical definability properties of infinite homogeneous sets for recursive partitions. We give Jockusch's proof of Seetapun's recent theorem that for all recursive partitions of $\lbrack\omega\rbrack^2$ into finitely many pieces, there exists an infinite homogeneous set $A$ such that $\emptyset' \nleq_T A$. Two technical extensions (...)
    Download  
     
    Export citation  
     
    Bookmark   4 citations  
  • 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.
    Download  
     
    Export citation  
     
    Bookmark   6 citations  
  • (1 other version)Nonstandard models in recursion theory and reverse mathematics.C. T. Chong, Wei Li & Yue Yang - 2014 - Bulletin of Symbolic Logic 20 (2):170-200.
    We give a survey of the study of nonstandard models in recursion theory and reverse mathematics. We discuss the key notions and techniques in effective computability in nonstandard models, and their applications to problems concerning combinatorial principles in subsystems of second order arithmetic. Particular attention is given to principles related to Ramsey’s Theorem for Pairs.
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • Cohesive sets and rainbows.Wei Wang - 2014 - Annals of Pure and Applied Logic 165 (2):389-408.
    We study the strength of RRT32, Rainbow Ramsey Theorem for colorings of triples, and prove that RCA0 + RRT32 implies neither WKL0 nor RRT42 source. To this end, we establish some recursion theoretic properties of cohesive sets and rainbows for colorings of pairs. We show that every sequence admits a cohesive set of non-PA Turing degree; and that every ∅′-recursive sequence admits a low3 cohesive set.
    Download  
     
    Export citation  
     
    Bookmark   5 citations  
  • Term extraction and Ramsey's theorem for pairs.Alexander P. Kreuzer & Ulrich Kohlenbach - 2012 - Journal of Symbolic Logic 77 (3):853-895.
    In this paper we study with proof-theoretic methods the function(al) s provably recursive relative to Ramsey's theorem for pairs and the cohesive principle (COH). Our main result on COH is that the type 2 functional provably recursive from $RCA_0 + COH + \Pi _1^0 - CP$ are primitive recursive. This also provides a uniform method to extract bounds from proofs that use these principles. As a consequence we obtain a new proof of the fact that $WKL_0 + \Pi _1^0 - (...)
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • Ramsey's theorem for computably enumerable colorings.Tamara Hummel & Carl Jockusch - 2001 - Journal of Symbolic Logic 66 (2):873-880.
    It is shown that for each computably enumerable set P of n-element subsets of ω there is an infinite Π 0 n set $A \subseteq \omega$ such that either all n-element subsets of A are in P or no n-element subsets of A are in P. An analogous result is obtained with the requirement that A be Π 0 n replaced by the requirement that the jump of A be computable from 0 (n) . These results are best possible in (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • Schnorr trivial sets and truth-table reducibility.Johanna N. Y. Franklin & Frank Stephan - 2010 - Journal of Symbolic Logic 75 (2):501-521.
    We give several characterizations of Schnorr trivial sets, including a new lowness notion for Schnorr triviality based on truth-table reducibility. These characterizations allow us to see not only that some natural classes of sets, including maximal sets, are composed entirely of Schnorr trivials, but also that the Schnorr trivial sets form an ideal in the truth-table degrees but not the weak truth-table degrees. This answers a question of Downey, Griffiths and LaForte.
    Download  
     
    Export citation  
     
    Bookmark   8 citations  
  • 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Σ (...)
    Download  
     
    Export citation  
     
    Bookmark   56 citations  
  • The cohesive principle and the Bolzano‐Weierstraß principle.Alexander P. Kreuzer - 2011 - Mathematical Logic Quarterly 57 (3):292-298.
    The aim of this paper is to determine the logical and computational strength of instances of the Bolzano-Weierstraß principle and a weak variant of it.We show that BW is instance-wise equivalent to the weak König’s lemma for Σ01-trees . This means that from every bounded sequence of reals one can compute an infinite Σ01-0/1-tree, such that each infinite branch of it yields an accumulation point and vice versa. Especially, this shows that the degrees d ≫ 0′ are exactly those containing (...)
    Download  
     
    Export citation  
     
    Bookmark   4 citations  
  • Open questions about Ramsey-type statements in reverse mathematics.Ludovic Patey - 2016 - Bulletin of Symbolic Logic 22 (2):151-169.
    Ramsey’s theorem states that for any coloring of then-element subsets of ℕ with finitely many colors, there is an infinite setHsuch that alln-element subsets ofHhave the same color. The strength of consequences of Ramsey’s theorem has been extensively studied in reverse mathematics and under various reducibilities, namely, computable reducibility and uniform reducibility. Our understanding of the combinatorics of Ramsey’s theorem and its consequences has been greatly improved over the past decades. In this paper, we state some questions which naturally arose (...)
    Download  
     
    Export citation  
     
    Bookmark   4 citations  
  • Inductive inference and reverse mathematics.Rupert Hölzl, Sanjay Jain & Frank Stephan - 2016 - Annals of Pure and Applied Logic 167 (12):1242-1266.
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • Ramsey's Theorem and Cone Avoidance.Damir D. Dzhafarov & Carl G. Jockusch - 2009 - Journal of Symbolic Logic 74 (2):557-578.
    It was shown by Cholak, Jockusch, and Slaman that every computable 2-coloring of pairs admits an infinite low₂ homogeneous set H. We answer a question of the same authors by showing that H may be chosen to satisfy in addition $C\,\not \leqslant _T \,H$, where C is a given noncomputable set. This is shown by analyzing a new and simplified proof of Seetapun's cone avoidance theorem for Ramsey's theorem. We then extend the result to show that every computable 2-coloring of (...)
    Download  
     
    Export citation  
     
    Bookmark   12 citations  
  • Reverse mathematics and a Ramsey-type König's Lemma.Stephen Flood - 2012 - Journal of Symbolic Logic 77 (4):1272-1280.
    In this paper, we propose a weak regularity principle which is similar to both weak König's lemma and Ramsey's theorem. We begin by studying the computational strength of this principle in the context of reverse mathematics. We then analyze different ways of generalizing this principle.
    Download  
     
    Export citation  
     
    Bookmark   7 citations  
  • Generalized cohesiveness.Tamara Hummel & Carl Jockusch - 1999 - Journal of Symbolic Logic 64 (2):489-516.
    We study some generalized notions of cohesiveness which arise naturally in connection with effective versions of Ramsey's Theorem. An infinite set A of natural numbers is n-cohesive (respectively, n-r-cohesive) if A is almost homogeneous for every computably enumerable (respectively, computable) 2-coloring of the n-element sets of natural numbers. (Thus the 1-cohesive and 1-r-cohesive sets coincide with the cohesive and r-cohesive sets, respectively.) We consider the degrees of unsolvability and arithmetical definability levels of n-cohesive and n-r-cohesive sets. For example, we show (...)
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • Maximal Towers and Ultrafilter Bases in Computability Theory.Steffen Lempp, Joseph S. Miller, André Nies & Mariya I. Soskova - 2023 - Journal of Symbolic Logic 88 (3):1170-1190.
    The tower number ${\mathfrak t}$ and the ultrafilter number $\mathfrak {u}$ are cardinal characteristics from set theory. They are based on combinatorial properties of classes of subsets of $\omega $ and the almost inclusion relation $\subseteq ^*$ between such subsets. We consider analogs of these cardinal characteristics in computability theory.We say that a sequence $(G_n)_{n \in {\mathbb N}}$ of computable sets is a tower if $G_0 = {\mathbb N}$, $G_{n+1} \subseteq ^* G_n$, and $G_n\smallsetminus G_{n+1}$ is infinite for each n. (...)
    Download  
     
    Export citation  
     
    Bookmark  
  • On the Indecomposability of $\omega^{n}$.Jared R. Corduan & François G. Dorais - 2012 - Notre Dame Journal of Formal Logic 53 (3):373-395.
    We study the reverse mathematics of pigeonhole principles for finite powers of the ordinal $\omega$ . Four natural formulations are presented, and their relative strengths are compared. In the analysis of the pigeonhole principle for $\omega^{2}$ , we uncover two weak variants of Ramsey’s theorem for pairs.
    Download  
     
    Export citation  
     
    Bookmark  
  • Dominating the Erdős–Moser theorem in reverse mathematics.Ludovic Patey - 2017 - Annals of Pure and Applied Logic 168 (6):1172-1209.
    Download  
     
    Export citation  
     
    Bookmark  
  • The computational content of intrinsic density.Eric P. Astor - 2018 - Journal of Symbolic Logic 83 (2):817-828.
    Download  
     
    Export citation  
     
    Bookmark   1 citation  
  • Partition theorems and computability theory.Joseph R. Mileti - 2005 - Bulletin of Symbolic Logic 11 (3):411-427.
    The connections between mathematical logic and combinatorics have a rich history. This paper focuses on one aspect of this relationship: understanding the strength, measured using the tools of computability theory and reverse mathematics, of various partition theorems. To set the stage, recall two of the most fundamental combinatorial principles, König's Lemma and Ramsey's Theorem. We denote the set of natural numbers by ω and the set of finite sequences of natural numbers by ω<ω. We also identify each n ∈ ω (...)
    Download  
     
    Export citation  
     
    Bookmark   8 citations  
  • Weaker cousins of Ramsey's theorem over a weak base theory.Marta Fiori-Carones, Leszek Aleksander Kołodziejczyk & Katarzyna W. Kowalik - 2021 - Annals of Pure and Applied Logic 172 (10):103028.
    Download  
     
    Export citation  
     
    Bookmark   2 citations  
  • Degrees bounding principles and universal instances in reverse mathematics.Ludovic Patey - 2015 - Annals of Pure and Applied Logic 166 (11):1165-1185.
    Download  
     
    Export citation  
     
    Bookmark   3 citations  
  • (2 other versions)2000 Annual Meeting of the Association for Symbolic Logic.A. Pillay, D. Hallett, G. Hjorth, C. Jockusch, A. Kanamori, H. J. Keisler & V. McGee - 2000 - Bulletin of Symbolic Logic 6 (3):361-396.
    Download  
     
    Export citation  
     
    Bookmark  
  • (1 other version)Low sets without subsets of higher many-one degree.Patrizio Cintioli - 2011 - Mathematical Logic Quarterly 57 (5):517-523.
    Given a reducibility ⩽r, we say that an infinite set A is r-introimmune if A is not r-reducible to any of its subsets B with |A\B| = ∞. We consider the many-one reducibility ⩽m and we prove the existence of a low1 m-introimmune set in Π01 and the existence of a low1 bi-m-introimmune set.
    Download  
     
    Export citation  
     
    Bookmark  
  • Jump inversions inside effectively closed sets and applications to randomness.George Barmpalias, Rod Downey & Keng Meng Ng - 2011 - Journal of Symbolic Logic 76 (2):491 - 518.
    We study inversions of the jump operator on ${\mathrm{\Pi }}_{1}^{0}$ classes, combined with certain basis theorems. These jump inversions have implications for the study of the jump operator on the random degrees—for various notions of randomness. For example, we characterize the jumps of the weakly 2-random sets which are not 2-random, and the jumps of the weakly 1-random relative to 0′ sets which are not 2-random. Both of the classes coincide with the degrees above 0′ which are not 0′-dominated. A (...)
    Download  
     
    Export citation  
     
    Bookmark   1 citation