Results 1 to 5 of 5

Math Help - Gödel's Incompleteness Theorem

  1. #1
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176

    Gödel's Incompleteness Theorem

    Hi,

    I was wondering if someone could please provide an example of something that is "unprovable"? Is the Continuum Hypothesis such an example?

    Also, I remember reading a while ago about the possible existence of theorems that were "unprovable" and so were true (because if they were false there would exist a counter-example, which would be a proof that they were false). However, surely this is a contradiction? Surely any example that could be proven false by a counter example cannot be proven to be unprovable?

    I hope those questions make sense...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Deadstar's Avatar
    Joined
    Oct 2007
    Posts
    722
    Am I right in thinking that the Axiom of Choice is unprovable? But its just taken as fact.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by Swlabr View Post
    Hi,

    I was wondering if someone could please provide an example of something that is "unprovable"? Is the Continuum Hypothesis such an example?

    Also, I remember reading a while ago about the possible existence of theorems that were "unprovable" and so were true (because if they were false there would exist a counter-example, which would be a proof that they were false). However, surely this is a contradiction? Surely any example that could be proven false by a counter example cannot be proven to be unprovable?

    I hope those questions make sense...
    Unprovable in the sense required here means unprovable within a given axiomatic system (complete with rules of deduction), which (usually) is rich enough to contain arithmetic, meaning Russel and Whiteheads system from their Principia Mathematica.

    If a theorem is unprovable (that is can neither be proven nor disproven) in such a system there can be no counter example since just displaying it is a proof that the purported theorem is false.

    So any candidate for theoremhood within such a system that has a counter example cannot be unprovable, so all unprovable theorems posses no counterexamples.

    (there is probably more than one fundamental error in the above)

    CB
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2008
    From
    Paris, France
    Posts
    1,174
    Quote Originally Posted by Swlabr View Post
    Hi,

    I was wondering if someone could please provide an example of something that is "unprovable"? Is the Continuum Hypothesis such an example?

    Also, I remember reading a while ago about the possible existence of theorems that were "unprovable" and so were true (because if they were false there would exist a counter-example, which would be a proof that they were false). However, surely this is a contradiction? Surely any example that could be proven false by a counter example cannot be proven to be unprovable?

    I hope those questions make sense...
    (There may as well be errors in my answer since I don't specialize in logic but that's the way I understand it, and I'd be pleased to have the opinion of someone more knowledgeable about it)

    I think a theorem may be unprovable in two ways, relatively to its truth.

    "Provable" presumes that a list of axioms has been chosen. A theorem is true if it is true in any mathematical model that satisfies the axioms. A theorem is provable if it can be deduced, step by step, using the axioms and usual deduction rules (this leads to a kind of constructive vision of truth: is "true" (= provable) what I can prove is true).

    A theorem may be unprovable because:

    1) The axioms are not sufficiently precise to settle the question: there are models where the theorem is true, others where it is false. This is the case of Euclid's fifth postulate, it can't be proved from the others (cf. non-Euclidean geometries). I think this is the case of CH (the continuum hypothesis) or for AC (axiom of choice), but I'm not sure, and I'm not sure we know or can know. In a sketchy way, that would mean that the abstract mathematical universe that is defined by the "usual axioms" is actually not completely defined by them, and some properties remain free, like CH. We can choose to work with a more precisely specified model of maths by choosing to take CH as a new axiom. Or by choosing to take its negation. Both choices are equally wise (logically), they induce no additional contradiction.

    2) The axioms are sufficiently precise so that the theorem is true in every model, but the truth of the theorem can't be proved from the axioms. This is where Gödel's incompleteness theorem is involved: it gives an example of such a situation. But not a very simple or interesting one... A few "elementary" examples were found since then, the most well-know is Goodstein's theorem I think.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by Laurent View Post
    2) The axioms are sufficiently precise so that the theorem is true in every model, but the truth of the theorem can't be proved from the axioms. This is where Gödel's incompleteness theorem is involved: it gives an example of such a situation. But not a very simple or interesting one... A few "elementary" examples were found since then, the most well-know is Goodstein's theorem I think.

    Ah, okay. It is this case I am interested in. Thanks for the example.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Gödel numbering
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 19th 2011, 10:36 PM
  2. Replies: 4
    Last Post: January 10th 2011, 09:51 AM
  3. Completeness and Incompleteness theorems
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: January 8th 2011, 12:07 PM
  4. Incompleteness thereom
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 28th 2010, 11:15 AM
  5. Replies: 0
    Last Post: November 27th 2009, 11:35 AM

Search Tags


/mathhelpforum @mathhelpforum