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.
It doesn’t talk about Gödel numbering, which is the real ingenuity behind the proof,
Depends if you only want to show that set theory is incomplete, you don’t need Gödel numbering and you can more-or-less turn Smullyan’s explanation into a complete proof in a straightforward manner.
Depends if you only want to show that set theory is incomplete, you don’t need Gödel numbering and you can more-or-less turn Smullyan’s explanation into a complete proof in a straightforward manner.
It doesn’t talk about Gödel numbering, which is the real ingenuity behind the proof, and it doesn’t talk about omega-inconsistency.
You don’t need omega-consistency, just consistency. Gödel originally proved it for omega-consistent theories, but five years later Rosser published a rather pleasing little trick that strengthens the result to just consistent theories.
You get real understanding when you study the actual proof. For that, the best book I know is Smullyan’s Goedel’s Incompleteness Theorems. For an informal argument that can be understood by someone who doesn’t know what a formal system is, I think this one is quite good.
It doesn’t talk about Gödel numbering, which is the real ingenuity behind the proof...
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).
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.
I know. But I thought it would be better than nothing. Such informal explanations also help to overcome the widespread belief that you need to be a genius to approach those problems.
Such informal explanations also help to overcome the widespread belief that you need to be a genius to approach those problems.
Fair point, but I think the aforementioned danger of misunderstanding is more harmful than learned helplessness with respect to math is. I’d rather people not know the theorem than misunderstand it and use said misunderstanding to wreak epistemic violence.
Scientifically, I suggest most of psychology and psychiatry (I’m looking at you, Law & Order: SVU). In a similar vein is programming/hacking (e.g. 24, any crime drama).
Godel’s incompleteness theorem
In popular culture? What misunderstandings of it have you seen?
Hmm, not popular culture. Certainly arguing with people purveying nonsense as a form of the argument “you can’t be certain therefore I might be right.”
Such informal explanations also help to overcome the widespread belief that you need to be a genius to approach those problems.
But they do so in the wrong way, but conveying a second misconception that these problems can be easily understood without bothering actually study much maths.
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.
Depends if you only want to show that set theory is incomplete, you don’t need Gödel numbering and you can more-or-less turn Smullyan’s explanation into a complete proof in a straightforward manner.
Ok, I agree that this is an important point.
You’re right, I hadn’t thought about that.
You don’t need omega-consistency, just consistency. Gödel originally proved it for omega-consistent theories, but five years later Rosser published a rather pleasing little trick that strengthens the result to just consistent theories.
You get real understanding when you study the actual proof. For that, the best book I know is Smullyan’s Goedel’s Incompleteness Theorems. For an informal argument that can be understood by someone who doesn’t know what a formal system is, I think this one is quite good.
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).
I know. But I thought it would be better than nothing. Such informal explanations also help to overcome the widespread belief that you need to be a genius to approach those problems.
Fair point, but I think the aforementioned danger of misunderstanding is more harmful than learned helplessness with respect to math is. I’d rather people not know the theorem than misunderstand it and use said misunderstanding to wreak epistemic violence.
A list of habitually abused scientific concepts in popular culture?
Godel’s incompleteness theorem
Schroedinger’s cat
many worlds
anything quantum really
most things about evolution
Add your own!
Scientifically, I suggest most of psychology and psychiatry (I’m looking at you, Law & Order: SVU). In a similar vein is programming/hacking (e.g. 24, any crime drama).
In popular culture? What misunderstandings of it have you seen?
Hmm, not popular culture. Certainly arguing with people purveying nonsense as a form of the argument “you can’t be certain therefore I might be right.”
Cryptography. Like, all of it.
But they do so in the wrong way, but conveying a second misconception that these problems can be easily understood without bothering actually study much maths.