# What is a sufficient piece of arithmetic for Gödel's first incompleteness theorem

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

andrewkirk
Homework Helper
Gold Member
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
Gold Member
Very interesting and extremely helpful, Nagase. I shall see if I can get hold of a copy. Thanks a million.

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!