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

Berardi, Stefano; Steila, Silvia (2017). Ramsey's Theorem for Pairs and k Colors as a Sub-Classical Principle of Arithmetic. The journal of symbolic logic, 82(02), pp. 737-753. Cambridge University Press 10.1017/jsl.2016.41

Preview

Text best16.pdf - Accepted Version Available under License Publisher holds Copyright. Download (375kB) | Preview

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 Σ 0 3 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 .

Interest & Impact

Downloads

324 since deposited on 18 Aug 2017
30 in the past 12 months

Citations

5 Citations in Web of Science ®
6 Citations in Scopus

Search

in Google Scholar™

Services

Actions (login required)

Edit item

Actions (login required)

Edit item