FOM: Erdos Probabilistic Method: Logical Status?

[Kanovei]

> Date: Sat, 2 Dec 2000 06:07:53 -0500
> From: Robert Tragesser <RTragesser at compuserve.com>
 
> RE: Erdos Probabilistic Method: Logical Status?
....
> "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."
....
> "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_ . . ." 
 
The analogy between 

(1) the "nonconstructive method" of 
derivation of Ex A(x) from  mes {x:A(x)} > 0, and 

(2) the axiom of choice 

is not transparent. 
In the fully finite case (1) is just a form of the 
pigeonhole principle, in the infinite domain this can be, 
e.g., the case of Lebesgue measure or Baire category, where 
indeed countable choice is obligatory unless the   
objects are specified in such a way that the countable choice 
is eliminated by methods of descriptive set theory.

> might raise the question
> about, say, "Cohen's Method of Forcing"?--Does it involve an
> essentially new logical idea?  

As a matter of fact one of ideas behind the forcing is (1), 
in its Baire category version. 

> (4) What is the reverse mathematics of "the Pigeonhole Principle?"
 
I remember to once read a long Riis's preprint, where, in 
particular, it was demonstrated that the "PP" has rather  
nontrivial relations with restricted systems of PA. 

V.Kanovei