ncase
patreon
Bonus Mini-explainer: Gödel's Proof!
🕑 Added 2023-05-26 20:15:56 +0000 UTC(⏱ reading time: 7 minutes)
Hi all!
Sincerest apologies for my lack of updates. I'll share more in a future post, but my last 2 months have been: lots of couch-surfing, moving cities over & over, starting hormones for my transition(!), pausing hormones, burnout, a fun conference, more burnout, etc, everything except finishing the AI Safety explainer.
So for now, here's a Patreon-exclusive* mini-explainer on Gödel's Proof, the most infamous proof of the 20th century! [*EDIT Feb 1st, 2024: Making it public so I can link to it publicly]
I want to shift towards making smaller-but-more projects, for faster creative iteration & fun. So, here's the first of the mini-bonuses. Enjoy!
– – – – – – – – – – – – – – – – – – – – – – – –
– – – – – – – – – – – – – – – – – – – – – – – –
The printing press wasn't that complicated. It's "just" a grid of letter stamps. And yet, it took a rare person to invent it, and it overturned the world, for better and worse.
Same for the most infamous math proof of the 20th century! It's not that complicated – it's "just" basic arithmetic – yet it took a rare mind to discover it, it shook mathematics & philosophy, and even led to the invention of the computer... and thus our modern world. For better and worse.
In this mini-explainer, we'll go through Kurt Gödel's simple but stunning proof – and see how you could've re-invented it for yourself, from scratch!
Let's begin, with a paradox and a dream...
“THIS SENTENCE IS FALSE.”
If it's true, then it's false. If it's false, then it's true.
So this sentence can't be only true or only false: it must be both true and false, or neither true nor false!
This ancient sentence (Liar's Paradox) spooked mathematicians. Our modern world is built on science, science is built on math, and math is built on logic. Yet, there's wacky logical paradoxes like the above.
That's why, in the early 1900's, mathematicians had a dream:
To put logic, and thus all of math & science, on new foundations. 100% Paradox-free, Guaranteed™️!
The most notorious of these attempts was Russell & Whitehead's thousand-page-book, Principia Mathematica. It proved 1+1=2 on page 80.
How did it try to ban paradox? Well, you might try banning statements that talk about themselves ("this sentence is..."). But there's still paradoxes like:
“The next sentence is true. The previous sentence is false.”
Fine, then let's ban statements from talking about statements at all. You can have math statements like, "there is no greatest number", but not "meta-math" statements like, "there exists a proof of ‘there is no greatest number’."
And juuust in case, let's also ban the words "true" and "false". We can now only say "proveable" and "unproveable". So, for a statement nicknamed S, we rewrite "true" & "false" as...
- "S is true" → "S is proveable".
- "S is false" → "the opposite of S (not-S) is proveable".
This also lets us talk about 2 important features we want for math:
Math is complete if, for every statement S, we can prove at least one of S or not-S. (that is: no "undecidable" statements.)
Math is consistent if, for every statement S, we can prove at most one of S or not-S. (that is: no S and not-S, a contradiction.)
So that's our dream! A new system of math that's complete and consistent: every claim can be proven or disproven, but not both like in paradoxes.
In 1931, a 20-something punk named Kurt Gödel smashed our dream. What's worse, he didn't smash just one new system of math, he smashed every possible system that can at least do arithmetic. (which I'll carelessly call just "math")
His attack was a one-two knockout punch:
PUNCH #1: Turn statements-about-numbers into numbers, so that statements can now talk about statements.
A simple analogy: let's turn the first nine letters into digits, and back...
a↔1, b↔2, c↔3,
d↔4, e↔5, f↔6,
g↔7, h↔8, i↔9
So: "babe" becomes 2125, and 2125 becomes "babe".
(Gödel's system was more complicated, of course, but similar in spirit. With a clever enough system, even a statement like "There is no largest prime number" can be expressed as a single [very big!] number.)
What does this buy us? Well: things you do to words now become things you do to numbers!
For example, "repeat this 2-letter word twice" becomes the math operation, "multiply by 101":
- "ha" → 81
- 81 multiplied by 101 = 8181
- 8181 → "haha"
Which is "ha" repeated twice, as promised.
(Again, go further with this idea, and even a complicated procedure like "Check this proof is correct" can be expressed as a single [very complicated!] math operation on a single [very big!] number.)
In sum: as long as your math system can do arithmetic, you can turn statements-about-numbers into numbers, so that statements can refer to & even do stuff to other statements! Even though we banned that!
Okay, but self-reference is still banned... so we're fine, right?
PUNCH #2: Make a statement indirectly refer to itself.
Consider this sentence:
“repeated twice, first time in quotes, is cool” repeated twice, first time in quotes, is cool
This sentence does not say "this sentence". It does not directly refer to itself. And yet, if you take “repeated twice, first time in quotes, is cool” and repeat it twice, first time in quotes... you get the exact same sentence above. And it is cool!
Self-creating sentences like these are called quines. Again, Gödel's trick was more complicated, but it was similar to "repeat twice" ↔ "multiply by 101".
Now, hold my beer:
“repeated twice, first time in quotes, is unproveable” repeated twice, first time in quotes, is unproveable.
Or:
This sentence is unproveable.
Thankfully, we can't make a sentence that says "this sentence is false", because we banned the words "true" and "false".
But alas, "this sentence is unproveable" is still enough to smash our dreams...
KNOCKOUT: Show that math can't be both complete & consistent. We must pick the less terrible choice. And we still can't prove the less terrible choice.
Remember how "this sentence is false" couldn't be just true or just false, it was forced to be both true and false or neither true nor false?
The same happens to "this sentence is unproveable"! Let's see how. We have a statement (nicknamed "G" for "Gödel") that says this:
G = “There is no proof of G.”
So the opposite of G, not-G, says this:
not-G = “There is a proof of G.“
Now, let's see what happens if we prove either one...
- If we find a proof of G... then that's what not-G claims, so it's also a proof of not-G.
- If we find a proof of not-G... then as it claims, there is a proof of G.
Therefore: you can't find a proof for just G or just not-G. Either both can be proven (inconsistent), or neither can be proven (incomplete).
Therefore...
Gödel's First Incompleteness Theorem:
If math is consistent, then math must be incomplete.
So... which is the less-worse choice?
Well, "incomplete" is super annoying – some questions will just have no answer even in theory – but "inconsistent" is fatal.
Why? Consider what happens if you validly prove that 0 = 1. (There are many invalid "trick" proofs, but they all do something sneaky like divide by zero.) If you proved 0 = 1, you could add 1 to both sides to get 1 = 2, then multiply both sides by 3 to get 3 = 6, and so on. That is: you can prove every number = every other number.
This is (a rough analogy for) the principle of explosion, and it's why inconsistency is fatal. If you prove one contradiction, the damage isn't "contained" – you prove all contradictions.
(Note: Gödel believed "This sentence is unproveable" was true anyway. But this was a philosophical idea, not formal mathematics – we threw out "true" and "false", remember? Besides, it was later shown [Tarski's Theorem] that if you did try to define "true" and "false" in formal math, you could make "this sentence is false", and break everything again.)
Okay. So let's ditch "complete", to keep "consistent". There may be unproveable statements, but at least they're all annoying tricks like "this sentence is unproveable"... we don't lose any important, right?
Uh...
Gödel's Second Incompleteness Theorem:
We can never prove that even arithmetic is consistent.*
So, "0 = 1"? We can't ever prove we won't prove that. Math is just a ticking time-bomb forever.
This follows easily from the First Incompleteness Theorem. Which, as a reminder, says:
If math is consistent, then math is incomplete.
So if you prove math is consistent, then you prove math is incomplete: that is, you can prove neither G nor not-G.
But G says you can't prove G! So you do prove G!
Mein Gott, zat's a contradiction!
Therefore: if you prove math is consistent, you make it inconsistent!
🎺 womp womp 🎺
* to be precise: we can't prove a math-system's consistency within itself. You could create a "higher" system to prove it's consistent... but then you'd need an even higher one to prove that's consistent... and so on, forever. So, either way...
End of proof. The dream is dead.
. . .
Well, that one dream was dead. But Gödel's proof sparked more dreams.
It shook mathematics. It reinvigorated philosophy. And one day, the Nazi-fighting codebreaker Alan Turing was inspired by Gödel's trick of turning statements-about-numbers into numbers... and wrote a paper about turning algorithms-using-data into data. This led to a niche lil' product you may have heard of, called a "computer". The printing press of our era.
As Nagel & Newman concluded in their 1959 book, Gödel's Proof:
[Gödel's work] is an occasion, not for dejection, but for a renewed appreciation of the powers of creative reason.
So, let us celebrate:
The dream is dead! Long live the dream!
– – – – – – – – – – – – – – – – – – – – – – – –
– – – – – – – – – – – – – – – – – – – – – – – –
Not sure when this mini-explainer will go public (I may want to expand it into a full explainer, but, ugh, scope) but for now, please gift me any feedback, if you want! What parts were insightful, confusing, boring, too fast, too slow, steps I skipped? Any other suggestions for this piece, or future bonus mini-explainers?
Thank you again! I'll share more about what's going on with my life in the next Patreon update. But for now, enjoy having had your mind blown!
👀,
~ Nicky Case
P.S: Special Thanks to Paul Dancstep for lending me his copy of the book Gödel's Proof, which I vandalized with googly eyes as seen above. This book got me to finally read Gödel's original paper (well, "original" translated to English) and deep dive into this monolith in mathematics' history.
Comments
Mats Borges
Howdy! I'm trying to write about that same exact synthesis! Do you have any particular sources you like that talk about it?
Tim S
One thing I'd love some more help understanding is how proving the statement about just numbers proves the thing we encoded that way. Presumably it must be a very special encoding that proving the statement about these particular numbers proves the statement about statements that we encoded.
Nathan Borson
Duality is dead! Long live duality! There are so many implications and possible follow-ups, so I get the scoping problem! Like @Parker Bond, I went straight to Heisenberg's uncertainty principle (G="This electron has X position and velocity"). But this is plenty for one explainer, maybe ending with links to a few related (anti-)concepts. The mini-explainer did work for me, perhaps better than GEB, which I remember fondly but faintly from many decades ago. You've inspired me to dig in again, and synthesize that philosophy with ancient Buddhist teachings about the illusion of existence vs. non-existence (likewise true/false, good/evil, I/other, etc.). This mini-explainer strengthens my skepticism about all such dichotomies. Our minds strive to collapse the world of possibilities to yes vs. no, but every such simplification removes us further from sensing reality in its nuance and complexity.
Daniel Chin
It's always exciting to revisit this topic. Now have you read GEB? It turned Quinning into a school of art.
Vittorio
I enjoyed a lot this post, was kinda familiar with the proof and this was a nice overview/reminder! Suggestion for future posts: higher order logics
Vittorio
I had the same reading experience with these Hofstadter books, but after a reread of GEB I can only advise you to give it a second chance!
Ted
I liked this mini-explainer a lot, but then, I'm such a fan of this proof and the beautiful science that stemmed from it that it probably makes me a little biased. Reading Smullyan's book as a young student was the initial spark that led me towards doing formal logic and computability theory later in my studies. At the time I struggled a bit to understand Smullyan's book, so to make sure I was following the argument, I decided to implement the proof "for real", by writing code that would print the undecidable statement, following the book step-by-step. It was somewhat of a magical moment when I was done and I could look at a math statement I built "by hand" that essentially said "this sentence is unproveable". Even if that statement is, of course, completely illegible: https://desfontain.es/blog/proposition-indemontrable.txt At the time I also wrote a blog post (in French) to describe the process (https://desfontain.es/blog/proposition-indemontrable.html) and published the annotated source code (also in French): https://desfontain.es/blog/proposition-indemontrable.ml.html
Sid_Cypher
Since math was born of observations of natural world, like geometers just "measuring land" and herders/treasurers counting animals, and we still use it for practical worldly sciences thousands of years later, I think it is good that math is an open system, forever incomplete. It means we can keep adding and refinining knowledge from the actual observable world around us, the natural laws of which (like cosmic constants and symmetries) are also presumably and hopefully consistent. If our math turned out to be consistent, complete, perfectable, then that would philosophically, epistemologically signify that math is not curiosity, but blind pride and hubris, haha
Viniter
Hmmm... I think I get the gist. I get how the one-two punch would lead to the knockout, but I don't think I quite grasp the punches. The thing I struggle with is how you get from mapping letters onto the numbers, and doing what's essentially "string manipulation" using arithmetic, to making statements about the system of mathematics itself. I understand that real mapping would be more complex and encode a whole language, word definitions and all, but how do you imbue that with meaning? You're still just executing some complex arithmetic function F on some big number N and getting some other number M... how do you convince anyone thay "F(N) = M" has some implications about the consistency of the whole system of math? It probably comes down to my lack of understanding of how systems like Principia Mathematica work.
Josh Kushner
An amazing suggestion and now top of my reading list. Thank you!
Nicky Case
Oh whoops – another friend of mine got stuck on the same part, I should've been more clear on that part. "G" was referring to the same G from ~10 paragraphs earlier. If G says "There is *no* proof of G" Then if we prove we can't prove G, since that's what G *says*, that *does* prove G! I should've added a reminder of what G was at that point; will edit that for the final post, if/when that's released!
Nicky Case
Thank you for your kind words! > I wonder if am entire story can be written with a plot that is self referential and contradictory. That's a brilliant idea, and I think that actually *is* the plot of a few of the stories inside Douglas Hofstadter's "Gödel, Escher, Bach". That book has the dubious honor of "I think it deeply influenced me but also I only skimmed it and maybe read 25% of it in total, also I don't actually recall anything specific from it." (Hofstadter's follow-up "I Am A Strange Loop" is a more... straightforward read.)
Josh Kushner
Well this provided wonderful brain gymnastics for today! I wonder if am entire story can be written with a plot that is self referential and contradictory. A "Stranger than Fiction" plot could have a self contradicting conclusion where any character's journey narrated into existence must always be untrue, and yet it is true. It makes me feel free-will vs determinism tension.
narF
Was interesting. Thanks!
Parker Bond
Is the not being able to prove G proves G kind of like Schrodinger's Cat, where it is both proven and disproven at the same time? Or did the part before womp womp break my brain? (Yes)
