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

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 kmany 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 kary tree there is some i < k and some branch with infinitely many children of index i .
Item Type: 
Journal Article (Original Article) 

Division/Institute: 
08 Faculty of Science > Institute of Computer Science (INF) > Logic and Theory Group (LTG) 08 Faculty of Science > Institute of Computer Science (INF) 
UniBE Contributor: 
Steila, Silvia 
Subjects: 
000 Computer science, knowledge & systems 500 Science > 510 Mathematics 
ISSN: 
00224812 
Publisher: 
Cambridge University Press 
Language: 
English 
Submitter: 
Lukas Jaun 
Date Deposited: 
18 Aug 2017 08:24 
Last Modified: 
18 Aug 2017 08:24 
Publisher DOI: 
10.1017/jsl.2016.41 
BORIS DOI: 
10.7892/boris.101443 
URI: 
https://boris.unibe.ch/id/eprint/101443 