We present a natural restriction of Hindman’s Finite Sums Theorem that admits a simple combinatorial proof (one that does not also prove the full Finite Sums Theorem) and low computability-theoretic and proof-theoretic upper bounds, yet implies the existence of the Turing Jump, thus realizing the only known lower bound for the full Finite Sums Theorem. This is the first example of this kind. In fact we isolate a rich family of similar restrictions of Hindman’s Theorem with analogous properties

"Weak yet strong" restrictions of Hindman's Finite Sums Theorem / Carlucci, Lorenzo. - In: PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY. - ISSN 0002-9939. - STAMPA. - 146:(2018), pp. 819-829. [10.1090/proc/13856]

"Weak yet strong" restrictions of Hindman's Finite Sums Theorem

Lorenzo Carlucci
Primo
2018

Abstract

We present a natural restriction of Hindman’s Finite Sums Theorem that admits a simple combinatorial proof (one that does not also prove the full Finite Sums Theorem) and low computability-theoretic and proof-theoretic upper bounds, yet implies the existence of the Turing Jump, thus realizing the only known lower bound for the full Finite Sums Theorem. This is the first example of this kind. In fact we isolate a rich family of similar restrictions of Hindman’s Theorem with analogous properties
2018
Hindman's Theorem; Finite Sums; Reverse Mathematics
01 Pubblicazione su rivista::01a Articolo in rivista
"Weak yet strong" restrictions of Hindman's Finite Sums Theorem / Carlucci, Lorenzo. - In: PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY. - ISSN 0002-9939. - STAMPA. - 146:(2018), pp. 819-829. [10.1090/proc/13856]
File allegati a questo prodotto
File Dimensione Formato  
Carlucci_Weak_2018.pdf

accesso aperto

Tipologia: Documento in Post-print (versione successiva alla peer review e accettata per la pubblicazione)
Licenza: Creative commons
Dimensione 294.75 kB
Formato Unknown
294.75 kB Unknown
Carlucci_Weak yet strong_2018.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 198.81 kB
Formato Adobe PDF
198.81 kB Adobe PDF   Contatta l'autore

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/11573/1064194
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? 6
social impact