FOM: Erdos Probabilistic Method: Logical Status?

[Matthew Frank]

Robert Tragesser asked various questions about Erdos's probabilistic
method.

> (1) Is it just drama or a genuine philosophical point that inspires
> the definite article 'the', when [Aigler and Ziegler] say 'the
> nonconstructive method'?

Just drama.


> (2) "the Probabilistic Method" does not involve any essentially new
> logical idea

I agree.


> (3) If [the probabilistic] doesn't involve any essentially novel
> logical ideas, it in any case surely involves novel methodical ideas.

I'm not sure that the method is so novel.  Lebesgue worried about similar
issues by the 1910s, showing how to construct elements of sets of positive
measure, and considering an example where this was non-trivial.  (I just
found out about this over the summer, so hopefully I remember it right:  
Consider the set of reals between 0 and 1 whose decimal expansions contain
all decimal digits equally often in the limit.  Lebesgue considered the
set of reals whose expansions have this equidistribution property not just
in base 10, but in any base.)

My impression is that Erdos's use of the probabilistic method is
remarkable for the concreteness and virtuosity of his applications.
Regardless of whether the method was new with him, many people took up
the method because of his inspiration.


> I am wondering how one ought to go about evaluating the
> foundational/philosophical significance of methodological ideas

One way, as you suggest, is to codify the principles in second-order
arithmetic and find their status in the reverse math hierarchy.  But, even
if one is committed to a formal analysis of methodological significance,
this is only one approach--reverse mathematics is not the only formal
system with foundational aims!  Still, the pigeonhole principle will
probably be unproblematic in any formal system.


> (4) What is the reverse mathematics of "the Pigeonhole Principle?"

Since you ask...we formalize this as:
for every n,
for every function f: [1,n+1]->[1,n]
there exist distinct a,b less than n+2 with f(a)=f(b)

The following proof by induction on n contains only bounded quantifiers,
and so stays within the base theory RCA_0.

n=1 is trivial.
For the inductive step, say f: [1,n+2] -> [1,n+1].
If for all x, f(x) < n+1, then we restrict f to [1,n+1]
  and are done by inductive hypothesis
If there is exactly one x such that f(x)=n+1, then
  consider f': [1,n+1] -> [1,n] defined by
    f'(x) = f(x) if f(x) is not n+1
            f(n+2) if f(x) = n+1
  Then by applying the inductive hypothesis to f',
  (and a slight analysis of cases) we can find the desired a and b.
If there are two x's such that f(x)=n+1, then we are done.


What I'd like to know about the pigeonhole principle is:  when did it come
to be associated with pigeons?

--Matt