Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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
2  
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

3 Answers 3

up vote 3 down vote accepted

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

share|improve this answer

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

share|improve this answer

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?

share|improve this answer
    
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
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.