[FOM] Inconsistency of P
Monroe Eskew
meskew at math.uci.edu
Mon Oct 3 00:15:56 EDT 2011
On Sun, Oct 2, 2011 at 10:44 AM, Panu Raatikainen
<panu.raatikainen at helsinki.fi> wrote:
>
> If c is the constant provided by Chaitin's theorem (for T), then yes,
>
> If T proves K(n)>c, for any n, then T is inconsistent.
>
> If a subtheory would prove K(n)>c, it is not necessarily inconsistent, but
> then it has to be severely limited theory, and must not be able to prove
> that a Turing machine halts (when that is in fact the case); i.e. it must
> fail to be Sigma_1 complete. That is, it must be more limited than e.g.
> Robinson arithmetic Q.
This is not correct. Suppose c is given by Chaitin's theorem. The
argument gives c as a number greater than the length of the following
program P:
Enumerate the proofs in T. When one is found of the statement
"K(n)>c" for some n, print "n" and halt.
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.
A counterexample can be given as follows. Let T be the set of all
sentences in the language of PA. Let c be a large number. For some
n, PA does not prove "K(n) \leq c." Let S be PA + "K(n)>c". Now
arrange the enumeration of the proofs of T so that the Chaitin machine
finds the proof in T of "K(0)>c" first and outputs 0. We can choose c
such that the length of this program is less than c. S is a
consistent, Sigma_1-complete subtheory of T which proves K(n)>c (and
does not prove K(0)>c), where c is given by Chaitin's theorem for T.
A cheap counterexample can be given by the following. Let T be as
above. Any choice for c will make the following sentence vacuously
true: "If T proves K(n)>c, for any n, then T is inconsistent."
Therefore find n and c such that PA proves K(n)>c.
Best,
Monroe
More information about the FOM
mailing list