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 , 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 and some branch with infinitely many children of index i.

Ramsey's theorem for pairs and K colors as a sub-classical principle of arithmetic

Berardi, Stefano;Steila, Silvia
2017-01-01

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 , 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 and some branch with infinitely many children of index i.
2017
82
2
737
753
http://journals.cambridge.org/action/displayBackIssues?jid=JSL
https://arxiv.org/abs/1601.01891
Intuitionistic arithmetic; Principle of Omniscience; Ramsey's Theorem; Philosophy; Logic
Berardi, Stefano; Steila, Silvia
File in questo prodotto:
File Dimensione Formato  
ramseys_theorem_for_pairs_and_k_colors_as_a_subclassical_principle_of_arithmetic.pdf

Accesso riservato

Tipo di file: PDF EDITORIALE
Dimensione 227.64 kB
Formato Adobe PDF
227.64 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Steila-RAMSEY’S THEOREM FOR k colors - JSL- 2016.pdf

Accesso riservato

Tipo di file: PDF EDITORIALE
Dimensione 250.41 kB
Formato Adobe PDF
250.41 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2318/1658138
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact