= 27d567bc2d48d9f40e9ccc20ea370b15)
XiXiDu comments on Explained: Gödel's theorem and the Banach-Tarski Paradox - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (40)
I'd read this explanation from Smullyan before I read about the theorem in more detail, and I don't think Smullyan's explanation conveys real understanding. It doesn't talk about Gödel numbering, which is the real ingenuity behind the proof, and it doesn't talk about omega-inconsistency. At best, it gives you a glimpse of the logic involved and gives you the ability to think up more cute examples that also serve as incomplete explanations. At worst, it might give you a fundamental misunderstanding of the theorem that may cause you to think and say extremely stupid things.
I haven't really looked into Gödel's theorem yet (got books though......in the queue) but Gödel numbering itself seems to be relatively simple. The Diagonal lemma seems to be much more difficult, or at least I am missing a lot of required background knowledge. I stopped reading the Wiki entry on it and suspended it until I am going to dive into logic and especially provability logic.
It depends on what you mean by "simple". The Diagonal Lemma is extremely easy to state and prove (by which I mean that the proof itself has very few steps), but the proof looks like magic. That is to say, the standard proof doesn't really reveal how the Lemma was discovered in the first place.
Gödel Numbering, on the other hand, isn't too difficult to understand, but actually proving the Incompleteness Theorems (or whatever) usually requires pages and pages of boring, combinatorial proofs that one's Numbering works the way one wants it to. Conceptually, however, Gödel Numbering was a massive leap forward. As I understand it, before Gödel's paper in 1931, no one had really realized that such techniques were possible (germs of the idea go back at least to Leibniz, though), nor that one could in fact use such a technique to make metatheoretical claims about one's object-level theory in the language of that theory itself (so that the theory could, in a sense, "prove things about itself"), nor what the implications of this would be.
Another thing to note is that Gödel's numbering technique inspired Alan Turing's work in 1936, and arguably was an absolutely necessary conceptual breakthrough for the invention of computers.
Oh, and I wouldn't recommend studying provability logic until you have already mastered a sufficient amount of Mathematical Logic, by which I mean that you have gained understanding equivalent to what you would ideally gain taking an advanced undergraduate Mathematics course or Philosophy course on the subject (assuming the Philosophy course was sufficiently technical/rigorous).