We investigate the uniform computational content of the open and clopen Ramsey theorems in the Weihrauch lattice. While they are known to be equivalent to ATR_0 from the point of view of reverse mathematics, there is not a canonical way to phrase them as multivalued functions. We identify eight different multivalued functions (five corresponding to the open Ramsey theorem and three corresponding to the clopen Ramsey theorem) and study their degree from the point of view of Weihrauch, strong Weihrauch, and arithmetic Weihrauch reducibility. In particular one of our functions turns out to be strictly stronger than any previously studied multivalued functions arising from statements around ATR_0.

The open and clopen Ramsey theorems in the Weihrauch lattice

Alberto Marcone;Manlio Valenti
2021-01-01

Abstract

We investigate the uniform computational content of the open and clopen Ramsey theorems in the Weihrauch lattice. While they are known to be equivalent to ATR_0 from the point of view of reverse mathematics, there is not a canonical way to phrase them as multivalued functions. We identify eight different multivalued functions (five corresponding to the open Ramsey theorem and three corresponding to the clopen Ramsey theorem) and study their degree from the point of view of Weihrauch, strong Weihrauch, and arithmetic Weihrauch reducibility. In particular one of our functions turns out to be strictly stronger than any previously studied multivalued functions arising from statements around ATR_0.
File in questo prodotto:
File Dimensione Formato  
(ASL) The open and clopen Ramsey theorems in the Weihrauch lattice.pdf

accesso aperto

Descrizione: post-print
Tipologia: Documento in Post-print
Licenza: Creative commons
Dimensione 277.3 kB
Formato Adobe PDF
277.3 kB Adobe PDF Visualizza/Apri

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/11390/1195039
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact