[FOM] Inconsistency of P
panu.raatikainen at helsinki.fi
Mon Oct 3 23:32:27 EDT 2011
Lainaus "Monroe Eskew" <meskew at math.uci.edu>:
> 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.
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 T.
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
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