Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
add comment

3 Answers

up vote 2 down vote accepted

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

share|improve this answer
add comment

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.