FOM: Chaitin vs Friedman

[Stephen G Simpson]

Raatikainen Panu A K, Wed, 21 Mar 2001 12:08:16 +0200:

 > There are two somewhat different results by Chaitin:
   ...

 > As I have (carefully) formulated them here, above results are just 
 > fine. What is problematic are the ambitious (fantastic?) 
 > philosophical conclusions one has drawn from them. 

Yes.  Thank you for making these points.  Chaitin's results are not
without interest, but claims about their philosophical/foundational
significance are greatly exaggerated.

Speaking of Chaitin's c, Raatikainen says:

 > there are codings such that theories with highly different power
 > (say, Q and ZFC) have the same finite limit. Also, the size and
 > complexity of F are quite irrelevant.
 ...

 > For every theory, there is indeed a finite limit, but that is all -
 > the value of this finite limit does not reflect any natural or
 > interesting property of F.

Yes.  

Now clearly there is a serious foundational/philosophical problem
here.  A crude attempt at formulating the problem:

 (*) For well known foundational theories F (e.g. F = PA, Z_2, ZFC,
     ZFC + a large cardinal axiom, etc), find versions of the
     incompleteness phenomenon, e.g., mathematically natural
     statements independent of F, which are sensitive to F.

I invite other FOM participants to give a sharper formulation.

Obviously (*) is a key f.o.m. problem -- some would say THE key
f.o.m. problem.  And this problem seems extremely difficult.  G"odel's
independent statements, Con(F), do not have the required properties,
nor do Chaitin's statements K(n) > c.  The Paris/Harrington theorem is
a well-known major contribution to (*).

Many people underestimate the difficulty of (*) and overestimate
Chaitin's contributions to it.  For example, the New Scientist article
at

   http://www.newscientist.com/features/features.jsp?id=ns22811

is loaded with overblown hype.

Harvey Friedman's recent Boolean relation theory is a direct assault
on (*).  In my estimation this work of Harvey is much deeper and
better than anything Chaitin has done, and it goes much farther than
Paris/Harrington.  Details are in Harvey's numbered FOM posting #100
of today, Wed, 21 Mar 2001 11:29:43 -0500.

On the one hand, it is good that serious f.o.m. issues have attracted
so much attention in the popular press.  On the other hand, it is
unfortunate that these issues are so badly misunderstood.

-- Steve