On the strength of Ramsey's theorem for pairs

DOI10.2307/2694910zbMath0977.03033OpenAlexW2148962283MaRDI QIDQ2732267

Carl G. jun. Jockusch, Theodore A. Slaman, Peter A. Cholak

Publication date: 9 January 2002

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.366.5115

zbMATH Keywords

reverse mathematics computability conservation Ramsey's theorem recursion theory

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Models of arithmetic and set theory (03C62) Applications of computability and recursion theory (03D80) Second- and higher-order arithmetic and fragments (03F35) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items

Primitive recursive reverse mathematics, HOW STRONG IS RAMSEY’S THEOREM IF INFINITY CAN BE WEAK?, ALMOST THEOREMS OF HYPERARITHMETIC ANALYSIS, The Paris-Harrington principle and second-order arithmetic -- bridging the finite and infinite Ramsey theorem, The coding power of a product of partitions, Milliken’s Tree Theorem and Its Applications: A Computability-Theoretic Perspective, (EXTRA)ORDINARY EQUIVALENCES WITH THE ASCENDING/DESCENDING SEQUENCE PRINCIPLE, Cone avoiding closed sets, The strength of infinitary Ramseyan principles can be accessed by their densities, An inside/outside Ramsey theorem and recursion theory, Reverse Mathematics: The Playground of Logic, RT₂² does not imply WKL₀, More on lower bounds for partitioning \(\alpha\)-large sets, Open Questions in Reverse Mathematics, Reduction games, provability and compactness, Partial impredicativity in reverse mathematics, Reverse mathematical bounds for the termination theorem, The proof-theoretic strength of Ramsey's theorem for pairs and two colors, Term extraction and Ramsey's theorem for pairs, Computable Reductions and Reverse Mathematics, Partial Orders and Immunity in Reverse Mathematics, Reverse mathematics and the equivalence of definitions for well and better quasi-orders, The metamathematics of Stable Ramsey’s Theorem for Pairs, RELATIONSHIPS BETWEEN COMPUTABILITY-THEORETIC PROPERTIES OF PROBLEMS, RAMSEY-LIKE THEOREMS AND MODULI OF COMPUTATION, THE STRENGTH OF RAMSEY’S THEOREM FOR COLORING RELATIVELY LARGE SETS, Iterative Forcing and Hyperimmunity in Reverse Mathematics, NONSTANDARD MODELS IN RECURSION THEORY AND REVERSE MATHEMATICS, The uniform content of partial and linear orders, Dominating the Erdős-Moser theorem in reverse mathematics, Unifying the model theory of first-order and second-order arithmetic via \(\mathrm{WKL}_0^\ast\), Coloring trees in reverse mathematics, The reverse mathematics of non-decreasing subsequences, On the strength of the finite intersection principle, Cohesive sets and rainbows, Book review of: D. R. Hirschfeldt, Slicing the truth. On the computable and reverse mathematics of combinatorial principles, On the strength of Ramsey's theorem for trees, OPEN QUESTIONS ABOUT RAMSEY-TYPE STATEMENTS IN REVERSE MATHEMATICS, Ramsey’s theorem for singletons and strong computable reducibility, Infinite dimensional proper subspaces of computable vector spaces, Subsets coded in elementary end extensions, The thin set theorem for pairs implies DNR, A variant of Mathias forcing that preserves \(\mathsf{ACA}_0\), “Weak yet strong” restrictions of Hindman’s Finite Sums Theorem, Some upper bounds on ordinal-valued Ramsey numbers for colourings of pairs, Phase Transitions for Weakly Increasing Sequences, On the uniform computational content of computability theory, ON THE UNIFORM COMPUTATIONAL CONTENT OF RAMSEY’S THEOREM, Controlling iterated jumps of solutions to combinatorial problems, The maximal linear extension theorem in second order arithmetic, Induction, Bounding, Weak Combinatorial Principles, and the Homogeneous Model Theorem, Primitive recursion and the chain antichain principle, \(\varPi^1_1\)-conservation of combinatorial principles weaker than Ramsey's theorem for pairs, Effectiveness of Hindman’s Theorem for Bounded Sums, Weakly Represented Families in Reverse Mathematics, Some Questions in Computable Mathematics, Generics for computable Mathias forcing, Some logically weak Ramseyan theorems, On the role of the collection principle for Σ⁰₂-formulas in second-order reverse mathematics, Weaker cousins of Ramsey's theorem over a weak base theory, Degrees bounding principles and universal instances in reverse mathematics, Reverse mathematics and a Ramsey-type König's Lemma, SEPARATING PRINCIPLES BELOW RAMSEY'S THEOREM FOR PAIRS, The cohesive principle and the Bolzano-Weierstraß principle, On the logical strengths of partial solutions to mathematical problems, Genericity for Mathias forcing over general Turing ideals, The weakness of being cohesive, thin or free in reverse mathematics, A weak variant of Hindman's theorem stronger than Hilbert's theorem, The strength of the Grätzer-Schmidt theorem, The inductive strength of Ramsey's theorem for pairs, THE STRENGTH OF RAMSEY’S THEOREM FOR PAIRS AND ARBITRARILY MANY COLORS, The weakness of the pigeonhole principle under hyperarithmetical reductions, On the strength of Ramsey's theorem without Σ₁‐induction, Random reals, the rainbow Ramsey theorem, and arithmetic conservation, Ramsey's theorem for trees: the polarized tree theorem and notions of stability, From Bolzano‐Weierstraß to Arzelà‐Ascoli, On the indecomposability of \(\omega^n\), New bounds on the strength of some restrictions of Hindman's theorem, Reverse mathematics and Ramsey's property for trees, On the Equimorphism Types of Linear Orderings, Forcing in Proof Theory, The canonical Ramsey theorem and computability theory, On uniform relationships between combinatorial problems, Reverse mathematics, computability, and partitions of trees, 2008 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '08, Partition Theorems and Computability Theory, On a question of Andreas Weiermann, \( \mathsf{SRT}_2^2\) does not imply \(\mathsf{RT}_2^2\) in \(\omega \)-models, The polarized Ramsey's theorem, Ramsey's theorem and cone avoidance, Stability and posets, On a conjecture of Dobrinen and Simpson concerning almost everywhere domination, Automorphism groups of arithmetically saturated models, The atomic model theorem and type omitting, Pigeons do not jump high, INDECOMPOSABLE LINEAR ORDERINGS AND HYPERARITHMETIC ANALYSIS, The strength of the rainbow Ramsey Theorem, Corrigendum to: “On the strength of Ramsey's Theorem for pairs”, Cohesive avoidance and strong reductions, COH, SRT 2 2 , and multiple functionals, A packed Ramsey’s theorem and computability theory, Partitioning 𝛼–large sets: Some lower bounds, The strength of Ramsey’s theorem for pairs over trees: I. Weak König’s Lemma, Combinatorial principles weaker than Ramsey's Theorem for pairs, The modal logic of reverse mathematics, Rainbow Ramsey Theorem for Triples is Strictly Weaker than the Arithmetical Comprehension Axiom, Linear extensions of partial orders and reverse mathematics, In search of the first-order part of Ramsey's theorem for pairs

Cites Work