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

Godel's Theorem

  1. Nov 15, 2005 #1
    One of Godel's results would imply that there must be arithmetic facts (formulae?) that cannot be derived from the peano axioms. (Unless my understanding here is wrong that is).

    So I wonder, has anyone found such a formula? How could it be proved?
     
  2. jcsd
  3. Nov 16, 2005 #2

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Your understanding is close. A better statement of the Gödel's First Incompleteness Theorem is that that any consistent and sufficiently powerful number theory must include undecidable propositions.

    The Continuum Hypothesis is the most famous undecidable proposition. Gödel proved no contradiction would result should the Continuum Hypothesis be added to ZF set theory. Cohen later proved no contradiction would result should the negation of the hypothesis be added to ZF.
     
  4. Nov 16, 2005 #3

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    There are a lot of very subtle nuances when dealing with formal logic.

    As a theory, the arithmetic of natural numbers is incomplete: that means there exists a statement P that cannot be proven or disproven from the axioms.

    However, one might have a model of the natural numbers. One of the things you can do with a model is to evaluate the truth of any statement.

    Therefore, for any model of the natural numbers, there must exist a true statement P that cannot be proven or disproven from the axioms. (Of course, P might be false in a different model of the natural numbers)


    Here's an example of a suitable statement P:

    http://mathworld.wolfram.com/GoodsteinsTheorem.html

    In formal set theory, we usually use a particular model of the natural numbers. Intuitively, each natural number is defined to be the set of all smaller natural numbers. So, 0 = {}, 1 = {0} (= {{}}), 2 = {0, 1}, et cetera. Goodstein's theorem is true for this model of the natural numbers.

    However, it would be false for some other model of the natural numbers.
     
  5. Nov 17, 2005 #4
    Goodstein's theorem sounds like what I was getting at.

    Interesting...
     
  6. Nov 23, 2005 #5

    benorin

    User Avatar
    Homework Helper

    I remember reading that if a statement cannot be proved from the Peano's axioms, the it is necessarily true. But memory doesn't serve where, or why that was so. Anybody gonna rebuke me?
     
  7. Nov 23, 2005 #6

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    If a statement cannot be proven from the axioms of peano then it is necessarily true? Erm, no, because 1+1=3 cannot be proven from the axioms since it is false.

    What kind of statement? In what model?
     
  8. Nov 25, 2005 #7

    benorin

    User Avatar
    Homework Helper

    sorry, perhaps it was if it is undecidable from the axioms...
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Godel's Theorem
  1. Godel's Theorem 2 (Replies: 6)

  2. Godel's Theorem (Replies: 2)

  3. Godel's Theorem (Replies: 8)

Loading...