[FOM] Friedman on Urquhart on Corfield

[Stephen G Simpson]

David Corfield 21 Oct 2003 11:14:46 writes:

 > The existence of a mathematical object is established by proving
 > that the probability of its existence is positive. The technique
 > was first devised by Paul Erd"os. [...]

I think Corfield is referring to the probabilistic method in finite
combinatorics, as pioneered by Erd"os and expounded in the book by
Erd"os and Spencer.

For those unfamiliar with the method, I want to point out that
Corfield's description of it is seriously inaccurate.  One does not
prove that the probability of (exists x) P(x) is positive and then
infer (exists x) P(x).  (Such an inference would be invalid.)  Rather,
one computes the probability that P(x) holds, where x is a randomly
chosen element of a particular finite sample space S.  In other words,
one is computing the measure of P, where P is a particular subset of
S.  If the probability is positive, then (exists x) P(x) follows,
because any set of positive measure is necessarily nonempty.

Probabilistic existence proofs are non-constructive, in the sense that
the proof does not produce a specific x such that P(x) holds.  Thus,
the probabilistic method presents an obvious challenge for
f.o.m. researchers.  In general, constructivity is an important
f.o.m. issue, and the f.o.m. literature contains many interesting
results concerning non-constructive existence proofs and the
possibility of replacing them by constructive ones.
 
 > Rota calls for [...] a "new logic associated with probabilistic
 > reasoning" [...]

Recently Kerry Ojakian, a graduate student in f.o.m. at Carnegie
Mellon University, has obtained some results concerning the reverse
mathematics of the probabilistic method in finite combinatorics.  This
work is carried out in the context of bounded arithmetic.

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