Gödel's first incompleteness theorem

The first in­com­plete­ness the­o­rem is a re­sult about the ex­is­tence of sen­tences of ar­ith­metic that can­not be proved or dis­proved, no mat­ter what ax­ioms we take as true.

What Gödel origi­nally proved was that ev­ery \(\omega\)-con­sis­tent and ax­iom­a­ti­z­able ex­ten­sion of Peano Arith­metic is in­com­plete, but the re­sult was later re­fined to weaken the re­quire­ment of \(\omega\)-con­sis­tency to sim­ple con­sis­tency and the set of the­o­rems that the ex­ten­sion had to prove to that of min­i­mal ar­ith­metic.

The heart of both proofs is the di­ag­o­nal lemma, which al­lows us ex­press self-refer­en­tial sen­tences in the lan­guage of ar­ith­metic.

This put an end to the dream of build­ing a com­plete log­i­cal sys­tem that ax­io­m­a­tized all of math­e­mat­ics, since as soon as one was ex­pres­sive enough to talk about ar­ith­metic, in­com­plete­ness would kick in.

In­ter­pre­ta­tion from model theory

The first in­com­plete­ness the­o­rem high­lights the im­pos­si­bil­ity of defin­ing the nat­u­ral num­bers with the usual op­er­a­tions of ad­di­tion and mul­ti­pli­ca­tion in first or­der logic.

We already knew from Lowen­hëim-Skolem the­o­rem that there would be mod­els of \(PA\) which are not iso­mor­phic to the usual ar­ith­metic, but the first in­com­plete­ness the­o­rem im­plies that some of those mod­els dis­agree in the truth value of some the­o­rems of this lan­guage (those are the un­de­cid­able sen­tences).



  • Mathematics

    Math­e­mat­ics is the study of num­bers and other ideal ob­jects that can be de­scribed by ax­ioms.