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.

Is Robinson Arithmetic complete in the sense of Gödels completeness theorem? And is Robinson Arithmetic incomplete in the sense of Gödels first incompleteness theorem? If RA is both it would be a good example to explain the different notions of "completeness" used in the two theorems mentioned.

share|improve this question
add comment

1 Answer

Gödel's completeness theorem isn't about theories but about the logic used in the language of a theory, namely about the connection between the syntax and semantics of that logic. The logic used to describe Robinson's arithmetic (first order logic) is complete and at the same time RA is not complete as a theory. The same applies to first order Peano Arithmetic. The logic used in the language of PA is complete but PA is not a complete theory. Same thing applies to ZFC. Generally, every incomplete theory described in first order logic has that property.

share|improve this answer
    
I thought Robinson's Arithmetic WAS complete as a theory. What am I misremembering? –  Jason DeVito Dec 4 '10 at 16:17
2  
@Jason: Robinson's arithmetic is incomplete and undecidable much like PA, but it's finitely axiomatized (en.wikipedia.org/wiki/Robinson%27s_Arithmetic). Maybe you're thinking about Presburger arithmetic which is decidable? –  Apostolos Dec 4 '10 at 16:35
    
Yes - it was Presburger arithmetic I was thinking of. Thank you for the clarification. –  Jason DeVito Dec 4 '10 at 17:14
1  
@Raskolnikov What tools do you have to define multiplication in Presburger? It's a worthwhile exercise to try it and see why you can't do it. –  Mark Reitblatt Dec 4 '10 at 17:23
1  
@Raskolnikov Yeah, that's the idea. The number of times you have to add "x" will not be constant. If you try to write it out in the formal language, you'll get stuck. –  Mark Reitblatt Dec 4 '10 at 19:05
show 3 more comments

Your Answer

 
discard

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