2
$\begingroup$

I have two questions actually.

Gödel's theorem is usually stated as applying to theories that are at least as strong as Peano's Arithmetic. But I've read that Robinson's Arithmetic (weaker than PA) is also subject to incompleteness, so I guess the hypothesis of Godel's theorem can be relaxed to apply to weaker theories than PA. What's the weakest theory to which it applies ?

Second question, Godel's theorem itself is proved in some mathematical theory. What theory is this ? I think it can be done in Robinson's Arithmetic but can it be done in even weaker theories ? Are these theories strong enough so that Godel's incompleteness applies to them ? Or can they prove their own consistency ?

Improve this question
$\endgroup$
4
  • $\begingroup$ The classical reference is: Tarski-Mostowski-Robinson : Undecidable theories. $\endgroup$
    – Goldstern
    Commented Dec 10, 2016 at 10:54
  • 1
    $\begingroup$ The first incompleteness theorem applies only to axiomatic systems defining sufficient arithmetic to carry out the necessary coding constructions (of which Gödel numbering forms a part). The axioms of Q [Robinson Arithmetic] were chosen specifically to ensure they are strong enough for this purpose. Thus the usual proof of the first incompleteness theorem can be used to show that Q is incomplete and undecidable. (en.wikipedia.org/wiki/Robinson_arithmetic) $\endgroup$
    – David Roberts ♦
    Commented Dec 10, 2016 at 11:00
  • $\begingroup$ Thanks ! So if I understand correctly there is no theory weaker than Robinson arithmetic to which the incompleteness theorems can be applied. And what about theories like PRA or IΔ0+Ω1, I don't understand yet what they are but they seem to be weaker than Robinson Arithmeric, is this true ? $\endgroup$
    – Jofil
    Commented Dec 10, 2016 at 12:19
  • $\begingroup$ @Jofil I'm not quite saying that. The answers at the linked duplicate question give more info. I just thought you'd like to know about Q being able to implement Gödel's theorem about itself. $\endgroup$
    – David Roberts ♦
    Commented Dec 10, 2016 at 23:04

0

Reset to default

Browse other questions tagged .