Chaitin's incompleteness theorem

[Aidan Rocke]

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]

> 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]

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