[FOM] Inconsistency of P

[Monroe Eskew]

On Sun, Oct 2, 2011 at 11:47 PM, Panu Raatikainen
<panu.raatikainen at helsinki.fi> wrote:
>
>
> In any case, the essential point is that for all Sigma_1 complete theories,
> (simple) consistency equals to Pi_1 soundness, i.e. that the theory does not
> prove any false Pi_1 sentences.
>
> If, as in our original example, a theory T is inconsistent, because it
> proves  "K(n)>c" for some n, it must be that it proves *some* false Pi_1
> sentence F as a consequence.
>
> So if a subtheory S also proves "K(n)>c" but is consistent, it must either
> be Sigma_1 incomplete, or somehow block the derivation of F from  "K(n)>c".
>
> Right?


No, in my specific counterexample, I showed a situation in which
"K(n)>c" is actually a TRUE sentence, proven by a consistent S
extending PA, where (paradoxically?) c is actually the constant coming
from a Chaitin machine for a strictly larger theory T (the axioms of T
are a superset of the S axioms), where T is inconsistent.

The Chaitin machine does NOT witness that "K(n)>c" is false, because
the machine does not actually output n!  It outputs a different number
m that nonetheless comes from a proof in T of "K(m)>c," and the
machine itself witnesses the statement "K(m)<c," showing T
inconsistent.  There is no way to make the machine actually find first
the proof in S of "K(n)>c" and still have the program be shorter than
c, that is assuming S is a consistent extension of PA (or some other
consistent Sigma_1-complete theory of numbers), which it is in my
example (unless PA turns out inconsistent).

What we can say is that when S proves "K(n)>c," this choice of c must
necessarily be LESS than the "Chaitin constant for S," i.e. the one
given by making a Chaitin machine *for S*, and n must be hard to
describe in few words.  But it surely does exist because there are
only so many Turing machines of length bounded by c.  So find some n
such that K(n)>c is true, and add that to the PA axioms, getting S.

Best,
Monroe