Godel's Theorem

[georgemw at speakeasy.net]

On 9 Jan 2002, at 10:40, Tim May wrote:


> By the way, for all of you who struggled to understand Godel's Theorem 
> expressed in the "logic" formulation that Godel first used--and that was 
> the basis of Newman's fairly popular exposition--there are very 
> understandable formulations of Godel's Theorem in terms of information 
> theory and compressibility. Chaitin has a very clean one (no Kleene pun 
> intended). 

Maybe I'm oversimplifying, but it seems to me that Godel's
theorem follows trivilaly once you've heard of Cantor's
diagonal slash.  As I understand it, Godel's theorem says
in essence that in any system complex enough to include the
irrational numbers there must be statements which are true in that
system but which cannot be proven in that sytem.  But since
there are uncountably many irrational numbers,
there are uncountably many statements of the form
A=A  which are true but which cannot be expressed with a finite
number of symbols. 

George

> --Tim May

George