[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/
More information about the FOM
mailing list