[FOM] Inconsistency of P: two questions

[Panu Raatikainen]

Especially for those who know (better than I do) the issues around the  
weak theories:

While going through the various steps in Nelson's sketch, a couple of  
questions, related to the Kritchman-Raz argument, occurred to me...
They might perhaps have some interest in themselves...

* * *

K(x) is obviously the Kolmogorov complexity of x.

Fix a theory T.

Let c be the limiting constant provided by Chaitin's theorem (for T);
thus T cannot prove K(n) > c, for any n.

Let \mu is  the number of integers 0 ≤  x ≤ 2^{c+1} such that K(x) > c.


Question 1:

One first appeals to the pigeonhole principle in order to demonstrate  
that 1 ≤ \mu, i.e. that there is at least one x ≤ 2^{c+1} such that  
K(x) > c.
- because there are fewer than 2^{c+1} Turing machines with at most c bits.

Is this application of the pigeonhole principle totally kosher? Is it  
available in all weak theories?



Question 2:

One then applies a form of induction to  \mu, using the above fact as  
the basis:

If \mu were 1, T would be able to prove, for some n, that K(n) > c.  
Contradiction. So \mu must be at least 2.


If \mu were 2, T would be able prove, for some n and m, that K(n) > c  
and K(m) > c. Contradiction.  So \mu must be at least 3.

etc. ...


Now I have some difficulties in seeing what exactly is the complexity  
(in terms of recursion-theoretic hierachies) of the property to which  
induction is applied to?

Is it a kind of induction that is available in the weak theories?



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/