id: 06040394
dt: j
an: 06040394
au: Towsner, Henry
ti: A simple proof and some difficult examples for Hindman’s theorem.
so: Notre Dame J. Formal Logic 53, No. 1, 53-65 (2012).
py: 2012
pu: University of Notre Dame, Notre Dame, IN; Duke University Press, Durham, NC
la: EN
cc: 
ut: Hindman’s theorem; reverse mathematics; Ramsey theory
ci: Zbl 0652.03040
li: doi:10.1215/00294527-1626518 euclid:ndjfl/1336586237
ab: The author gives a new, simplified proof of Hindman’s theorem that
    formalizes in the system $\mathsf{ACA}^+$. This is slightly weaker than
    the best known upper bound $\mathsf{ACA}^+_0$ (note the subscript 0
    which indicates that induction is restricted to $Σ^0_1$ formulas) on
    the strength of Hindman’s theorem, see [{\it A. Blass}, {\it J.
    Hirst} and {\it S. Simpson}, “Logical analysis of some theorems of
    combinatorics and topological dynamics", Contemp. Math. 65, 125‒156
    (1987; Zbl 0652.03040)]. Moreover, the author introduces a technique to
    construct instances of Hindman’s theorem which have computationally
    difficult solutions. He uses this technique to show that parts of his
    new proof are optimal. Also, he constructs an instance which has no
    $Σ_2$ solutions. This improves the best known lower bound which was
    $Δ_2$. This research is connected to the long open problem to
    determine the precises strength, in the sense of reverse mathematics,
    of Hindman’s theorem.
rv: Alexander Kreuzer (Lyon)