Join the discussion
Write your take first — we'll ask for email only when you're ready to publish.
- Hacker News
- (2020)
Some previous discussions:
- Relevant:
The Annotated Godel: A Reader's Guide to his Classic Paper on Logic and Incompleteness by Hal Prince.
A good review - https://eevans.co/blog/annotated-godel-review/
by rramadass - Great breakdown: https://stopa.io/post/269by manesioz
- 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
- Even more videos to binge before the holidays end! Thanks for sharing!by 3abiton
- I'm aware that very smart people have thought carefully about all this, but I still can't help thinking that this argument is unnecessarily complicated. It seems to me that a proof is something that can be written down as a finite string of symbols, so any proof system admits only countably many proofs. On the other hand, it's easy to make up an example of an uncountable set of propositions. That's too many for each of them to have a proof, so some of them must be unprovable. What am I missing?by gradschool
- Does your uncountable set of propositions include some which cannot be written as a finite string of symbols?
If "yes" - how might such as proposition be proven true with a finite string of symbols?
(If your proof symbols are from an infinite character set, that has its own issues.)
by bell-cot - 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 - That won't work. Gödel number encodes a paradox, but a halting execution of a TM is not a paradox, so can't be written as a Gödel number.by GoblinSlayer
- Of possible interest
Godels Incompleteness Theorem (Little Mathematics Library)
by V. A. Uspensky
by the-mitr - Thank You.
A classic Mir publication from the Soviet-era.
by rramadass - > 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 - It’s clearly true in The Natural Numbers. It’s not provable because in some model it’s false. Being clearly true in one model does not make it provable.by czgov
- 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
- Very Nice; Thank You!
Is there a way to get a pdf of the slides?
by rramadass - I hope you don't mind, but just in case anyone is curious like I am, here i think is the video to the talk https://www.youtube.com/watch?v=KdZq5JvhPVQby fhe
- If you find this interesting, I highly recommend reading "Gödel, Escher, Bach: an Eternal Golden Braid"by gavinsyancey
- while it is a groovy into to recursion and other cool ideas, GEB annoys me in that I feel like the three figures in the title are ill matched. Godel proves a super important result in math, sure... Escher was a skilled draughtsman who had a feel for tesselation. An OK artist IMO but no special insights. Bach on the other hand was an expressive genius who in the volume, power and beauty of his productions just seemed to drop out the sky like a meteor. Escher does not belong in the same breath frankly. if Bach made a crab canon or did other marginally math-y things that is just not the point - the work lives or dies in entirely different terms...by quaverquaver
- It’s actually an interesting fact that every person who was programming in the 80s owns a copy of GEB, which they flipped through a bit and then put on the bookshelf and never actually read.by khazhoux
- “Godel’s Proof”[1] is also a great and shorter read if the scale of GEB is intimidating(I know it was for me at first).by trescenzi
- 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).
Instead I'd recommend Gödel's Proof by Nagel and Newman for a conceptual intro.
[1] I'm not a mathematician, so my understanding is necessarily informal.
by andyjohnson0 - "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.
- Wish I had the full text on me, but I recall there's a version of it with an introduction by Douglas Hofstadter that disagrees with the interpretation of the proof by Nagel and Newman, and it's something key to their culminating assessment of what Gödel's proof truly means, which is a remarkable disagreement to put into a forward to a text. Unfortunately the Kindle version I got from Amazon doesn't contain his forward and I'm struggling to find that version.
Edit: found the quote, and frankly I agree wholeheartedly with Hofstadter who seems to have a much more sophisticated understanding of the capabilities of computers, perhaps owing to his encountering them in a later era.
"My book, despite owing a large debt to Nagel and Newman, does not agree with all of their philosophical conclusions, and here I would like to point out one key difference. In their “Concluding Reflections,” Nagel and Newman argue that from Godel’s discoveries it follows that computers—“calculating machines,” as they call them—are in principle incapable of reasoning as flexibly as we humans reason, a result that supposedly ensues from the fact that computers follow “a fixed set of directives” (i.e., a program).
To Nagel and Newman, this notion corresponds to a fixed set of axioms and rules of inference—and the computer’s behavior, as it executes its program, amounts to that of a machine systematically churning out proofs of theorems in a formal system. This mapping of computer onto formal system takes the term “calculating machine” very literally—that is, a machine built to deal.with numbers and arithmetical facts alone. The idea that such machines by their very nature should churn out sets of true statements about mathematics is seductive and certainly has a grain of truth to it, but it is far from the full vision of the power and versatility of computers.
Although computers, as their name implies, are built of rigidly arithmetic-respecting hardware, nothing in their design links them inseparably to mathematical truth. It is no harder to get a computer to print out scads of false calculations (“2 + 2 = 5; 0/0 = 43,” etc.) than to print out theorems in a formal system. A subtler challenge would be to devise “a fixed set of directives” by which a computer might explore the world of mathematical ideas (not just strings of mathematical symbols), guided by visual imagery, the associative patterns linking concepts, and the intuitive processes of guesswork, analogy, and esthetic choice that every mathematician uses.
When Nagel and Newman were composing Godel’s Proof, the goal of getting computers to think like people—in other words, artificial intelligence—was very new and its potential was unclear. The main thrust in those early days used computers as mechanical instantiations of axiomatic systems, and as such, they did nothing but churn out proofs of theorems. Now admittedly, if this approach represented the full scope of how computers might ever in principle be used to model cognition, then, indeed, Nagel and Newman would be wholly justified in arguing, based on Godel’s discoveries, that computers, no matter how rapid their calculations or how capacious their memories, are necessarily less flexible and insightful than the human mind.
But theorem-proving is among the least subtle of ways of trying to get computers to think[...]"
He goes on like this for a bit more, and fleshes out a deeper argument, but this is already long as quoted passages on hn go. But I think Hofstadter is exactly right and shows a much more sophisticated understanding of computers than Nagel and Newman in their celebrated introduction to Gödel. I would go so far as to say their philosophical conclusion is almost exactly wrong, and is as baffling as if Darwin's Origin of Species included a section of "conclusions" denying the possibility of ever developing effective vaccines in the future. Wrong to the point of being contrary to the spirit of the subject that was so exceptionally articulated up to that point. And it's in my opinion terribly damaging for a conclusion so backwards to be embedded in a text that's celebrated as the best explanation of the proof.
by glenstein - Also recommend this book. Very concise too, it's only around 100 pages.by willmeyers