Godel Background

• Born 1906 in Austria, died 1978 in Princeton.
• Taught at University of Vienna before emigrating to US.
• Delivered his famous first incompleteness proof as a talk at a conference in the 1930s.
• Developed close friendship with Einstein, who helped him get both his job at Princeton and his citizenship.

The First Incompleteness Theorem
In simplest terms, Godel's First Incompleteness Theorem states that: for systems of sufficient strength (such as arithmetic with multiplication) the system is either inconsistent or incomplete.

Godel proves this by proving that it is possible to construct (in arithmetic with multiplication) a sentence that we can interpret as meaning, This sentence is not provable. We call this now a Godel Sentence. Note: all he has to do is prove this can be said in arithmetic, and as a consequence arithmetic must be either inconsistent or incomplete. Can you see why?

The proof is difficult, but we can consider it in the abstract, and also consider some simplified and analogous proofs.

Smullyan's helpful analogies
We have a theory with:

• Version 1
  • Elements: ~, P, N, (, ).
  • Sentences: any strings of the form P(X), PN(X), ~P(X) and ~PN(X), where X is some string is a sentence.
  • A norm is a string followed by that string. E.g., P(P), ~P(~P), and so on.
  • Interpret P to mean provable, N to mean norm, ~ to be not.
  • Find a sentence that is true but not provable.
• Version 2 (with a kind of Godel numbering).
  • Elements: ~, P, N, 1, 0.
  • Sentences: any string of oform PX, PNX, ~PX, ~PNX, where X is any number.
  • Godel numbering: 10, 100, 1000, 10000, and 100000 are the Godel numbers for ~, P, N, 1, 0.
  • A "norm" is an expression followed by its Godel number. E.g.: "PNP1001000100"
  • Interpret PX to mean X is printable. PNX means the norm of X is printable. ~PX means not printable X, and ~PNX means the norm of X is not printable.
  • Find a true sentence that the machine cannot print.

Summary
Let's remind ourselves of some terminology. Here is a rough description of our main concepts (they need to be precisely defined relative to a particular logical system--but don't worry about that detail):

• Completeness: all the truths are provable.
• Consistency: no falsehoods are provable.
• Decidability: there is an effective procedure to determine if some formula is provable.

I'd like for you to be able to take away the following:

• Godel's First Theorem: for systems of sufficient strength (such as arithmetic with multiplication), the system is either inconsistent or incomplete.
• Godel proves this first theorem by using Godel Numbering, which is a kind of coding that allows us to turn each expression of arithmetic into a sequence of numbers; and then we can use arithmetic itself to describe patterns (such as proofs) in these numbers.
• Godel uses this procedure to create a Godel Sentence, which we can interpret to mean something like "This sentence is not provable."
• Godel's Second Theorem: for systems of sufficient strength (such as arithmetic with multiplication) you cannot prove the consistency of that system from within that system.