Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

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


Author: Lorenzo Carlucci
Journal: Proc. Amer. Math. Soc. 146 (2018), 819-829
MSC (2010): Primary 03D80, 05P10; Secondary 03F35
DOI: https://doi.org/10.1090/proc/13856
Published electronically: September 28, 2017
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 03D80, 05P10, 03F35

Retrieve articles in all journals with MSC (2010): 03D80, 05P10, 03F35


Additional Information

Lorenzo Carlucci
Affiliation: Dipartimento di Informatica, Sapienza Università di Roma Via Ariosto 25, 00185 Rome, Italy
Email: carlucci@di.uniroma1.it

DOI: https://doi.org/10.1090/proc/13856
Received by editor(s): November 4, 2016
Received by editor(s) in revised form: March 29, 2017
Published electronically: September 28, 2017
Additional Notes: The work was done partially while the author was visiting the Institute for Mathematical Sciences, National University of Singapore in 2016. The visit was supported by the Institute.
Communicated by: Mirna Džamonja
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society