5 ms·

Would anyone happen to have a recommendation for someone hoping to make Gödel's incompleteness theorem "click"? It feels like every time I reapproach it, I have

by jekude 3y ago

Would anyone happen to have a recommendation for someone hoping to make Gödel's incompleteness theorem "click"? It feels like every time I reapproach it, I have to start the intuition building all over again.

Areading314 3y ago
Read gödel, escher, bach by Douglas Hofstaedter
- mayd 3y ago
  As the late Martin Gardiner opined: "Every few decades an unknown author brings out a book of such depth, clarity, range, wit, beauty and originality that it is recognised at once as a major literary event. This is such a work." Nevertheless, Infinity and the Mind: The Science and Philosophy of the Infinite by Rudy Rucker is, in my opinion, a better choice for the mathematically inclined layman interested in Goedel's discoveries and plenty of related mathematics. Rucker's book even includes an account of his (somewhat over-enfusive) meeting with the great man.
bsdpufferfish 3y ago
Why are you interested? I recommend the short book "Godel's proof". Godel's work is wrapped up in historical context which is both interesting and distracting from the core idea. For example, Bertrand's Russells' work and book isn't really essential, it's just the system which Godel worked in to do his proof.
steppi 3y ago
There’s a wonderful book on the subject by Raymond Smullyan, of knights and knaves recreational math puzzle fame which helped make it click for me. https://lib.undercaffeinated.xyz/get/pdf/5823 https://lib.undercaffeinated.xyz/get/pdf/5823
- johnthescott 3y ago
  K&K i would recommend as a first read on logic. i found GEB to be a bit long winded.
pandoro 3y ago
It's very entry-level (my level :)) but I found Veritaseum's video about it really clear and instructive: https://www.youtube.com/watch?v=HeQX2HjkcNo https://www.youtube.com/watch?v=HeQX2HjkcNo
aragonite 3y ago
Gödel Without (Too Many) Tears, by Peter Smith. Also his An Introduction to Gödel’s Theorems. https://www.logicmatters.net/books/ https://www.logicmatters.net/books/
Angostura 3y ago
"Godel, Escher, Bach" was my first introduction to it - you might find it an interesting book
- vouaobrasil 3y ago
  Speaking as a PhD in pure math: It's a great book, but I would not recommend it at all for someone trying to get the gist of the theorem. GEB is a book for those who already have a strong self-interest in or prediliction to the intricacies of mathematical logic. It's a long book and is likely to be off-putting for those wanting a practical approach. Raymond Smullyan's book (another reply to the OP) is a much better choice.
  - Angostura 3y ago
    Fair point. I don't have a mathematical grounding, but found it a thought-provoking and accessible intro. But different people will find different approaches compelling.
mananaysiempre 3y ago
The corresponding section in the beginning of Scott Aaronson’s “Quantum computing since Democritus” (the online version works[1]; see also the related blog post[2]). It’s short and to the point (unlike GEB) and enough to understand why something in this vein must be true. It’s not detailed enough, though, to understand each of the technical conditions in the standard statement individually (no explanation of ω-consistency and the like). [1] https://www.scottaaronson.com/democritus/lec3.html https://www.scottaaronson.com/democritus/lec3.html [2] https://scottaaronson.blog/?p=710 https://scottaaronson.blog/?p=710
- bondarchuk 3y ago
  Is there an entry-level explanation that explicitly goes over the following points? Let me illustrate: >The Incompleteness Theorem says that, given any consistent, computable set of axioms, there's a true statement about the integers that can never be proved from those axioms. Upon reading something like this I immediately have questions like: if this is so, then how do we know that this statement about the integers is true at all? What does it mean for something to be true within a set of axioms when you can't prove it? Why don't we say that the truth of this statement, within those axioms, is undetermined? If we, on the outside, know that it's true, why can't we forcefully plug that truth back into the theory? OK, I know that last one, you can do it but then you can also do an incompleteness proof for the new theory. But still, if the "problem" is only with self-referential statements, why can't we somehow isolate all self-referential statements and have a theory that's complete and consistent except for some caveats, which seems vastly better than just inconsistent, period? Sorry if that makes no sense, I know this topic is famous for attracting cranky discourse.. It just feels like all the popular explanations stop just short of really grappling with the real weirdness of the theorem.
  - deleted 3y ago
    [deleted]
  - colineartheta 3y ago
    > all the popular explanations stop just short of really grappling with the real weirdness of the theorem. No offense, but if I’m reading your comment correctly you’re making it out that nobody familiar with the proof has ever considered what “truth” really is. That’s…well, there’s a saying amongst physicists that, “you’re not even wrong.” The semantics of language and math have a copious amount of literature behind them. Not to mention that even asking the question is, forgive me, a tad juvenile. Also, recursively applying known unknowns back into the statement (? If I understood that correctly) is itself incomplete: how could a system be “complete” if there are unknowns? Forgive me if it seems I, too, have ventured into the cranky side of the discourse.
