HN

Need help?
<- Back
How Gödel's Proof Works (2020)

How Gödel's Proof Works (2020)

tzury

Comments (39)

  • 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.
  • 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/
  • gavinsyancey
    If you find this interesting, I highly recommend reading "Gödel, Escher, Bach: an Eternal Golden Braid"
  • 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.
  • the-mitr
    Of possible interestGodels Incompleteness Theorem (Little Mathematics Library)by V. A. Uspenskyhttps://archive.org/details/GodelsIncompletenessTheorem
  • 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.)
  • 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."
  • somethinsfishy
    If you like video, supplement your reading withJoel David Hamkins - Oxford lectures on the philosophy of mathematics "The Gödel incompleteness phenomenon" https://www.youtube.com/watch?v=Y5trjR5aw0kalso, "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
  • 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.
  • manesioz
    Great breakdown: https://stopa.io/post/269
  • dschoon
    Quanta Magazine is a never ending source of good material. Add it to your feed.
  • 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...
  • 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
  • bananaflag
    (2020)
  • 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.
  • 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.
  • ChrisArchitect
  • anon
    undefined