What Gödel Discovered (2020)
by qnleigh on 3/30/2026, 7:23:11 PM
Comments
by: dvt
This blog post gets <i>way</i> too caught up in Gödel numbers, which are merely a technical detail (specifically how the encoding is done is irrelevant). A clever detail, but a detail nonetheless. Author gets lost in the sauce and kind of misses the forest for the trees. In class, we used Löb's Theorem[1] to prove Gödel, which is much more grokkable (and arguably even <i>more</i> clever). If you truly get Löb, it'll kind of blow your mind.<p>[1] <a href="https://inference-review.com/article/loebs-theorem-and-currys-paradox" rel="nofollow">https://inference-review.com/article/loebs-theorem-and-curry...</a>
4/2/2026, 4:50:06 AM
by: qnleigh
I feel like it's nice to get the gist before diving into the gory details. The proof works by showing that just within the axioms of arithmetic, you can formally state the sentence "this sentence is unprovable." This has some very strange consequences:<p>- It can't be false, because if it's false then it is provable, and 'provable' means ' can be proven to be true.' That would be a contraction.<p>- So therefore it must be true, implying that it can't be proven. Consequently there are statements that are true but unprovable, even just within the axioms of arithmetic.<p>This is Gödel's incompleteness theorem in a nutshell. Most of the proof is spent developing machinery for doing logic, talking about provability, and ultimately getting a statement to refer to itself all using integers and their properties. It's quite satisfying because it doesn't require any super-advanced math, and yet the result is very deep.
4/2/2026, 5:53:48 AM
by: txhwind
The proof will be more friendly to nowadays programmers if we treat all "Gödel numbers" as bytecode of a programming language. It's trivial that functions like "prove" and "subst" can be implemented based on abilities like bytecode parsing and expression tree manipulation.
4/2/2026, 5:11:49 AM