5
$\begingroup$

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.

Does such a proof exist? Is it even feasible? Please include references with your answer. Thanks

  • 0
    @Carl: if you make your comment into an answer, I'll accept it as the answer to the question.2011-05-27

3 Answers 3

3

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".

2

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

-1

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?

  • 0
    @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.2011-05-28