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

About Gödel incompleteness theorem

  1. Aug 25, 2014 #1
    I'm a starting amateur mathematician. I'm studying Gödel's incompleteness theorem and have a couple of rookie questions that I can't seem to sort out.
    1) In the text I'm reading it talks repeatedly about systems containing "addition and multiplication". Since multiplication can be derived from addition, why is it relevant to mention multiplication?
    2) If the G sentence is added to the set of axioms, there will be always another sentence G' that is undecidable, and if this one is added then there will be a G'', G''', etc. If there appears to be a systematic way of building this sentences, why it is not valid to include axioms to build all this kind of sentences?
    Thanks in advanced!! The subject is thrilling and I'm looking forward to read and learn much more.
  2. jcsd
  3. Aug 26, 2014 #2
    1) See Presburger Arithmetic; http://en.wikipedia.org/wiki/Presburger_arithmetic. Multiplication is not necessarily definable from addition. Note that this theory is demonstrably complete, consistent, and decidable.

    2) In Cantor's diagonal argument for the uncoutability of the reals, one starts with a countable list of real numbers and gives a construction of a number not on the list, demonstrating that no countable list of real numbers is complete. Simply adding the constructed number to the list doesn't "fix" the problem.

    Similarly Gödel's proof shows that for every consistent recursive list of axioms there is at least one statement which cannot be proven or disproven. Adding all of those statements as axioms, even in a recursive way, doesn't solve that problem. You still "end up" with a recursive list with its own Gödel sentence. Or to put it another way, every recursive list of Gödel sentences must be missing at least one Gödel sentence, just like every countable list of real numbers is missing at least one real number.
  4. Aug 27, 2014 #3
    Superb answer. Thanks a million gopher!!
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook