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

[img]
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 .

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:

0022-4812

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

Actions (login required)

Edit item Edit item
Provide Feedback