The proof-theoretic strength of Ramsey's theorem for pairs and two colors

DOI10.1016/j.aim.2018.03.035zbMath1469.03033arXiv1601.00050OpenAlexW2964070035MaRDI QIDQ1644984

Keita Yokoyama, Ludovic Patey

Publication date: 22 June 2018

Published in: Advances in Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1601.00050

zbMATH Keywords

reverse mathematicsproof-theoretic strengthRamsey's theorem

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Ramsey theory (05D10) Nonstandard models of arithmetic (03H15) Models of arithmetic and set theory (03C62) Applications of computability and recursion theory (03D80) Second- and higher-order arithmetic and fragments (03F35)

Related Items

An inside/outside Ramsey theorem and recursion theory, Reverse mathematical bounds for the termination theorem, 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, HOW STRONG IS RAMSEY’S THEOREM IF INFINITY CAN BE WEAK?, The Paris-Harrington principle and second-order arithmetic -- bridging the finite and infinite Ramsey theorem, Some upper bounds on ordinal-valued Ramsey numbers for colourings of pairs, (EXTRA)ORDINARY EQUIVALENCES WITH THE ASCENDING/DESCENDING SEQUENCE PRINCIPLE, Weaker cousins of Ramsey's theorem over a weak base theory, A weak variant of Hindman's theorem stronger than Hilbert's theorem, Where pigeonhole principles meet Koenig lemmas, THE STRENGTH OF RAMSEY’S THEOREM FOR PAIRS AND ARBITRARILY MANY COLORS, The strength of Ramsey’s theorem for pairs over trees: I. Weak König’s Lemma, In search of the first-order part of Ramsey's theorem for pairs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Reverse mathematical bounds for the termination theorem
• Primitive recursion and the chain antichain principle
• \(\varPi^1_1\)-conservation of combinatorial principles weaker than Ramsey's theorem for pairs
• The inductive strength of Ramsey's theorem for pairs
• Ramsey's theorem for pairs and provably recursive functions
• Rapidly growing Ramsey functions
• Handbook of proof theory
• Ramsey methods in analysis
• Proof-theoretic analysis of termination proofs
• On the strength of Ramsey's theorem
• The strength of infinitary Ramseyan principles can be accessed by their densities
• More on lower bounds for partitioning \(\alpha\)-large sets
• Formalizing forcing arguments in subsystems of second-order arithmetic
• On the strength of Ramsey's theorem for pairs
• A Δ₂⁰ set with no infinite low subset in either it or its complement
• RT₂² does not imply WKL₀
• THE DEFINABILITY STRENGTH OF COMBINATORIAL PRINCIPLES
• The metamathematics of Stable Ramsey’s Theorem for Pairs
• Slicing the Truth
• Iterative Forcing and Hyperimmunity in Reverse Mathematics
• Partition Theorems and Computability Theory
• Partitioning 𝛼–large sets: Some lower bounds
• Combinatorial principles weaker than Ramsey's Theorem for pairs
• Partial realizations of Hilbert's program
• An introduction to recursively saturated and resplendent models
• Some independence results for Peano arithmetic
• A classification of rapidly growing Ramsey functions
• Some combinatorics involving ξ-large sets
• Reverse mathematics and a Ramsey-type König's Lemma
• On the strength of Ramsey's theorem without Σ₁‐induction
• Random reals, the rainbow Ramsey theorem, and arithmetic conservation
• On the Ramseyan Factorization Theorem
• SEPARATING PRINCIPLES BELOW RAMSEY'S THEOREM FOR PAIRS
• ∏ 0 1 Classes and Degrees of Theories
• Ramsey's theorem and recursion theory
• Some remarks on the theory of graphs