# Gödel's 1st Incompleteness Thm: Min Arithmetic Req'd?

• I
In summary, the conversation discusses the minimum requirement for a theory of numbers to prove Gödel's First Incompleteness Theorem. Robinson Arithmetic is shown to be the weakest finitely axiomatizable theory that is essentially undecidable, while a weaker theory called R is also proven to be essentially undecidable but not finitely axiomatizable. The book "Undecidable Theories" by Tarski, Mostowski, and Robinson is recommended as a resource for further reading.

Gold Member
I often read (for example, in Wikipedia on "Rosser's Trick") that in order for a proof of Gödel's First Incompleteness Theorem, one assumes an efficient consistent theory of numbers which includes a "sufficient fragment of elementary arithmetic". What minimum would qualify? Is Robinson's Q a minimum? (Among others, obviously.)

Robinson Arithmetic is certainly sufficient, and is what is used in the versions of the proof that I have read.
I don't know if any of the Robinson axioms can be removed while still leaving the incompleteness theorem in place. My guess would be No, but I've never seen any investigation of it.

I suggest reading Tarski, Mostowski, and Robinson's Undecidable Theories, which shows that (a) Robinson's arithmetic is the weakest finitely axiomatizable theory which is essentially undecidable (cf. Theorem 11, where they prove that the omission of any of its seven axioms makes the theory decidable); (b) there is, however, a weaker theory which is not finitely axiomatizable and which is also essentially undecidable (they call it R in their paper). Using ##\Delta_n## as an abbreviation of ##S(S(\dots(0)))## (the successor function applied n times to 0), the axioms for R consist in the following schema (p. 53):

1. ##\Delta_p + \Delta_q = \Delta_{p+q}##;
2. ##\Delta_p \times \Delta_q = \Delta_{p \times q}##;
3. For each ##p, q## such that ##p \not =q##, ##\Delta_p \not = \Delta_q##;
4. ##x \leq \Delta_p \rightarrow x = \Delta_0 \vee \dots \vee x = \Delta_p##;
5. ##x \leq \Delta_p \vee \Delta_p \leq x##.

On pages 53-54, they show that all these axioms are derivable from Q (that is, Robinson's Arithmetic), thus, that R is weaker than Q. Next, they prove (Theorem 6) that every recursive function is definable in R. This, coupled with Corollary 2 (if T is a consistent theory in which all recursive functions are definable, then T is essentially undecidable), gives the result that R is essentially undecidable. Notice that, since R is recursively axiomatizable, it follows, by Turing's theorem (if a theory is recursively axiomatizable and complete, it is decidable), that it is incomplete.

PeroK, nomadreid, andrewkirk and 1 other person
Very interesting and extremely helpful, Nagase. I shall see if I can get hold of a copy. Thanks a million.