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
> 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.
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.
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:
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.
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.)
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/
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.
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?
> Mathematician Gregory Chaitin deeply admires Kurt Gödel’s work, viewing the incompleteness theorems as monumental. However, rather than relying on the liar’s paradox like Gödel, Chaitin reframed incompleteness through information theory and computer size (using the Berry paradox). He argues that Gödel’s proof makes incompleteness look like a rare, pathological exception, whereas his own information-theoretic approach shows it is natural, universal, and everywhere in math.
Google AI. Trust me bros, he said something along those lines. Understanding Godel's proof is terribly challenging even for teenage Chaitin.
Found this lovely anecdote
>Robert J. Marks: So you cold called him then. [...]
>Gregory Chaitin: So he said, “Okay, send me a paper of yours on this topic. I’ll take a look at it. And if like it, maybe I’ll give you an appointment to visit.” [...] So he had taken a look at it and immediately perceived a crucial aspect of the definition of complexity that I was proposing. And he gave me an appointment. [...]
>Gregory Chaitin: I was all set for the great day — and it snowed! And this was the week before Easter. So that’s unusual, a spring snowstorm but it wasn’t a big snowstorm. Nothing was going to stop me from visiting my hero. So there I am in my office at the IBM Watson Center, about to leave. I figured out how much time I needed. About to leave and unfortunately — very unfortunately — the phone rang. It was Gödel ’s secretary saying Gödel is very careful with his health. And because it snowed, he’s not coming in to his office today. And therefore your appointment is canceled.
>So that was a surreal experience. And there was no way to reschedule because I was going to leave just in a few days, heading back to Argentina, to Buenos Aires. But actually this surreal story actually fits better Gödel and his legend, because for example, when Gödel died, they found lots of answers typed up to letters he received, but were never sent. They were never mailed. So there was a surreal quality to Gödel and to communicating with Gödel.
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.
26 comments
[ 0.33 ms ] story [ 9.6 ms ] threadThat'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.
Some previous discussions:
2023 https://news.ycombinator.com/item?id=38391787
2020 https://news.ycombinator.com/item?id=23832087
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
https://shs.cairn.info/revue-internationale-de-philosophie-2...
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.)
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.
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.
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.
"Opposite statements, G and ~G, can’t both be true in a consistent axiomatic system."
Godels Incompleteness Theorem (Little Mathematics Library)
by V. A. Uspensky
https://archive.org/details/GodelsIncompletenessTheorem
Google AI. Trust me bros, he said something along those lines. Understanding Godel's proof is terribly challenging even for teenage Chaitin.
Found this lovely anecdote
>Robert J. Marks: So you cold called him then. [...]
>Gregory Chaitin: So he said, “Okay, send me a paper of yours on this topic. I’ll take a look at it. And if like it, maybe I’ll give you an appointment to visit.” [...] So he had taken a look at it and immediately perceived a crucial aspect of the definition of complexity that I was proposing. And he gave me an appointment. [...]
>Gregory Chaitin: I was all set for the great day — and it snowed! And this was the week before Easter. So that’s unusual, a spring snowstorm but it wasn’t a big snowstorm. Nothing was going to stop me from visiting my hero. So there I am in my office at the IBM Watson Center, about to leave. I figured out how much time I needed. About to leave and unfortunately — very unfortunately — the phone rang. It was Gödel ’s secretary saying Gödel is very careful with his health. And because it snowed, he’s not coming in to his office today. And therefore your appointment is canceled.
>So that was a surreal experience. And there was no way to reschedule because I was going to leave just in a few days, heading back to Argentina, to Buenos Aires. But actually this surreal story actually fits better Gödel and his legend, because for example, when Gödel died, they found lots of answers typed up to letters he received, but were never sent. They were never mailed. So there was a surreal quality to Gödel and to communicating with Gödel.
https://mindmatters.ai/2021/03/gregory-chaitins-almost-meeti...
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/
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.