# math into logic

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

-

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

-

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.

-
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). –  Ross Millikan Oct 1 '11 at 5:05
@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. –  Carl Mummert Oct 1 '11 at 22:07

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.

-