# Proof of Gödel's first incompleteness theorem

## Weak form

The weak Gödel’s first incompleteness theorem states that every $$\omega$$-consistent axiomatizable extension of minimal arithmetic is incomplete.

Let $$T$$ extend minimal arithmetic, and let $$Prv_{T}$$ be the standard provability predicate of $$T$$.

Then we apply the diagonal lemma to get $$G$$ such that $$T\vdash G\iff \neg Prv_{T}(G)$$.

We assert that the sentence $$G$$ is undecidable in $$T$$. We prove it by contradiction:

Suppose that $$T\vdash G$$. Then $$Prv_ {T}(G)$$ is correct, and as it is a $$\exists$$-rudimentary sentence then it is provable in minimal arithmetic, and thus in $$T$$. So we have that $$T\vdash Prv_ {T}(G)$$ and also by the construction of $$G$$ that $$T\vdash \neg Prv_{T}(G)$$, contradicting that $$T$$ is consistent.

Now, suppose that $$T\vdash \neg G$$. Then $$T\vdash Prv_{T}(G)$$. But then as $$T$$ is consistent there cannot be a standard proof of $$G$$, so if $$Prv_{T}(x)$$ is of the form $$\exists y Proof_{T}(x,y)$$ then for no natural number $$n$$ it can be that $$T\vdash Proof_ {T}(\ulcorner G\urcorner,n)$$, so $$T$$ is $$\omega$$-inconsistent, in contradiction with the hypothesis.

## Strong form

Every consistent and axiomatizable extension of minimal arithmetic is incomplete.

This theorem follows as a consequence of the undecidability of arithmetic combined with the lemma stating that any complete axiomatizable theory is undecidable

Parents: