8 views

Skip to first unread message

Aug 12, 2021, 6:25:48 PM8/12/21

to Algorithmic Information Theory

Good evening AIT mailing list,

*or* doing rigorous math with a finite number of propositions and

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

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

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
> interpret it in a very narrow sense. i.e. we can only prove finitely many

> facts of the form K(x) > K(y).

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.

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.

Aug 13, 2021, 6:49:46 AM8/13/21

to John Tromp, Algorithmic Information Theory

Good afternoon AIT mailing list,

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

Search

Clear search

Close search

Google apps

Main menu