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