“Weak yet strong” restrictions of Hindman’s Finite Sums Theorem
HTML articles powered by AMS MathViewer
- by Lorenzo Carlucci PDF
- Proc. Amer. Math. Soc. 146 (2018), 819-829 Request permission
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
- Andreas Blass, Some questions arising from Hindman’s theorem, Sci. Math. Jpn. 62 (2005), no. 2, 331–334. MR 2179959
- Andreas R. Blass, Jeffry L. Hirst, and Stephen G. Simpson, Logical analysis of some theorems of combinatorics and topological dynamics, Logic and combinatorics (Arcata, Calif., 1985) Contemp. Math., vol. 65, Amer. Math. Soc., Providence, RI, 1987, pp. 125–156. MR 891245, DOI 10.1090/conm/065/891245
- A. T. Brauer, Über Sequenzen von Potenzresten, Sitz. Ber. Preuss. Akad. Wiss., Phys. -math. Klasse (1928), pp. 9–16.
- L. Carlucci. A weak variant of Hindman’s Theorem stronger than Hilbert’s Theorem, Archive for Mathematical Logic, to appear.
- Peter A. Cholak, Carl G. Jockusch, and Theodore A. Slaman, On the strength of Ramsey’s theorem for pairs, J. Symbolic Logic 66 (2001), no. 1, 1–55. MR 1825173, DOI 10.2307/2694910
- D. Dzhafarov, C. G. Jockusch, R. Solomon, and L. B. Westrick, Effectiveness of Hindman’s Theorem for bounded sums. In A. Day, M. Fellows, N. Greenberg, B. Khoussainov, and A. Melnikov, eds., Proceedings of the International Symposium on Computability and Complexity (in honour of Rod Downey’s 60th birthday), Lecture Notes in Computer Science, Springer, pp. 134–142. Springer (2017).
- Harvey Friedman and Stephen G. Simpson, Issues and problems in reverse mathematics, Computability theory and its applications (Boulder, CO, 1999) Contemp. Math., vol. 257, Amer. Math. Soc., Providence, RI, 2000, pp. 127–144. MR 1770738, DOI 10.1090/conm/257/04031
- Emanuele Frittaion, Brown’s lemma in second-order arithmetic, Fund. Math. 238 (2017), no. 3, 269–283. MR 3654099, DOI 10.4064/fm221-9-2016
- Ronald L. Graham, Bruce L. Rothschild, and Joel H. Spencer, Ramsey theory, Wiley-Interscience Series in Discrete Mathematics, John Wiley & Sons, Inc., New York, 1980. MR 591457
- Neil Hindman, The existence of certain ultra-filters on $N$ and a conjecture of Graham and Rothschild, Proc. Amer. Math. Soc. 36 (1972), 341–346. MR 307926, DOI 10.1090/S0002-9939-1972-0307926-0
- Neil Hindman, Finite sums from sequences within cells of a partition of $N$, J. Combinatorial Theory Ser. A 17 (1974), 1–11. MR 349574, DOI 10.1016/0097-3165(74)90023-5
- Neil Hindman, Imre Leader, and Dona Strauss, Open problems in partition regularity, Combin. Probab. Comput. 12 (2003), no. 5-6, 571–583. Special issue on Ramsey theory. MR 2037071, DOI 10.1017/S0963548303005716
- Denis R. Hirschfeldt, Slicing the truth, Lecture Notes Series. Institute for Mathematical Sciences. National University of Singapore, vol. 28, World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2015. On the computable and reverse mathematics of combinatorial principles; Edited and with a foreword by Chitat Chong, Qi Feng, Theodore A. Slaman, W. Hugh Woodin and Yue Yang. MR 3244278
- Jeffry L. Hirst, Hilbert versus Hindman, Arch. Math. Logic 51 (2012), no. 1-2, 123–125. MR 2864401, DOI 10.1007/s00153-011-0257-4
- Carl G. Jockusch Jr., Ramsey’s theorem and recursion theory, J. Symbolic Logic 37 (1972), 268–280. MR 376319, DOI 10.2307/2272972
- Antonio Montalbán, Open questions in reverse mathematics, Bull. Symbolic Logic 17 (2011), no. 3, 431–454. MR 2856080, DOI 10.2178/bsl/1309952320
- Hans Jürgen Prömel, Ramsey theory for discrete structures, Springer, Cham, 2013. With a foreword by Angelika Steger. MR 3157030, DOI 10.1007/978-3-319-01315-2
- Jon Henry Sanders, A GENERALIZATION OF SCHUR’S THEOREM, ProQuest LLC, Ann Arbor, MI, 1968. Thesis (Ph.D.)–Yale University. MR 2617864
- Y. Setyawan, Combinatorial number theory: Results of Hilbert, Schur, Folkman, and Hindman., Thesis (M.Sc.), Simon Fraser University, 1998.
- I. Schur, Über die Kongruenze $x^m+y^m \cong z^m (\mathrm {mod}\, p)$, Jber. Deutsch. Math.-Verein. 25 (1916), 114–117.
- Saharon Shelah, Primitive recursive bounds for van der Waerden numbers, J. Amer. Math. Soc. 1 (1988), no. 3, 683–697. MR 929498, DOI 10.1090/S0894-0347-1988-0929498-X
- Stephen G. Simpson, Subsystems of second order arithmetic, 2nd ed., Perspectives in Logic, Cambridge University Press, Cambridge; Association for Symbolic Logic, Poughkeepsie, NY, 2009. MR 2517689, DOI 10.1017/CBO9780511581007
- B. L. van der Waerden, Beweis einer Baudetschen Vermutung, Nieuw Arch. Wisk. 15 (1927), 212–216.
Additional Information
- Lorenzo Carlucci
- Affiliation: Dipartimento di Informatica, Sapienza Università di Roma Via Ariosto 25, 00185 Rome, Italy
- MR Author ID: 714329
- Email: carlucci@di.uniroma1.it
- 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
- © Copyright 2017 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 146 (2018), 819-829
- MSC (2010): Primary 03D80, 05P10; Secondary 03F35
- DOI: https://doi.org/10.1090/proc/13856
- MathSciNet review: 3731714