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

  • I
  • Thread starter nomadreid
  • Start date
  • #1
nomadreid
Gold Member
1,481
150
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.)
 

Answers and Replies

  • #2
andrewkirk
Science Advisor
Homework Helper
Insights Author
Gold Member
3,886
1,454
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.
 
  • Like
Likes nomadreid
  • #3
9
8
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.
 
  • Like
Likes PeroK, nomadreid, andrewkirk and 1 other person
  • #4
nomadreid
Gold Member
1,481
150
Very interesting and extremely helpful, Nagase. I shall see if I can get hold of a copy. Thanks a million.
 
  • #5
9
8
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!
 
  • Like
Likes nomadreid
  • #6
nomadreid
Gold Member
1,481
150
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 :smile:) 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).
 

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

Replies
16
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
6
Views
2K
Replies
1
Views
2K
  • Last Post
Replies
2
Views
1K
Replies
1
Views
2K
Replies
3
Views
2K
Replies
24
Views
1K
Replies
2
Views
4K
Replies
25
Views
5K
Top