# Chaitin's incompleteness theorem

20 views

### Aidan Rocke

Aug 12, 2021, 6:25:48 PM8/12/21
to Algorithmic Information Theory
Good evening AIT mailing list,

At present, most logicians I have discussed Chaitin's theorem with
interpret it in a very narrow sense. i.e. we can only prove finitely many
facts of the form K(x) > K(y).

However, I went over Chaitin's incompleteness theorem a few months ago
and a natural variation occurred to me which implies that there is a
Kolmogorov Complexity bound on Gödel numbers whose truth-value
is decidable. I think this makes the importance of the original theorem
clearer as it implies that there are only finitely many mathematical
propositions that are both true and formally provable.

In some sense, we are forced to choose between doing mathematics
with an unbounded number of propositions in an inconsistent manner
or doing rigorous math with a finite number of propositions and
experimental math with everything else. Might anyone in this mailing
list know of a publication which takes such an approach to Chaitin's
incompleteness theorem?

References:

1. Ncatlab. Chaitin Incompleteness theorem. https://ncatlab.org/nlab/show/Chaitin%27s+incompleteness+theorem
2. Gregory Chaitin. From Philosophy to Program Size. https://arxiv.org/abs/math/0303352
3. Gregory Chaitin. The Limits of Mathematics. 1994 (arXiv:chao-dyn/9407003)

Cheers,

Aidan Rocke

### John Tromp

Aug 13, 2021, 2:38:52 AM8/13/21
to Aidan Rocke, Algorithmic Information Theory
> At present, most logicians I have discussed Chaitin's theorem with
> interpret it in a very narrow sense. i.e. we can only prove finitely many
> facts of the form K(x) > K(y).

That's wrong. For sufficiently small fixed c, we can know the set S of
all simple y with K(y) < c. So for all y in S, and all x not in S, we
can prove K(x) > K(y), making an infinite number of facts.

> there are only finitely many mathematical
> propositions that are both true and formally provable.

That's wrong too. All theories of interest, e.g. Peano arithmetic or
ZFC, prove infinitely many mathematical propositions to be true, e.g.
Succ(n) > n.
They'd be of no interest if they had only finitely many theorems.

### Aidan Rocke

Aug 13, 2021, 6:49:46 AM8/13/21
to John Tromp, Algorithmic Information Theory
Good afternoon AIT mailing list,

I wrote imprecisely when I said that there are finitely many propositions that
are both true and provable. What I meant was that the consistency of mathematics
built upon a finite number of axioms depends on excluding Gödel numbers that have
a Kolmogorov Complexity beyond a particular threshold. This perspective is partly
motivated by Chaitin's heuristic argument:

If a set of theorems constitutes t bits of information, and a set of axioms contains less than
t bits of information, then it is impossible to deduce these theorems from these axioms.
-Chaitin, Information-theoretic Limitations on Formal Systems(1974)

In Chaitin's lectures 'From Philosophy to Program Size' he argues that this will
force future mathematicians to consider tradeoffs between adding new axioms
or accepting experimental methods as methods of verification in pure mathematics.
I believe that we have reached this point in the history of mathematics.

I won't argue that I have done what is necessary to prove a rigorous variant of
Chaitin's heuristic argument. But, I wonder whether there is a community of
information theorists that has made a serious effort in this direction. The best
approximation to what I am looking for appears to be:

Is Complexity a Source of Incompleteness? by Calude and Jürgensen(2004)

Cheers,

Aidan