How Gödel's Proof Works (2020)

gavinsyancey

If you find this interesting, I highly recommend reading "Gödel, Escher, Bach: an Eternal Golden Braid"

smfjaw

This is my favourite proof in all of maths (that I've been exposed to). Truly unreal feeling proving a statement is unprovable using godel numbering in an exam

matherial

> 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.

ChrisArchitect

(2020) Some previous discussions: 2023 https://news.ycombinator.com/item?id=38391787 2020 https://news.ycombinator.com/item?id=23832087

manesioz

Great breakdown: https://stopa.io/post/269

somethinsfishy

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

Paracompact

I think Godel's theorem is the single most important result in mathematics. At the same time, when the subject comes up, I like to link people to this essay to dispel a lot of the woo surrounding it regarding human exceptionalism, religion, etc: https://shs.cairn.info/revue-internationale-de-philosophie-2...

dsego

I am wondering if I'm just not smart enough to understand, but I've managed to slog through GEB and in the end the proof seems contrived, it stands on self reference.

pfdietz

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.)

gregfjohnson

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/

reliablereason

Gödels incompleteness is just an example of the fact that you cant determine the outcome of infinite regression (in the general case). The same as me asking you to give me the last digit of pi. I am a bit annoyed by pop science always twisting it to sound so convoluted.

sharts

Kind of annoying that literally every article or link shared about this always goes on with some massive introduction of the past instead of just getting to the point. 2+2=4 without 7 paragraphs about humanity wanting numerical representations of quantities and the various number systems devised throughout history before they actually gloss over the actual facts and details.

MathMonkeyMan

"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.

8bitsrule

This article is the most concise presentation of GP ... and of the conclusion it leads to ... I've seen. "Opposite statements, G and ~G, can’t both be true in a consistent axiomatic system."

the-mitr

Of possible interest Godels Incompleteness Theorem (Little Mathematics Library) by V. A. Uspensky https://archive.org/details/GodelsIncompletenessTheorem

dschoon

Quanta Magazine is a never ending source of good material. Add it to your feed.