# Proof of Gödel's first incompleteness theorem

## Weak form

The weak Gödel’s first in­com­plete­ness the­o­rem states that ev­ery $$\omega$$-con­sis­tent ax­iom­a­ti­z­able ex­ten­sion of min­i­mal ar­ith­metic is in­com­plete.

Let $$T$$ ex­tend min­i­mal ar­ith­metic, and let $$Prv_{T}$$ be the stan­dard prov­abil­ity pred­i­cate of $$T$$.

Then we ap­ply the di­ag­o­nal lemma to get $$G$$ such that $$T\vdash G\iff \neg Prv_{T}(G)$$.

We as­sert that the sen­tence $$G$$ is un­de­cid­able in $$T$$. We prove it by con­tra­dic­tion:

Sup­pose that $$T\vdash G$$. Then $$Prv_ {T}(G)$$ is cor­rect, and as it is a $$\exists$$-rudi­men­tary sen­tence then it is prov­able in min­i­mal ar­ith­metic, and thus in $$T$$. So we have that $$T\vdash Prv_ {T}(G)$$ and also by the con­struc­tion of $$G$$ that $$T\vdash \neg Prv_{T}(G)$$, con­tra­dict­ing that $$T$$ is con­sis­tent.

Now, sup­pose that $$T\vdash \neg G$$. Then $$T\vdash Prv_{T}(G)$$. But then as $$T$$ is con­sis­tent there can­not be a stan­dard proof of $$G$$, so if $$Prv_{T}(x)$$ is of the form $$\exists y Proof_{T}(x,y)$$ then for no nat­u­ral num­ber $$n$$ it can be that $$T\vdash Proof_ {T}(\ulcorner G\urcorner,n)$$, so $$T$$ is $$\omega$$-in­con­sis­tent, in con­tra­dic­tion with the hy­poth­e­sis.

## Strong form

Every con­sis­tent and ax­iom­a­ti­z­able ex­ten­sion of min­i­mal ar­ith­metic is in­com­plete.

This the­o­rem fol­lows as a con­se­quence of the un­de­cid­abil­ity of ar­ith­metic com­bined with the lemma stat­ing that any com­plete ax­iom­a­ti­z­able the­ory is undecidable

Parents: