# Information-theoretic proof of Gödel's Theorem?

I'm looking for an information-theoretic proof of Gödel's Theorem that goes something like this, without any reference to diagonalization:

1. Every axiom system in the scope of Gödel's Theorem has a finite number of bits.
2. It requires an infinite number of bits to specify the all the truths of number theory.
3. By the Soundness theorem, no new bits can be introduced by deduction.
4. So no such axiom system as specified in part 1 above can fully axiomatize number theory.

-
I think Chaitin's proof can be seen in this way. Point 2. is where perhaps a bit of diagonalization is needed. (those infinitely many truths are "number n can't be encoded in less than log_2 n bits", true for infinitely many n's) – user8268 Mar 30 '11 at 7:21
It seems to me that by the time you have proved (2) you will have already proved the theorem. – Carl Mummert Mar 30 '11 at 10:25
@Carl: if you make your comment into an answer, I'll accept it as the answer to the question. – ShyPerson May 27 '11 at 18:21

I think that parts (1) and (2) would already prove the theorem. The heart is part (2), which phrased another way says "no finite number of bits can encode all truths of number theory". The difficult thing with the proof would be making formal sense of "finite number of bits".

-

You might want to have a look at this: http://en.wikipedia.org/wiki/Kolmogorov_complexity#Chaitin.27s_incompleteness_theorem

However, it would seem that diagonalization is indeed used, to generate the paradoxical string (for which the complexity cannot be proved).

-

This makes no sense to me. Yes, some axiom systems can be written down using a finite number of bits. From those axioms infinitely many theorems may be deduced. Does it not require infinitely many bits to specify them? How does your "proof" distinguish between systems that are complete, such as Presburger arithmetic, and systems that are not?

-
Point 2. wants to say that there are infinitely many bits of independent truths in number theory – user8268 Mar 30 '11 at 7:30
... (expressible in the language of Peano arithmetics) – user8268 Mar 30 '11 at 7:38
First question: since Kolmogorov–Chaitin complexity (en.wikipedia.org/wiki/Kolmogorov_complexity) is being used here, the actual information content of the theorems of an axiom system is no greater than the number of bits needed to encode the axioms. Second question: Since Presburger arithmetic is deductively complete, the whole theory has no more information than the axioms. This need not be the case for other systems. – ShyPerson Mar 30 '11 at 19:44
@ShyPerson: as I understand Chaitin (willing to be corrected) no axiom system has a set of theorems of greater complexity than the axioms, which is his central point. Just because you can prove infinitely many statements does not prove that the axioms have infinite information content. Think of proving $1+n=S(n)$ in PA. – Ross Millikan May 28 '11 at 4:58