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

[nomadreid]

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

 

[andrewkirk]

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.

 

[Nagase]

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.

 

[nomadreid]

Very interesting and extremely helpful, Nagase. I shall see if I can get hold of a copy. Thanks a million.

 

[Nagase]

Very interesting and extremely helpful, Nagase. I shall see if I can get hold of a copy. Thanks a million.

You're welcome. Fortunately, the book is available as a very cheap Dover paperback, so it won't cost you much!

 

[nomadreid]

Nagase, you make the assumption that I am in a place where I have easy access to the purchase of Dover paperbacks. Since I am in a place where English is not an official language, there are only three ways to get such books: ordering from abroad (and sometimes the shipping is more than the book), or getting it online (which I have managed to do ) or to find it in one of the obscure little bookshops carrying used English books (given that these bookshops contain mainly detective and romance fiction, the probability here is less than the proverbial epsilon).