deleted 3y ago
[deleted]

by jekude 3y ago

Areading314 3y ago

Read gödel, escher, bach by Douglas Hofstaedter

mayd 3y ago
As the late Martin Gardiner opined: "Every few decades an unknown author brings out a book of such depth, clarity, range, wit, beauty and originality that it is recognised at once as a major literary event. This is such a work." Nevertheless, Infinity and the Mind: The Science and Philosophy of the Infinite by Rudy Rucker is, in my opinion, a better choice for the mathematically inclined layman interested in Goedel's discoveries and plenty of related mathematics. Rucker's book even includes an account of his (somewhat over-enfusive) meeting with the great man.

bsdpufferfish 3y ago

Why are you interested? I recommend the short book "Godel's proof". Godel's work is wrapped up in historical context which is both interesting and distracting from the core idea. For example, Bertrand's Russells' work and book isn't really essential, it's just the system which Godel worked in to do his proof.

steppi 3y ago

There’s a wonderful book on the subject by Raymond Smullyan, of knights and knaves recreational math puzzle fame which helped make it click for me. https://lib.undercaffeinated.xyz/get/pdf/5823 https://lib.undercaffeinated.xyz/get/pdf/5823

johnthescott 3y ago
K&K i would recommend as a first read on logic. i found GEB to be a bit long winded.

pandoro 3y ago

It's very entry-level (my level :)) but I found Veritaseum's video about it really clear and instructive: https://www.youtube.com/watch?v=HeQX2HjkcNo https://www.youtube.com/watch?v=HeQX2HjkcNo

aragonite 3y ago

Gödel Without (Too Many) Tears, by Peter Smith. Also his An Introduction to Gödel’s Theorems. https://www.logicmatters.net/books/ https://www.logicmatters.net/books/

Angostura 3y ago

"Godel, Escher, Bach" was my first introduction to it - you might find it an interesting book

vouaobrasil 3y ago
Speaking as a PhD in pure math: It's a great book, but I would not recommend it at all for someone trying to get the gist of the theorem. GEB is a book for those who already have a strong self-interest in or prediliction to the intricacies of mathematical logic. It's a long book and is likely to be off-putting for those wanting a practical approach. Raymond Smullyan's book (another reply to the OP) is a much better choice.
- Angostura 3y ago
  Fair point. I don't have a mathematical grounding, but found it a thought-provoking and accessible intro. But different people will find different approaches compelling.

mananaysiempre 3y ago

The corresponding section in the beginning of Scott Aaronson’s “Quantum computing since Democritus” (the online version works[1]; see also the related blog post[2]). It’s short and to the point (unlike GEB) and enough to understand why something in this vein must be true. It’s not detailed enough, though, to understand each of the technical conditions in the standard statement individually (no explanation of ω-consistency and the like). [1] https://www.scottaaronson.com/democritus/lec3.html https://www.scottaaronson.com/democritus/lec3.html [2] https://scottaaronson.blog/?p=710 https://scottaaronson.blog/?p=710

bondarchuk 3y ago
Is there an entry-level explanation that explicitly goes over the following points? Let me illustrate: >The Incompleteness Theorem says that, given any consistent, computable set of axioms, there's a true statement about the integers that can never be proved from those axioms. Upon reading something like this I immediately have questions like: if this is so, then how do we know that this statement about the integers is true at all? What does it mean for something to be true within a set of axioms when you can't prove it? Why don't we say that the truth of this statement, within those axioms, is undetermined? If we, on the outside, know that it's true, why can't we forcefully plug that truth back into the theory? OK, I know that last one, you can do it but then you can also do an incompleteness proof for the new theory. But still, if the "problem" is only with self-referential statements, why can't we somehow isolate all self-referential statements and have a theory that's complete and consistent except for some caveats, which seems vastly better than just inconsistent, period? Sorry if that makes no sense, I know this topic is famous for attracting cranky discourse.. It just feels like all the popular explanations stop just short of really grappling with the real weirdness of the theorem.
- deleted 3y ago
  [deleted]
- colineartheta 3y ago
  > all the popular explanations stop just short of really grappling with the real weirdness of the theorem. No offense, but if I’m reading your comment correctly you’re making it out that nobody familiar with the proof has ever considered what “truth” really is. That’s…well, there’s a saying amongst physicists that, “you’re not even wrong.” The semantics of language and math have a copious amount of literature behind them. Not to mention that even asking the question is, forgive me, a tad juvenile. Also, recursively applying known unknowns back into the statement (? If I understood that correctly) is itself incomplete: how could a system be “complete” if there are unknowns? Forgive me if it seems I, too, have ventured into the cranky side of the discourse.

deleted 3y ago

[deleted]