Join the discussion
Write your take first — we'll ask for email only when you're ready to publish.
- Hacker News
- If you like video, supplement your reading with
Joel David Hamkins - Oxford lectures on the philosophy of mathematics "The Gödel incompleteness phenomenon" https://www.youtube.com/watch?v=Y5trjR5aw0k
also, "Gödel's incompleteness theorems: The proof that broke mathematics" | Joel David Hamkins https://www.youtube.com/watch?v=Sza69An_H8o spam-bait title but excellent mid-level talk.
edit: speling
- For me this proof was always a cautionary tale about being careful about recursion when you use any language.
It's the same thing as with set theory. Once you let yourself talk about sets of sets without any restrictions other than the language itself puts on what you are talking about, you'll end up with sort of contradictory recursion that ends up in a paradox. The message is not "set theory is incomplete, or invalid" but rather "we were a bit too cavalier with words and not everything we can say about sets makes sense just because it's grammatically correct so we need to be more careful about defining what a set is and what it can and cannot contain".
For me "provability" is a direct equivalent of unrestricted sets of sets. If you don't restrict what provability means and how it can be used in context of the rest of math you end up with contradictory recursion that makes you believe there are true but unprovable things. It's easier to spot how bonkers it is on sets because there you end up with a set that is and isn't its own element at the same time (because sets are so generic that can produce paradoxical recursion on themselves without any other concept involved), but things being unprovable and true at the same time is the same category of absurdity.
by scotty79 - You can also obtain incompleteness from the unsolvability of the halting problem, by noting that if every statement in (say) Peano arithmetic were provable, one could solve the halting problem. Encode a halting execution of a TM as an integer using Gödel numbers and write a statement that the execution halts. Either that statement or its negation would be provable, so search for proofs for each at the same time.
An additional related theorem is Rogers' recursion theorem, which is how we get programs that, when run, print their own source code (by the theorem this can be done in any Turing complete programming language.)
by pfdietz - Of possible interest
Godels Incompleteness Theorem (Little Mathematics Library)
by V. A. Uspensky
by the-mitr - > However, although G is undecidable, it’s clearly true.
That's... not really true; it's surprising to see it in Quanta, of all places.
Godel's (separate) completeness theorem says that in first-order logic, anything that's semantically true in all possible scenarios can be syntactically proved. So, if G is "clearly true", that ought to make it provable.
The theorems don't contradict each other because in FOL, G is not guaranteed to be true. Its truth is independent of the machinery Godel put in place.
It's not something you really need to get into an introductory text, but it actually makes the whole outcome easier to grasp, and leads to many more counterintuitive results, such as Skolem's paradox.
by matherial - Show HN: I recently gave a talk on the incompleteness theorem, specifically expressed in the language of software. It starts with a bit of historical background and a discussion of some of the philosophical context in which he carried out his work. The second half of the talk is my attempt to show the beautiful essential idea at the core of Godel's idea, pitched to a technically knowledgeable general audience. These are the slides from the talk, not translated into web pages; YMMV. Link: https://www.gregfjohnson.com/godel_incompleteness/by gregfjohnson
- "Gödel's Proof" by Ernest Nagel and James R. Newman helped me to get it at some point.
On Amazon: <https://www.amazon.com/Godels-Proof-Ernest-Nagel-ebook/dp/B0...>
I might even pick up an ebook version if I can find it somewhere else. Been a while.
- If you find this interesting, I highly recommend reading "Gödel, Escher, Bach: an Eternal Golden Braid"by gavinsyancey