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".

$\endgroup$

3 Answers 3

4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ For those who have read Smullyan and Frankel, do you have a recommendation for second order logic? It seems people shy away, so I would be interested in a book that talks about that (understanding that it will probably be a promoter of second order). $\endgroup$ Commented Oct 1, 2011 at 5:05
  • $\begingroup$ @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. $\endgroup$ Commented Oct 1, 2011 at 22:07
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .