Bonus Mini-explainer: Gödel's Proof!

(⏱ 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.