Is complexity a source of incompleteness?

DOI10.1016/J.AAM.2004.10.003MaRDI QIDQ2386137zbMATH OpenOpenAlexWikidataFDO

Authors Cristian S. Calude, Helmut Jürgensen

Publication date 22 August 2005

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0408144, https://hdl.handle.net/2292/3748

complexity measure complexity of a theory complexity of sentences Gödel numbering incompleteness unprovability

Complexity of proofs (03F20) Gödel numberings and issues of incompleteness (03F40) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Abstract: 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.

Recommendations

Cites work

Cited in

(25)

This page was built for publication: Is complexity a source of incompleteness?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2386137)