[FOM] Inconsistency of P

[Monroe Eskew]

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