Chaitin's incompleteness theorem

8 views
Skip to first unread message

Aidan Rocke

unread,
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

unread,
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

unread,
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 

Reply all
Reply to author
Forward
0 new messages