Logic Incompleteness – Proof of Gödel’s First Incompleteness Theorem

incompletenesslogicpopular-math

One encounters in books and YouTube videos various ways of describing Gödel's Incompleteness Theorems and their proof. My background is not at all in formal logic, and I want to check if my understanding below of how one can break down the idea of the proof of Gödel's First Incompleteness Theorem is (roughly) correct:

Given a formal system $X$, write

  • $W_X$ for the set of well-formed formulae,
  • $P_X \subset W_X$ for the set of provable well-formed formulae,
  • $\neg : W_X \to W_X$ for the negation function.

Theorem: Every sufficiently powerful consistent formal system $X$ has undecidable statements.

Idea of the proof:

  1. We have a function $\,\phi : W_X \to W_X$ [where $\phi(\mathbf{w})$ formalises the statement that $\mathbf{w} \in P_X$] with the property that $\,\phi^{-1}(P_X)=P_X$.
  2. Construct a formula $\mathbf{w}_0 \in W_X$ such that $\,\phi(\mathbf{w}_0)=\neg\mathbf{w}_0$.
  3. Suppose $\mathbf{w}_0 \in P_X$; i.e. (by 1) $\mathbf{w}_0 \in \phi^{-1}(P_X)$, so $\phi(\mathbf{w}_0) \in P_X$, i.e. (by 2) $\neg\mathbf{w}_0 \in P_X$, contradicting the consistency of $X$.
  4. Suppose $\neg\mathbf{w}_0 \in P_X$; i.e. (by 2) $\phi(\mathbf{w}_0) \in P_X$, so $\mathbf{w}_0 \in \phi^{-1}(P_X)$, i.e. (by 1) $\mathbf{w}_0 \in P_X$, contradicting the consistency of $X$.

Best Answer

  1. We have a function $\,\phi : W_X \to W_X$ [where $\phi(\mathbf{w})$ formalises the statement that $\mathbf{w} \in P_X$] with the property that $\,\phi^{-1}(P_X)=P_X$.

We'd usually write this function as $\varphi\mapsto\operatorname{Prov}(\ulcorner\varphi\urcorner).$ The property means $\operatorname{Prov}(\ulcorner\varphi\urcorner)$ is provable if and only if $\varphi$ is provable. Note that in slight contradiction with your statement of the theorem, this is a statement about both the strength and soundness of the theory... not just consistency. The theory must be strong in the sense that it proves all sentences are provable that are and must be sound in the sense that it doesn't prove any statements to be provable that aren't.

  1. Construct a formula $\mathbf{w}_0 \in W_X$ such that $\,\phi(\mathbf{w}_0)=\neg\mathbf{w}_0$.

This is the diagonalization step. Equality is generally too much to ask for, though. What we really want is for the theory to prove the equivalence: $\operatorname{Prov}(\ulcorner\varphi\urcorner)\iff \lnot \varphi$ for some $\varphi.$

  1. Suppose $\mathbf{w}_0 \in P_X$; i.e. (by 1) $\mathbf{w}_0 \in \phi^{-1}(P_X)$, so $\phi(\mathbf{w}_0) \in P_X$, i.e. (by 2) $\neg\mathbf{w}_0 \in P_X$, contradicting the consistency of $X$.

In other words, if $\varphi$ is provable, then $\operatorname{Prov}(\ulcorner\varphi\urcorner)$ is provable by 1 so by the provable equivalence in 2, $\lnot \varphi$ is provable and the system is inconsistent. Yep, that's right

  1. Suppose $\neg\mathbf{w}_0 \in P_X$; i.e. (by 2) $\phi(\mathbf{w}_0) \in P_X$, so $\mathbf{w}_0 \in \phi^{-1}(P_X)$, i.e. (by 1) $\mathbf{w}_0 \in P_X$, contradicting the consistency of $X$.

Yes, if $\lnot \varphi$ is provable, then by the equivalence $\operatorname{Prov}(\ulcorner\varphi\urcorner)$ is provable, so by 1, $\varphi$ is provable and the system is inconsistent.


So, yeah, this doesn't seem too far off as a high-level understanding. But note there is a lot glossed over involving constructing the provability predicate (part 1) and proving the diagonal lemma (for which the existence of the sentence constructed part 2 is a special case). The first part is technical but mostly straightforward and unsurprising so seems suitable to omit, whereas the diagonal lemma part seems worthy of further engagement if you want to really have a (rough) understanding the theorem.

Also, as I remarked below part 1, your assumptions in

Theorem: Every sufficiently powerful consistent formal system $X$ has undecidable statements.

are a bit incongruent with the proof sketch here. The direction of part 1 you used in part 4 assumes soundness, not just consistency of the system. Soundness assumptions are, to a certain extent, unavoidable in this version of the proof, though they can be sharpened somewhat (to an assumption of $\omega$-consistency or 1-soundness) and there are other proofs that work with just consistency alone.

Also, perhaps more imporantly, we need to stipulate that the theory is computably axiomatizable, if that is not already implicit in the definition of "formal system". This is necessary for step 1, to make expressing provability in arithmetic possible.