Ramsey's Theorem for Pairs and k Colors as a Sub-Classical Principle of Arithmetic

2016/01/08 by Berardi, Stefano, Steila, Silvia
#03B30 #03F55 #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.1601.01891

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 k ≥ 2, Ramsey's Theorem for pairs and recursive assignments of k colors is equivalent to the Limited Lesser Principle of Omniscience for Σ⁰₃ 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.

Related

• The Strength of Ramsey's Theorem For Pairs over trees: I. Weak König's Lemma
• Coloring the rationals in reverse mathematics
• The proof-theoretic strength of Ramsey's theorem for pairs and two colors
• Erdos-Moser and ISigma₂
• Π⁰₄ conservation of Ramsey's theorem for pairs