[FOM] Inconsistency of P: two questions

Panu Raatikainen panu.raatikainen at helsinki.fi
Wed Oct 5 04:11:47 EDT 2011

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?



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