Embracing the Incompleteness of Knowledge

I was in high school when I read “Gödel, Escher, Bach” by Douglas Hofstadter.

To paraphrase Gödel’s incompleteness theorems:

1. Any mathematical system rich enough to do arithmetic cannot be both consistent and complete. There will always be true statements it cannot prove.

2. Any assurance of its consistency can only be made from outside.

So, it either contains contradictions or it cannot be provably complete from within itself.

Gödel’s theorems are beautiful. For their transcendent genius. For their elegance. For how they challenge certainty within a system of thought.

The proof applies to specific mathematical systems. But it is an interesting challenge to any system of thought sophisticated enough to attempt to understand itself. Can it be proven consistent within its own frame of reference? Or are there things unknowable or unverifiable within those constraints?

At any rate, it informs my total skepticism in human certainty.

Today I took the time to dive into Gödel’s proof and better understand it by restating it in words (my words). Here goes…

Gödel’s Proof of his Incompleteness Theorem

S is a mathematical system bounded by a set of statements assumed to be true (axioms) and capable of at least basic arithmetic.

Within that system we can assign a Gödel number, a unique integer calculated using prime factorization, to every symbol, formula, and proof in S. This means every formula constructible within S has exactly one integer address and every integer address corresponds to exactly one formula.

The basic arithmetic also enables us to create a predicate Provable(n) which returns true or false. Provable is true when there exists an integer m that both decodes into a valid proof sequence in S and has the formula with Gödel number n as its final conclusion (i.e. it is a proof for the formula with Gödel number n).

Within S, we can create a mathematical statement G using Gödel’s Diagonal Lemma to claim that no proof of G exists within S. G has Gödel number ⌈G⌉ and states that Provable(⌈G⌉) is false.

G ↔ ¬Provable(⌈G⌉), ¬ represents “not”, as in not Provable.

Assume S is consistent and that an integer m exists, where m decodes into a valid proof in S whose final conclusion has Gödel number ⌈G⌉. Then S has a valid proof of G. Therefore Provable(⌈G⌉) is true.

But G asserts ¬Provable(⌈G⌉).

S has now proved both Provable(⌈G⌉) and ¬Provable(⌈G⌉) simultaneously.

Contradiction. If S is consistent, m must not exist. No proof of G can exist in S. So, S contains a true statement G that it cannot prove.

Therefore if S is consistent, it is incomplete. To be complete it must be inconsistent.