# FOM: Erdos Probabilistic Method: Logical Status?

Robert Tragesser RTragesser at compuserve.com
Sat Dec 2 06:07:53 EST 2000

```To: FOM
RE: Erdos Probabilistic Method: Logical Status?

I have some questions about the logical cum
foundational status of the Erdos/Renyi "Proba-
bilisitc method",--

In Aigler/Ziegler's _Proofs from The Book_, Chapt. 30
'Probability makes counting (sometimes) easy". says
that it is devoted to what is possibly Paul Erdo"s'
"most lasting legacy" _the probabilistic method_,
which they state "in the simplest way" as,

"IF, IN A GIVEN SET OF OBJECTS, THE PROBABILITY THAT
AN OBJECT DOES NOT HAVE A CERTAIN PROPERTY P IS LESS
THAN 1, THEN THERE MUST EXIST AN OBJECT WITH THIS
PROPERTY."

In the 1974, Erdos/Spencer _Probabilistic Methods in
Combinatorics_, the method is called 'the probabilistic
or the nonconstructive method'(p.9).  They subsequently remark
of "the nonconstructive method" (p.10),

"A SIMILARITY EXISTS BETWEEN THE NONCONSTRUCTIVE METHOD
AND THE USE OF _THE AXIOM OF CHOICE_. ONE MIGHT EVEN
THINK OF THE NONCONSTRUCTIVE METHOD AS A FINITISTIC
ANALOGUE OF _THE AXIOM OF CHOICE_ . . ." and they go
on to explain that since there are only finite sets
at issue, the object proved to exist can always in
principle be obtained albeit "laboriously" so that "unlike
the Axiom of Choice, there are no logical difficulties."

MY QUESTIONS:
(1) Is it just drama or a genuine philosophical point that
inspires the definite article 'the', when they say 'the
nonconstructive method'?
(2) Is it right what I think, that "the Probabilistic Method"
does not involve any essentially new logical idea? Otherwise
put (?), what is the reverse mathematics of the Probabilistic
Method? [Is it appropriate to ask this last? Aigner/Ziegler do
seem to think that "the Probabilistic Method" can be captured
in a principle or a family of principles.]
(3) If it doesn't involve any essentially novel logical ideas,
it in any case surely involves novel methodical ideas.  If this
is so, I am wondering how one ought to go about evaluating the
foundational/philosophical significance of methodological ideas?
I think of this as much as question about what an essentially
new logical idea might be? I think that I might raise the question
about, say, "Cohen's Method of Forcing"?--Does it involve an
essentially new logical idea? If not, how do we determine its logical
status? Is it coded as a principle on which reverse mathematics can
act? In any case, if it does not involve an essentially new logical
idea, what ought we to say about its philosophical/foundational
status?
_Nota Bene_: I am not at all prepared to elaborate what is meant
by "new logical idea" or even "logical idea", though I am prepared
to have the opinion that Axioms of Comprehension and Axioms of Choice
might serve as examples of essentially new logical ideas (?).  Otherwise
put, Wouldn't it be in bad faith that a logician with foundational
interests would claim to not have a clue to what cogent sense could
be assigned to "new logical idea"?

(4) What is the reverse mathematics of "the Pigeonhole Principle?"
[E.g., "For n >k, if n objects are distributed among k distinct places,
then at least one place will have more than one of those n objects
distributed to it."]

robert tragesser
westbrook, connecticut
rtragesser at hotmail.com

-------------------- End Forwarded Message --------------------

```