Gödel's proof
by Ernest Nagel, James Roy Newman · first published 1958
77% recommend21% neutral3% critical
Why HN recommends it
Short, approachable explanation of how Gödel's incompleteness proof works, aimed at laypeople, undergrads, and programmers. Favored over Gödel, Escher, Bach for readers who want just the proof without digressions.
Summarised by Claude from recommending comments
In 1931 Kurt Godel published his fundamental paper, "On Formally Undecidable Propositions of "Principia Mathematica" and Related Systems." This revolutionary paper challenged certain basic assumptions underlying much research in mathematics and logic. Godel received public recognition of his work in 1951 when he was awarded the first Albert Einstein Award for achievement in the natural sciences--perhaps the highest award of its kind in the United States. The award committee described his work in mathematical logic as "one of the greatest contributions to the sciences in recent times." Howev
Affiliate links. As an Amazon Associate I earn from qualifying purchases.
Mentions per year
What Hacker News says
Related books
2012–2024An Introduction to Gödel's Theorems
Peter Smith
Recommended by 3 · mentioned by 43 recommend · 4 mention3 recommend · 43 recommend
2014–2022Forever undecided
Raymond M. Smullyan
Recommended by 4 · mentioned by 44 recommend · 4 mention4 recommend · 44 recommend
2014–2020Euclidean and non-Euclidean geometries
Marvin J. Greenberg
Recommended by 1 · mentioned by 21 recommend · 2 mention1 recommend · 21 recommend
The lady or the tiger?
Raymond M. Smullyan
Recommended by 10 · mentioned by 1210 recommend · 12 mention10 recommend · 1210 recommend
2008–2022The Mathematical Tourist
Ivars Peterson
Recommended by 4 · mentioned by 44 recommend · 4 mention4 recommend · 44 recommend
2007–2026I Am a Strange Loop
Douglas R. Hofstadter
Recommended by 101 · mentioned by 204101 recommend · 204 mention101 recommend · 204101 recommend
2010–2022Godel's Theorem
Torkel Franzen
Recommended by 4 · mentioned by 54 recommend · 5 mention4 recommend · 54 recommend
2008–2023Number theory
George E. Andrews
Recommended by 5 · mentioned by 65 recommend · 6 mention5 recommend · 65 recommend
When I first became fascinated with incompleteness (following initial coursework in theory of computation), it kind of became my "religion" of sorts for a while. But as many mathematicians lament, the Incompleteness Theorem is one of the most popularly abused proofs of all time - used for non-experts to assert their own half-baked pseudo-philosophy (of course, the same goes for quantum mechanics a
on “Gödel and the limits of logic” ↗I read it cover to cover out of a sense of obligation but came away very disappointed. The Achilles-Turtle-Random Other Creature allegories got very tiresome, and the content took a very long time to get to the point. For anyone interested in the proof, I recommend Gödel’s Proof by Nagel instead. It covers the same material in about a tenth the space. (GEB has other philosophical discourses that
on “What Made Gödel’s Incompleteness Theorem Hard to Prove” ↗…even vaguely cares about fundamentals of computer science should definitely give it a read, and if possible a thorough read. Slightly related: Although a more technical/deeper discussion, but the book "Godel's Proof"[1] by Nagel and Newman is a very approachable text in this domain, and explains many aspects of the incompleteness theorems. [1] http://www.amazon.com/G%C3%B6dels-Proof-Ernest-Nagel/dp/0814...
on “Gödel, Turing and Cantor: The Math” ↗For me, GEB was a considerable waste of time and contributed nothing to my understanding of intelligence or AI. The time would have been be better spent elsewhere. If you want to understand Godel's proofs then I recommend "Godel's Proof" by Ernest Nagel and James R. Newman: http://www.amazon.com/Gödels-Proof-Ernest-Nagel/dp/081475837.... Instead of Hofstadter's GEB, read some of his papers, e.g., "Analogy…
on “Ask HN: Is "Gödel, Escher, Bach" still worth reading?” ↗…one running inside each human brain) is going to at least be as complex as this set of axioms. Also, you really should read the JR Lucas material-- it explains this. And, I'd suggest Nagel & Newman's _Godel's Proof_ for a great introductory explanation of the Incompleteness Theorems.
on “Is nature a low-complexity sampler?” ↗There is a little great book called "Godel's proof" by Nagel and Newman[1]. And definitely requires some focus but readable nevertheless. [1] https://www.amazon.com/G%C3%B6dels-Proof-Ernest-Nagel/dp/081... Edit : removed a line
on “1931: Kurt Gödel shows limits of math, logic, computing, AI” ↗GEB was a considerable waste of time and contributed nothing to my understanding of intelligence or AI. The time would have been be better spent elsewhere. If you want to understand Godel's proofs then I recommend the book "Godel's Proof" by Ernest Nagel and James R. Newman: http://www.amazon.com/Gödels-Proof-Ernest-Nagel/dp/081475837... Instead of Hofstadter's GEB, read some of his papers,…
on “The Man Who Would Teach Machines to Think” ↗I'd highly recommend "Gödel's Proof" by Ernest Nagel and James Newman (https://www.amazon.com/G%C3%B6dels-Proof-Ernest-Nagel/dp/081...). It'll probably require a bit of patience to go through, but should be fairly accessible to reader without an extensive mathematics background.
on “Time Travelers” ↗Gödel’s Proof, by Nagel & Newman gives a good explanation for the semi-layman or undergrad coming across this for the first time. Before picking up this book as an undergrad in pure maths, I still had romantic ideas about a separate platonic universe and the divine authority of mathematics to explain all human thought. This book, along with studying the various geometries, each with a different
on “A Computability Proof of Gödel’s First Incompleteness Theorem” ↗…reading it is an incredibly useful thing in my view. It's a thick book and takes commitment to read. Side note: Check out this book (http://www.amazon.com/G%C3%B6dels-Proof-Ernest-Nagel/dp/0814...) on Godel's proof. It's been updated by Doug Hofstadter the author of GEB. I found it pretty good. Read it slowly, two three time if needed. It will make sense.
on “Eliminate the Computer Science major” ↗…is that the Devil himself collects these discarded old volumes and passes them out as reading material to nerds in Hell. For 8 years you've been wasting your free time. Sell the GEB and read Nagel's "Godel's Proof" (see my other post for URL) instead.
on “6 month read-through/discussion of Gödel, Escher, Bach starting 1/17 on Reddit” ↗GEB is a great book, and I've probably read it at least 3.33333333... times over the years. As a late teen it blew my mind. But I'm not sure I'd recommend it as a route into Gödel's proofs [1]. The book covers a lot of other ground too, and is notoriously digressive and quirky (looking at you, dialogues). I'd recommend Gödel's Proof by Nagel and Newman for a conceptual intro. [1] I'm not a mathe
on “How Gödel's Proof Works” ↗Nice list. I have been kind of doing the same thing - only over many years. One book that was incredible and disturbing was a small paperback - giving a layman's guide to Godel's Proof (maybe by Nagel&Newman?). The topic is too abstract to ever apply to a real world problem. But it is so profound that it is hard to imagine going through life not knowing it.
on “Learning Math” ↗I read this little gem over the summer: Godel's Proof (http://www.amazon.com/Godels-Proof-Ernest-Nagel/dp/081475837...) At 160 pages, it's the ideal size to carry with you everywhere you go. All summer long, any time I had an extra half an hour, I would…
on “Ask HN: Good books on mathematics for somebody who's only taken high school math?” ↗I highly recommend Gödel's Proof (Nagel and Newman) as a supplement. I got a lot out of Hofstadter's book, but honestly found much of the discussion of the incompleteness theorem more confusing than it needed to be. If you're mostly interested in the Gödel part, I actually recommend you read it instead of Hofstadter's book. Gödel's Proof is very concise, and more clearly describes the core argume
on “Ask HN: Experiences with 'Gödel, Escher, Bach' (GEB)?” ↗