In 1931 Godel proved something that truly shocked the mathematical world. This is Godel’s First Incompleteness Theorem:
Any consistent formal system F that is sufficiently strong is incomplete; i.e., there are statements of the language of F which can neither be proved nor disproved in F.
Almost every word in that statement has a precise technical meaning that will take work to understand. Merely understanding what Godel’s theorem means will be the goal of the first series of posts, and it will not a be a short series…
- What is a formal system?
- Meaning in a formal system
- Why do we care about formal systems?
- Propositional Logic
- Soundness, consistency, and completeness
- Inconsistent systems can prove anything
- Insufficiently strong formal systems: can they be both consistent and complete?
- Relations (in Logic, not in Love)
- First vs. Second Order Logic
- Expressibility and Capturability
- Primitive Recursive Functions
- A summary
Only after we have achieved a decent understanding of the statement can we hope to understand how to prove it; this will be the goal of a second series of posts (TBD).
Why am I writing this?
As with all my posts, I’m mostly writing this for me. It’s taken a lot of work getting to this point, where I feel like I understand Godel’s theorem well enough to (attempt to) explain it. Actually going through the exercise of writing it down has not only clarified my own understanding (and certainly pointed out holes), but it will also serve as a useful reference for my future self who will, inevitably, forget much of this.
So you might you want to read this? Surely \(\exists\) explanations by better writers, by better logicians, and both. The only reason that I can think of is that I have very recently gone from not understanding this topic to (mostly) understanding it. And remembering what it feels like to not already understand a topic is a huge asset when it comes to explaining it. I find the inability to remember what it feels like to not understand a topic once you’ve finally understood it rather fascinating; it might warrant a blog post of its own sometime in the future.
It might be helpful for you to know where I’m coming from. Here is a list of the main resources that I used to learn this topic.