[FOM] inconsistency of P

Edward Nelson nelson at math.Princeton.EDU
Wed Sep 28 12:02:10 EDT 2011

Thanks, Daniel Mehkeri, for the quote, and thanks, Shane Steinert-Threlkeld,
for the link to Terrence Tao's comments. There Tao writes:

> I have read through the outline. Even though it is too sketchy to count as a
> full proof, I think I can reconstruct enough of the argument to figure out
> where the error in reasoning is going to be. Basically, in order for
> Chaitin's theorem (10) to hold, the Kolmogorov complexity of the consistent
> theory T has to be less than \ell. But when one arithmetises (10) at a given
> rank and level on page 5, the complexity of the associated theory will
> depend on the complexity of that rank and level; because there are going to
> be more than 2^l ranks and levels involved in the iterative argument, at
> some point the complexity must exceed \ell, at which point Chaitin's theorem
> cannot be arithmetised for this value of \ell.
> (One can try to outrun this issue by arithmetising using the full strength
> of Q_0^*, rather than a restricted version of this language in which the
> rank and level are bounded; but then one would need the consistency of Q_0^*
> to be provable inside Q_0^*, which is not possible by the second
> incompleteness theorem.)
> I suppose it is possible that this obstruction could be evaded by a
> suitably clever trick, but personally I think that the FTL neutrino
> confirmation will arrive first.

Here are my comments on this:

So far as I know, the concept of the "Kolmogorov
complexity of a theory", as opposed to the Kolmogorov
complexity of a number, is undefined. Certainly it
does not occur in Chaitin's theorem or the Kritchman-Raz 

I work in a fixed theory Q_0^*. As Tao remarks, this
theory cannot prove its own consistency, by the second
incompleteness theorem. But this is not necessary.
The virtue of the Kritchman-Raz proof of that theorem
is that one needs only consider proofs of fixed rank
and level, and finitary reasoning leads to a contradiction.


Also, a member of FOM asked me, in a personal communication, 
to write a detailed proof (as opposed both to the sketch in
and to the completely formal proof barely begun in the work
in progress at http://www.math.princeton.edu/~nelson/books.html)
of the inconsistency of P. I am doing this, but it will take a 
few days. When finished, it will be at

A final comment: one can just treat the full proofs given by
the blue Proof hyperlinks as part of the text. They are proofs
so detailed than one can verify them without thinking. That
they were produced with the help of a software program is 

Ed Nelson

More information about the FOM mailing list