Friday, January 20, 2006

Chaitin's limits of mathematics

Godel's incompleteness theorem says that if a formal axiomatic system that consistent and expressive enough to do arithmetic, then it will bite off more than it can it chew. That is, there will be formal propositions that the system is powerful enough to express, but not powerful enough to prove or disprove. In this sense, all interesting (read: consistent and sufficiently expressive) formal axiomatic systems are incomplete: they pose questions that can only be answered by more powerful systems.

So, formal mathematics is incomplete, but how incomplete is it? About fifty years after Godel's theorem, Gregory Chaitin gave a quantified answer to this question. You can read excellent, relatively nontechnical expositions by Chaitin on his results here and here. The gist of it is that if you can unambiguously describe a formal axiom system with N bits, then that system cannot compute more than N bits of the binary expansion of the halting probability.

Chaitin calls the bits of the halting probability "irreducible mathematical information" and "random." I agree with the former but not the latter. Yes, to compute more bits you need to add more axioms to your system, but you need not add axioms randomly. Set theorists have built an elaborate heirarchy of proposed new axioms; this heirarchy has a beautiful structure that is anything but random. One could claim that the truth of these new axioms is random. However, such a claim is inherently metaphysical, for it is impossible to produce empirical evidence directly for or against the axioms in question. (There is empirical evidence in favor of their consistency, but that's not the same as truth.) I don't know if Chaitin intends to make this metaphysical claim, and at any rate I can't disprove the claim, but I can say I find it implausible. "God does not play dice."

Okay, enough complaints for now. Chaitin argues that incompleteness implies that mathematicians needs to use experimentation to produce tentative axioms to use to prove theorems that cannot be deduced from of our currently accepted axioms. I agree wholeheartedly. That heirarchy of new set-theoretic axioms I mentioned earlier is believed (by most set-theorists) to be consistent essentially because no one has been able to deduce a contradiction from them (yet). In fact, for a few years many set theorists believed in the consistency of the existence of a Reinhardt cardinal, until a contradiction was deduced.


Post a Comment

Links to this post:

Create a Link

<< Home