[FOM] Inconsistency of P

Panu Raatikainen 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. [1]

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 ;-) [1]

* * *

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.



[1] 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.

Panu Raatikainen

Ph.D., University Lecturer
Docent in Theoretical Philosophy

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 mailing list