[FOM] Inconsistency of P

Panu Raatikainen panu.raatikainen at helsinki.fi
Mon Oct 3 00:49:27 EDT 2011

"Monroe Eskew" <meskew at math.uci.edu>:

> Suppose S is a subtheory of T, and n is such that S proves K(n)>c.
> Then P outputs some m, where m is the *first* one seen by P, not
> necessarily equal to n.  Hence, T proves K(m)<c and K(m)>c, so it is
> inconsistent.  Now if S is sufficiently strong (so that it is Sigma_1
> complete), then S proves K(m)<c.  However, this does not mean that S
> proves K(n)<c, because the witness showing K(m)<c is a proof in T, not
> necessarily in S.  So it might take a more complex program to actually
> output n.  The Chaitin machine for S could work, but this might be
> longer than c.

"K(n)<c" is a Sigma_1 sentence.

If "K(n)<c" is true, and S is Sigma_1 complete, then S proves  
"K(n)<c". Period.

That is what Sigma_1 completeness is.

I am afraid I fail to see how any involved Chaitin machine  
considerations (or whatever) could change that...



Panu Raatikainen

Ph.D., University Lecturer
Docent in Theoretical Philosophy

Theoretical Philosophy
Department of Philosophy, History, Culture and Art Studies
P.O. Box 24  (Unioninkatu 38 A)
FIN-00014 University of Helsinki

E-mail: panu.raatikainen at helsinki.fi


More information about the FOM mailing list