On the strength of Ramsey's theorem

DOI10.1305/NDJFL/1040136917zbMATH Open0843.03034OpenAlexW2016125425MaRDI QIDQ1913632FDOQ1913632

Authors: David Seetapun, Theodore A. Slaman 

Publication date: 22 May 1996

Published in: Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1305/ndjfl/1040136917

Recommendations

• The inductive strength of Ramsey's theorem for pairs
• On the strength of Ramsey's theorem for pairs
• The proof-theoretic strength of Ramsey's theorem for pairs and two colors
• Ramsey's theorem for pairs and provably recursive functions

zbMATH Keywords

Ramsey's theorem for pairsfirst order arithmeticcomprehension scheme

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30)

Cites Work

• Title not available (Why is that?)
• Classes of Recursively Enumerable Sets and Degrees of Unsolvability
• Title not available (Why is that?)
• A criterion for completeness of degrees of unsolvability
• Title not available (Why is that?)
• The Baire category theorem in weak subsystems of second-order arithmetic
• The theory of \(\kappa\)-like models of arithmetic

Cited In (91)

• Computing sets from all infinite subsets
• Reverse mathematics and a Ramsey-type König's lemma
• On the indecomposability of \(\omega^n\)
• The definability strength of combinatorial principles
• On the strength of Ramsey's theorem for pairs
• Title not available (Why is that?)
• The polarized Ramsey's theorem
• \(\mathsf{RT}_{2}^{2}\) does not imply \(\mathsf{WKL}_{0}\)
• Strong reductions between combinatorial principles
• On the uniform computational content of Ramsey's theorem
• Dickson's lemma and weak Ramsey theory
• Using Ramsey's theorem once
• A variant of Mathias forcing that preserves \(\mathsf{ACA}_0\)
• Some Questions in Computable Mathematics
• Automorphism groups of arithmetically saturated models
• The metamathematics of Stable Ramsey’s Theorem for Pairs
• In search of the first-order part of Ramsey's theorem for pairs
• Generics for computable Mathias forcing
• Some logically weak Ramseyan theorems
• Weaker cousins of Ramsey's theorem over a weak base theory
• Infinite dimensional proper subspaces of computable vector spaces
• Cone avoiding closed sets
• On the strength of Ramsey's theorem without \(\Sigma _{1}\)-induction
• Ramsey's theorem for pairs and \(k\) colors as a sub-classical principle of arithmetic
• Thin set theorems and cone avoidance
• Controlling iterated jumps of solutions to combinatorial problems
• Coloring the rationals in reverse mathematics
• Partition Theorems and Computability Theory
• Partial orders and immunity in reverse mathematics
• Term extraction and Ramsey's theorem for pairs
• The strength of Ramsey's theorem for coloring relatively large sets
• Forcing in Proof Theory
• Ramsey's theorem and cone avoidance
• The weakness of the pigeonhole principle under hyperarithmetical reductions
• Dominating the Erdős-Moser theorem in reverse mathematics
• \({\Pi^1_2}\)-comprehension and the property of Ramsey
• Rainbow Ramsey theorem for triples is strictly weaker than the arithmetical comprehension axiom
• Some upper bounds on ordinal-valued Ramsey numbers for colourings of pairs
• \(\varPi^1_1\)-conservation of combinatorial principles weaker than Ramsey's theorem for pairs
• Coloring trees in reverse mathematics
• \( \mathsf{SRT}_2^2\) does not imply \(\mathsf{RT}_2^2\) in \(\omega \)-models
• The coding power of a product of partitions
• Ramsey-like theorems and moduli of computation
• \(\Pi\frac12\)-comprehension and the property of Ramsey
• The strength of the rainbow Ramsey Theorem
• Pigeons do not jump high
• Thin set versions of Hindman's theorem
• Sets without subsets of higher many-one degree
• The strength of the tree theorem for pairs in reverse mathematics
• Book review of: D. R. Hirschfeldt, Slicing the truth. On the computable and reverse mathematics of combinatorial principles
• Peano Arithmetic and Hyper-Ramsey Logic
• Random reals, the rainbow Ramsey theorem, and arithmetic conservation
• The canonical Ramsey theorem and computability theory
• Ordinal analysis and the infinite Ramsey theorem
• The proof-theoretic strength of Ramsey's theorem for pairs and two colors
• Cohesive avoidance and strong reductions
• Genericity for Mathias forcing over general Turing ideals
• The weakness of being cohesive, thin or free in reverse mathematics
• Independence of Ramsey theorem variants using \(\varepsilon _0\)
• The thin set theorem for pairs implies DNR
• On the Ramseyan factorization theorem
• Open questions about Ramsey-type statements in reverse mathematics
• Ramsey theorem for pairs as a classical principle in intuitionistic arithmetic
• On the strength of Ramsey's theorem for trees
• Induction, bounding, weak combinatorial principles, and the homogeneous model theorem
• The inductive strength of Ramsey's theorem for pairs
• Ramsey's theorem for pairs and provably recursive functions
• Cohesive sets and rainbows
• Title not available (Why is that?)
• Ramsey's theorem and products in the Weihrauch degrees
• The strength of infinitary Ramseyan principles can be accessed by their densities
• On the logical strengths of partial solutions to mathematical problems
• 2008 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '08
• Where pigeonhole principles meet Koenig lemmas
• Relationships between computability-theoretic properties of problems
• 1998 European Summer Meeting of the Association for Symbolic Logic
• Effective versions of Ramsey's Theorem: Avoiding the cone above 0′
• A miniaturisation of Ramsey's theorem
• Unprovable Ramsey-type statements reformulated to talk about primes
• Erdős-Moser and \(I \Sigma_2\)
• Milliken’s Tree Theorem and Its Applications: A Computability-Theoretic Perspective
• (EXTRA)ORDINARY EQUIVALENCES WITH THE ASCENDING/DESCENDING SEQUENCE PRINCIPLE
• An inside/outside Ramsey theorem and recursion theory
• The strength of Ramsey's theorem for pairs over trees. I: Weak König's lemma
• The Ginsburg-Sands theorem and computability theory
• HOW STRONG IS RAMSEY’S THEOREM IF INFINITY CAN BE WEAK?
• Cappable CEA sets and Ramsey's theorem
• THE REVERSE MATHEMATICS OF THE THIN SET AND ERDŐS–MOSER THEOREMS
• A note on Ramsey theorems and Turing jumps
• The Paris-Harrington principle and second-order arithmetic -- bridging the finite and infinite Ramsey theorem
• The reverse mathematics of wqos and bqos

This page was built for publication: On the strength of Ramsey's theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1913632)