[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...

Best

Panu



-- 
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
Finland

E-mail: panu.raatikainen at helsinki.fi

http://www.mv.helsinki.fi/home/praatika/



More information about the FOM mailing list