# 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).

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