Is Complexity a Source of Incompleteness?

Details Is Complexity a Source of Incompleteness? Is Complexity a Source of Incompleteness?

2004-08-11

arxiv.org/abs/math/0408144v2

Mathematics

Logic

15 pages, improved version

Scientific paper

In this paper we prove Chaitin's ``heuristic principle'', {\it the theorems of a finitely-specified theory cannot be significantly more complex than the theory itself}, for an appropriate measure of complexity. We show that the measure is invariant under the change of the G\"odel numbering. For this measure, the theorems of a finitely-specified, sound, consistent theory strong enough to formalize arithmetic which is arithmetically sound (like Zermelo-Fraenkel set theory with choice or Peano Arithmetic) have bounded complexity, hence every sentence of the theory which is significantly more complex than the theory is unprovable. Previous results showing that incompleteness is not accidental, but ubiquitous are here reinforced in probabilistic terms: the probability that a true sentence of length $n$ is provable in the theory tends to zero when $n$ tends to infinity, while the probability that a sentence of length $n$ is true is strictly positive.

Affiliated with

Also associated with

No associations

Rating

Is Complexity a Source of Incompleteness? does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Is Complexity a Source of Incompleteness?, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Is Complexity a Source of Incompleteness? will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-208396