RAMSEY’S THEOREM FOR PAIRS ANDKCOLORS AS A SUB-CLASSICAL PRINCIPLE OF ARITHMETIC
Stefano Berardi, Silvia Steila · Journal of Symbolic Logic · 2017
Abstract The purpose is to study the strength of Ramsey’s Theorem for pairs restricted to recursive assignments ofk-many colors, with respect to Intuitionistic Heyting Arithmetic. We prove that for every natural number $k \ge 2$ , Ramsey’s Theorem for pairs and recursive assignments ofkcolors is equivalent to the Limited Lesser Principle of Omniscience for ${\rm{\Sigma }}_3^0$ formulas over Heyting Arithmetic. Alternatively, the same theorem over intuitionistic arithmetic is equivalent to: for every recursively enumerable infinitek-ary tree there is some $i < k$ and some branch with infinitely many children of indexi.