[FOM] Inconsistency of P
meskew at math.uci.edu
Tue Oct 4 02:28:45 EDT 2011
I agree with everything you said in this latest message, as long as
you are assuming T is consistent. But I would like to emphasize that
your original claim-- that the hypothesized subtheory S must be very
weak-- is not correct. If S proves "K(n)>c" for some n, then we can
indeed conclude that T is inconsistent. But there need not be any
special deficiency of S in consistency, truth, or strength, since c
depends on T-- it is c(T), not c(S). This was Tao's main point. If
you are still not convinced, please provide some details of the
contrary argument you have in mind.
On Mon, Oct 3, 2011 at 8:32 PM, Panu Raatikainen
<panu.raatikainen at helsinki.fi> wrote:
> Look, forget witnesses, forget Chaitin machines, forget any particular way
> to demonstrate Chaitin's theorem!
> In the end of the day, what Chaitin's theorem says that given a theory T,
> there is a constant c such that T cannot prove "K(n)>c" for *any* natural
> number. 
> If S then really is a *subtheory* of T, it simply cannot prove "K(m)>c" for
> "some other m" - note the *any* above. If it can, it is not a subtheory of
> It is really that simple. And so is the relevant set too ;-) 
> * * *
> What is right is this:
> If we then *assume* (contrary to the fact; for the sake of the proof) that
> S, the subtheory, proves "K(n)>c", we may not be able to conclude that S is
> inconsistent - and in particular, not conclude on the basis of the standard
> proof of Chaitin's theorem.
>  The complement of "K(n)>c" is "simple" (in Post's sense); that is the
> reason behind the fact that you cannot prove "K(n)>c" for for *any* n.
More information about the FOM