[FOM] Re: counting arguments?

[Stephen G Simpson]

Timothy Y. Chow 26 Oct 2003 writes:
 > 
 > Certainly, I have heard more than one practitioner of probabilistic
 > combinatorics claim something to the effect that some of the more
 > advanced probabilistic proofs "do not reduce to counting."

When you say "probabilistic combinatorics", what exactly are you
referring to?  Perhaps you mean topological/ergodic Ramsey theory, as
pioneered by H. Furstenberg.  This is quite different from
probabilistic existence proofs in finite combinatorics, as pioneered
by Erd"os.  When I said that it all boils down to counting, I was
referring to the Erd"os stuff, not the Furstenberg stuff.

 > What I think they mean is that they appeal to theorems that are
 > typically stated and proved in the context of general measure
 > theory.  A natural question from the f.o.m.  point of view is
 > whether these appeals to infinitary mathematics are a posteriori
 > eliminable.

Furstenberg et al use infinitistic methods in topological dynamics and
ergodic theory, including transfinite induction, to prove finitary
theorems, e.g., generalizations of Szemeredi's theorem.  Generally
speaking, it is not known whether the infinitistic methods are
eliminable.  This is a fascinating f.o.m. question that begs for
analysis in the style of reverse mathematics.  The surface has barely
been scratched.  Some specific questions and references are given in a
recent survey paper by me and Friedman on open problems in reverse
mathematics.

Stephen G. Simpson
Professor of Mathematics
Pennsylvania State University
http://www.math.psu.edu/simpson/