# [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?

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/