[FOM] response to Harvey's posting on the reverse mathematics of Hindman's Theorem

[Kreuzer, Alexander Philipp Sim]

Dear Harvey,
dear Henry,

> On 19 Sep 2015, at 00:59, Henry Towsner <htowsner at stanfordalumni.org> wrote:
>
> On Tue, Sep 1, 2015 at 1:51 AM, Harvey Friedman <hmflogic at gmail.com> wrote:
> Doesn't Towsner adapt the ultrafilter proof more or less in tact more
> or less lower than even Pi11-CA0? What do you think about the
> possibility of preserving the ultrafilter proof more or less in tact
> working in ACA_0+?
>
> The basic status of ultrafilters in reverse math, as I know it, goes as follows.  It turns out that it depends heavily on *how* the ultrafilters are used.  The first question you could ask is to simply have a nonprincipal ultrafilter; this implies ACA0 over RCA0 (basically because a nonprincipal ultrafilter can be easily used to prove Ramsey's Theorem), but is conservative over ACA0 (this follows from a result in Enayat, "From bounded arithmetic to second order arithmetic via automorphisms", and is proven separately by Kreuzer, "Non-principal ultrafilters, program extraction and higher-order reverse mathematics", and me "Ultrafilters in reverse mathematics").

In
"On idempotent ultrafilters in higher-order reverse mathematics, JSL 80 vol 1, 2015, http://dx.doi.org/doi:10.1017/jsl.2014.58
we were able to extend this to idempotent ultrafilters.
One gets that over ACA_0^w (the higher type extension of ACA_0) the existence of an idempotent ultrafilter is Pi12-conservative over the iterated Hindman's theorem
(which is equivalent to the Miliken-Tayler variant of Hindman's theorem and follows from ACA_0^+).


> A further class of results, largely unexamined in the reverse math literature, are those which use even more of the topology of the ultrafilters.  Most of these involve the minimal ideal---one can show that there is a minimal two-sided ideal in the space of ultrafilters, and specifically choose an idempotent ultrafilter from within this ideal.  The elements of such an ultrafilter are called "central sets" (I believe they were originally defined by Furstenberg with a definition based on their dynamical properties).  There are combinatorial characterizations, but they're fairly complicated.  (See Hindman and Strauss, "A simple characterization of sets satisfying the Central Sets Theorem".)  The are various results in this area one could investigate (most straightforwardly, proving that any finite coloring of the natural numbers has a monochromatic set satisfying the conclusion of the "central sets theorem", which is not known to be as strong as containing an actual central set; if I remember correctly, Hindman says in print somewhere that he does not expect his grandchildren to live to see a combinatorial proof of this result).

Actually, the statement that each finite coloring of N contains a monochromatic central set follows from the Auslander Ellis theorem (AET). In detail, Theorem 8.8 of H. Furstenberg: "Recurrence in ergodic theory and combinatorial number theory" should formalize in ACA0 + AET)
However, it is not clear if ACA0+AET also proves that each finite coloring of a _central set_ contains a monochromatic central set. (For Hindman’s theorem the corresponding statement follows by an easy combinatorial argument.)
In fact, this would be needed to give a conservativity result for minimal idempotent ultrafilters.
At http://arxiv.org/abs/1305.6530 is an old draft of mine discussing this problem.

Best,
Alexander
--
Alexander P. Kreuzer
NUS Singapore
www.math.nus.edu.sg/~matkaps/


________________________________

Important: This email is confidential and may be privileged. If you are not the intended recipient, please delete it and notify us immediately; you should not copy or use it for any purpose, nor disclose its contents to any other person. Thank you.