[FOM] 607: Hindman's Theorem

[Harvey Friedman]

[1] Henry Towsner, A Simple Proof of Hindman’s Theorem, June 21, 2009,
http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=806B28AAEDE5611117BEF5DE7B25D899?doi=10.1.1.249.1174&rep=rep1&type=pdf

[2] Henry Towsner, Hindman’s Theorem: An Ultrafilter Argument in
Second Order Arithmetic, Henry Towsner June 21, 2009,
http://arxiv.org/pdf/0906.3882v1.pdf

[3] Neil Hindman and Dona Strauss. Algebra in the Stone-Cˇech
compactification, volume 27 of de Gruyter Expositions in Mathematics.
Walter de Gruyter & Co., Berlin, 1998. Theory and applications.

[4] Jeffry L. Hirst. Hindman’s theorem, ultrafilters, and reverse
mathematics. J. Symbolic Logic, 69(1):65–72, 2004.

As Towsner  states in [2], there are three proofs before Towsner of
Hindman's Theorem (see below).

1. Hindman's original combinatorial proof. There is no deep pathology,
but the proof uses Pi12-TI0, an unusually hefty system.
2. Baumgartner's streamlined combinatorial proof. Again no deep
pathology, and uses ACA0+, a strong version of arithmetic
comprehension.
3. Glazer's proof, which uses a considerable amount of deep pathology.

Of course, the deep pathology in Glazer's idempotent ultrafilter proof
can be a priori removed using an absoluteness argument going back to
Goedel , since Hindman's theorem is Pi12. This argument removes any
use of the axiom of choice. However, that is logically horrifically
uneconomical, and mathematically unfriendly. But it does remove the
deeply pathological in explicitness by a sledgehammer.

[4] removes the deep pathology in Glazer's proof by using ultrafilters
on countable sets, but the argument uses more than Z_2.

[2] brings new ideas to [4], and gives a Glazer inspired proof living
lower than Pi11-CA0. Not as logically economical as the best known,

[1] gives a direct combinatorial proof that is simpler than all other
combinatorial proofs, inspired by [2], landing in the best known
ACA0+.

It appears to me that one thing that we want is to try to go further
and forge the Glazer's ultrafilter method into a systematic
combinatorial tool that ideally lives in some version of arithmetic
comprehension.

According to Towsner, there are many other uses of what I call deep
pathology to prove infinite combinatorial statements such as Hindman's
theorem, in [3]. Has there been a similar countable approximation
theory for these as well?

Also, I am under the impression that there are uses of deep pathology
in ergodic theory, involving the deeply pathological dual of
l_infinity and L^infinity. Can we forge a similar systematic  tool for
these ergodic theory applications? And what do the direct analysis
proofs look like?

HINDMAN'S THEOREM. In any coloring of the natural numbers by finitely
many colors, there is an infinite set of natural numbers, all of whose
nonempty finite sums have the same color.

Of course, in Invariant Borel Theory, Boolean Relation Theory,
Continuation/Emulation Theory, we don't use the deep pathology I have
been talking about, but something much more exotic, and not known to
mathematicians. And there, removal is demonstrably impossible.

************************************************************
My website is at https://u.osu.edu/friedman.8/ and my youtube site is at
https://www.youtube.com/channel/UCdRdeExwKiWndBl4YOxBTEQ
This is the 607th in a series of self contained numbered
postings to FOM covering a wide range of topics in f.o.m. The list of
previous numbered postings #1-599 can be found at the FOM posting
http://www.cs.nyu.edu/pipermail/fom/2015-August/018887.html

600: Removing Deep Pathology 1  8/15/15  10:37PM
601: Finite Emulation Theory 1/perfect?  8/22/15  1:17AM
602: Removing Deep Pathology 2  8/23/15  6:35PM
603: Removing Deep Pathology 3  8/25/15  10:24AM
604: Finite Emulation Theory 2  8/26/15  2:54PM
605: Integer and Real Functions  8/27/15  1:50PM
606: Simple Theory of Types  8/29/15  6:30PM

Harvey Friedman