Gödel's first incompleteness theorem


by Jaime Sevilla Molina Jul 10 2016 updated Oct 16 2016

The theorem that destroyed Hilbert's program

[summary: Every [ consistent] and [ axiomatizable] extension of [ minimal arithmetic] is incomplete]

The first incompleteness theorem is a result about the existence of sentences of arithmetic that cannot be proved or disproved, no matter what axioms we take as true.

What Gödel originally proved was that every [ $~$\omega$~$-consistent] and [ axiomatizable] extension of Peano Arithmetic is incomplete, but the result was later refined to weaken the requirement of $~$\omega$~$-consistency to simple Consistency and the set of theorems that the extension had to prove to that of [ minimal arithmetic].

The heart of both proofs is the Diagonal lemma, which allows us express self-referential sentences in the language of arithmetic.

This put an end to the dream of building a [-complete] Logical system that axiomatized all of mathematics, since as soon as one was expressive enough to talk about arithmetic, incompleteness would kick in.

Interpretation from model theory

The first incompleteness theorem highlights the impossibility of defining the natural numbers with the usual operations of [ addition] and [ multiplication] in [ first order logic].

We already knew from Lowenhëim-Skolem theorem that there would be models of $~$PA$~$ which are not isomorphic to the usual arithmetic, but the first incompleteness theorem implies that some of those models disagree in the truth value of some theorems of this language (those are the undecidable sentences).