# G0. Understanding Godel's First Incompleteness Theorem - A Roadmap

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.

### References

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.

- Gödel’s Proof, by Nagel and Newman.
- Gödel, Escher, Bach: An Eternal Golden Braid, by Hofstadter
- An Introduction to Gödel’s Theorems, by Peter Smith
- James Meyer’s Step by Step Guide to Godel’s Incompleteness Proof
- Logic Matters
- A translation of Godel’s oroginal paper