[FOM] Inconsistency of P

Panu Raatikainen panu.raatikainen at helsinki.fi
Sun Oct 2 13:44:58 EDT 2011


Lainaus "Daniel Mehkeri" <dmehkeri at gmail.com>:


> Yes. To quickly clarify: as I understood it, the proof attempt was  
> relying on the fact that if T proves K(n)>m, then T is inconsistent.  
> If a subtheory of T proves K(n)>m, then it does not follow that the  
> subhteory is inconsistent.

I am no sure whether the last sentence is still supposed be a part of  
the proof attempt, or an independent statement of a fact?

(And I must say that I am not at all sure what exactly was the idea of  
the attempted proof - thing started to move much too fast for me in  
page 5 in Outline...)


Anyway:

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.



All the Best

Panu




-- 
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
Finland

E-mail: panu.raatikainen at helsinki.fi

http://www.mv.helsinki.fi/home/praatika/



More information about the FOM mailing list