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: