×

A weak variant of Hindman’s theorem stronger than Hilbert’s theorem. (English) Zbl 1384.03094

Summary: J. L. Hirst [Arch. Math. Logic 51, No. 1–2, 123–125 (2012; Zbl 1239.03038)] investigated a natural restriction of Hindman’s finite sums theorem – called Hilbert’s theorem – and proved it equivalent over \(\mathbf {RCA}_0\) to the infinite pigeonhole principle for all colors. This gave the first example of a natural restriction of Hindman’s theorem provably much weaker than Hindman’s theorem itself. We here introduce another natural restriction of Hindman’s theorem – which we name the adjacent Hindman’s theorem with apartness – and prove it to be provable from Ramsey’s theorem for pairs and strictly stronger than Hirst’s Hilbert’s theorem. The lower bound is obtained by a direct combinatorial implication from the adjacent Hindman’s theorem with apartness to the increasing polarized Ramsey’s theorem for pairs introduced by D. D. Dzhafarov and J. L. Hirst [Arch. Math. Logic 48, No. 2, 141–157 (2009; Zbl 1172.03007)]. In the adjacent Hindman’s theorem homogeneity is required only for finite sums of adjacent elements.

MSC:

03B30 Foundations of classical theories (including reverse mathematics)
05D10 Ramsey theory
03F35 Second- and higher-order arithmetic and fragments
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Blass, A.: Some questions arising from Hindman’s Theorem. Sci. Math. Jpn. 62, 331-334 (2005) · Zbl 1084.05008
[2] Blass, A.R., Hirst, J.L., Simpson, S.G.: Logical analysis of some theorems of combinatorics and topological dynamics. In: Logic and Combinatorics (Arcata, Calif., 1985), Contemp. Math., vol. 65, pp. 125-156. American Mathematical Society, Providence, RI (1987) · Zbl 1061.05095
[3] Carlucci, L.: “Weak yet strong” restrictions of Hindman’s Finite Sums Theorem. Proc. Am. Math. Soc. (to appear) · Zbl 1477.03174
[4] Carlucci, L., Kołodziejczyk, L. A., Lepore, F., Zdanowski, K.: New bounds on the strength of some restrictions of Hindman’s Theorem. In: Kari, J., Manea, F., Petre, I. (eds.) Unveiling Dynamics and Complexity, 13th Conference Computability in Europe 2017 (Turku, Finland, June 12-16, 2017), Springer, pp. 210-220 (2017) · Zbl 1496.03242
[5] Cholak, P., Jockusch, C.G., Slaman, T.: On the strength of Ramsey’s Theorem for pairs. J. Symb. Log. 66(1), 1-55 (2001) · Zbl 0977.03033 · doi:10.2307/2694910
[6] Chong, C.T., Lempp, S., Yang, Y.: On the role of the collection principle for \[\Sigma^0_2\] Σ20 formulas in second-order reverse mathematics. Proc. Am. Math. Soc. 138, 1093-1100 (2010) · Zbl 1195.03015 · doi:10.1090/S0002-9939-09-10115-6
[7] Chong, C.T., Slaman, T.A., Yang, Y.: The metamathematics of the Stable Ramsey’s Theorem for Pairs. J. Am. Math. Soc. 27, 863-892 (2014) · Zbl 1341.03015 · doi:10.1090/S0894-0347-2014-00789-X
[8] Dzhafarov, D.D., Hirst, J.L.: The polarized Ramsey’s theorem. Arch. Math. Log. 48(2), 141-157 (2011) · Zbl 1172.03007 · doi:10.1007/s00153-008-0108-0
[9] Dzhafarov, D., Jockusch, C., Solomon, R., Westrick, L.B.: Effectiveness of Hindman’s Theorem for bounded sums. In: Day, A., Fellows, M., Greenberg, N., Khoussainov, B., Melnikov, A. (eds.) Proceedings of the International Symposium on Computability and Complexity (in Honour of Rod Downey’s 60th birthday). Lecture Notes in Computer Science, pp. 134-142. Springer (2017) · Zbl 1480.03005
[10] Hindman, N.: The existence of certain ultrafilters on \[NN\] and a conjecture of Graham and Rothschild. Proc. Am. Math. Soc. 36(2), 341-346 (1972) · Zbl 0225.10056
[11] Hindman, N.: Finite sums from sequences within cells of a partition of N. J. Comb. Theory Ser. A 17, 1-11 (1974) · Zbl 0285.05012 · doi:10.1016/0097-3165(74)90023-5
[12] Hindman, N., Leader, I., Strauss, D.: Open problems in partition regularity. Comb. Probab. Comput. 12, 571-583 (2003) · Zbl 1061.05095 · doi:10.1017/S0963548303005716
[13] Hirst, J.: Hilbert vs Hindman. Arch. Math. Log. 51(1-2), 123-125 (2012) · Zbl 1239.03038 · doi:10.1007/s00153-011-0257-4
[14] Kołodziejczyk, L.A., Michalewski, H., Pradic, P., Skrzypczak, M.: The logical strength of Büchi’s decidability theorem. In: Reigner, L., Talbot, J.-M. (eds.) Proceedings of Computer Science Logic 2016, CSL 2016, August 29 to September 1, 2016, Marseille, France. Leibniz International Proceedings in Informatics, pp. 36:1-36:16. Dagstuhl Publishing (2016) · Zbl 1370.03058
[15] Montalbán, A.: Open questions in reverse mathematics. Bull. Symb. Log. 17(3), 431-454 (2011) · Zbl 1233.03023 · doi:10.2178/bsl/1309952320
[16] Patey, L., Yokoyama, K.: The proof theoretic strength of Ramsey’s Theorem for pairs. Preprint (2016) · Zbl 1469.03033
[17] Simpson, S.G.: Subsystems of Second Order Arithmetic. Perspectives in Logic, 2nd edn. Cambridge University Press, Cambridge (2009) · doi:10.1017/CBO9780511581007
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.