2
$\begingroup$

How does one translate Godel sentence about the integers into "This sentence is not provable" and Rosser's sentence into "If this sentence is provable, there is a shorter proof of its negation".

If I write down a sentence in logic, how can one translate it into a statement about the natural integers?

Which words am I allowed to use such that it can be translated into a mathemtical statement abouth the integers?

What is a precise way to translate logical statements into mathemtical statements about integers? For instance the AND operator and "This sentence" and "X is provable".

3 Answers 3

2

The main points are these:

  • you need to have a complete formalization of the language and the deductive system (i.e. the deduction rules)
  • once the language is completely formalized you can define a codification which attach a number to any formal statement (aka formula)
  • once the deductive system is formalized and the language is coded with numbers you can express all the deductive rules as complex arithmetical operations on the code-numbers
  • the statement "from $A$ follows $B$ throught the deduction rules" now can be translated into an arithmetical statement of the form "from the number $Code(A)$ you can derive the number $Code(B)$ by the application of these arithmetical operations"
  • so at this stage any statement about provability of formulas has been converted into a statement about numbers and arithmetics.

To carry on each of these steps several technical problems need to be solved, see the references above for the details.

4

It's rather a long story, and the best way to understand it is probably to work your way through a proof in a logic textbook or in a popularization such as Nagel and Newman.

  • 0
    @Ross: the two best references for second-order logic are Shapiro's *Foundations without foundationalism* and Simpson's *Subsystems of second-order arithmetic*. There is no great reference at the undergraduate level, although a few textbooks mention it.2011-10-01
2

An important tool used in these types of constructions is Gödel's β function. Also these Wikipedia articles cover the main ideas:

Gödel numbering

Proof sketch for Gödel's first incompleteness theorem