[FOM] Inconsistency of P
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
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...
Ph.D., University Lecturer
Docent in 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