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.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.