Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Jun 1, 2016 #1
    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.)
  2. jcsd
  3. Jun 1, 2016 #2


    User Avatar
    Science Advisor
    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.
  4. Jun 2, 2016 #3
    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.
  5. Jun 2, 2016 #4
    Very interesting and extremely helpful, Nagase. I shall see if I can get hold of a copy. Thanks a million.
  6. Jun 3, 2016 #5
    You're welcome. Fortunately, the book is available as a very cheap Dover paperback, so it won't cost you much!
  7. Jun 3, 2016 #6
    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).
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted

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