Ramsey's theorem for pairs and k colors as a sub-classical principle of arithmetic

DOI10.1017/JSL.2016.41MaRDI QIDQ4977228zbMATH OpenOpenAlexFDO

Authors Stefano Berardi, Silvia Steila

Publication date 3 August 2017

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

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

zbMATH Keywords

intuitionistic arithmeticprinciple of omniscienceRamsey's theorem

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) First-order arithmetic and fragments (03F30) Intuitionistic mathematics (03F55) Ramsey theory (05D10)

Abstract: The purpose is to study the strength of Ramsey's Theorem for pairs restricted to recursive assignments of $k$-many colors, with respect to Intuitionistic Heyting Arithmetic. We prove that for every natural number $kgeq2$, Ramsey's Theorem for pairs and recursive assignments of $k$ colors is equivalent to the Limited Lesser Principle of Omniscience for $Sigm{a}_3^0$ formulas over Heyting Arithmetic. Alternatively, the same theorem over intuitionistic arithmetic is equivalent to: for every recursively enumerable infinite $k$-ary tree there is some $i<k$ and some branch with infinitely many children of index $i$.

Recommendations

• Ramsey theorem for pairs as a classical principle in intuitionistic arithmetic
• The proof-theoretic strength of Ramsey's theorem for pairs and two colors
• On the strength of Ramsey's theorem
• The strength of Ramsey's theorem for pairs over trees. I: Weak König's lemma
• The strength of Ramsey's theorem for pairs and arbitrarily many colors

Cites work

• An intuitionistic analysis of size-change termination
• An intuitionistic version of Ramsey's theorem and its use in program termination
• scientific article; zbMATH DE number 3446873 (Why is no real title available?)
• scientific article; zbMATH DE number 3237829 (Why is no real title available?)
• scientific article; zbMATH DE number 3291139 (Why is no real title available?)
• On the uniform computational content of Ramsey's theorem
• On uniform relationships between combinatorial problems
• Ramsey methods in analysis
• Ramsey theorem for pairs as a classical principle in intuitionistic arithmetic
• Ramsey's theorem and recursion theory
• Ramsey's theorem for pairs and provably recursive functions
• Stop when you are almost-full. Adventures in constructive termination
• The size-change principle for program termination

Cited in

(8)

• Ramsey theorem for pairs as a classical principle in intuitionistic arithmetic
• The strength of Ramsey's theorem for pairs and arbitrarily many colors
• Ramsey theorem as an intuitionistic property of well founded relations
• Refining the arithmetical hierarchy of classical principles
• Another proof of the intuitionistic Ramsey theorem
• A general constructive form of Higman's lemma
• Ramsey's theorem and König's lemma
• Ramsey's theorem for pairs and provably recursive functions

This page was built for publication: Ramsey's theorem for pairs and \(k\) colors as a sub-classical principle of arithmetic

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