Notices
Results 1 to 15 of 15
Like Tree1Likes
  • 1 Post By Guitarist

Thread: Examples of Gödel's incompleteness theorem

  1. #1 Examples of Gödel's incompleteness theorem 
    Forum Freshman
    Join Date
    Jun 2009
    Posts
    25
    Dear all,

    I'm wondering whether there are any other examples of Gödel's incompleteness theorem in action other than statements such as "this statement is not true" (i.e. formalizations of the liar's paradox)?

    If not: then how exactly is his theorem relevant in the broader field of mathematics, seeing that only very specific kinds of metamathematical statements are involved?


    Reply With Quote  
     

  2.  
     

  3. #2  
    Forum Senior TheObserver's Avatar
    Join Date
    Jan 2012
    Location
    Alberta, Canada
    Posts
    351
    Godels incompleteness theorem is a statement about formal systems at least as complex as the natural numbers. It says that we cannot design an algorithm that is capable of proving all true statements that a formal system could make. Because of it, we can not use a system to prove the internal consistency of the system itself. We can't pull ourselves up with our own bootstraps so to speak. It is completely relevant to the very broad fields of mathematics (logic); metalogic or set theory for example, or even computer science, where questions about the provability of formal statements comes into the fore ground. However, for most areas of mathematics it is of very little practical consequence.


    Reply With Quote  
     

  4. #3  
    Brassica oleracea Strange's Avatar
    Join Date
    Oct 2011
    Location
    喫茶店
    Posts
    16,670
    One example is Continuum hypothesis. I don't know how important this is; i.e. whether any results with practical use would be affected if it were either true or false.
    Without wishing to overstate my case, everything in the observable universe definitely has its origins in Northamptonshire -- Alan Moore
    Reply With Quote  
     

  5. #4  
    Moderator Moderator Markus Hanke's Avatar
    Join Date
    Nov 2011
    Location
    Ireland
    Posts
    7,302
    I think it is quite fundamental so far as the question is concerned of whether there is a Theory of Everything that can be described in terms of mathematics. Is maths complete enough to explain everything in the universe, including the universe itself ? Is that even possible ?
    Do I have an answer ? No.
    Comments, anyone ??
    Reply With Quote  
     

  6. #5  
    Brassica oleracea Strange's Avatar
    Join Date
    Oct 2011
    Location
    喫茶店
    Posts
    16,670
    I suppose one way of looking at it is that mathematics is a tree of possibilities. Wherever there is an undecidable theorem (like the continuum hypothesis) you end with two different branches depending whether you assume it is true or fasle.

    A bit like geometry: you can choose Euclidean (parallel lines never meet) or different forms of non-Euclidean. It isn't necessarily that one is right and one is wrong, they have different applications.
    Without wishing to overstate my case, everything in the observable universe definitely has its origins in Northamptonshire -- Alan Moore
    Reply With Quote  
     

  7. #6  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,614
    ER, well don't get too carried away guys!

    Here's a fun way to think of one Goedel's 2 theorems, but it is just for illustration

    The set of symbols - letters - that make up an alphabet is finite, and therefore countable. In our case it has cardinality 26

    Suppose we make use of this fact to enumerate these, and, for reasons I will explain shortly, designate as follows: A = 10, B = 20, C = 30 etc.

    Then a word will be of the form 2050140 = BEN. This is clearly a number, i.e. an element in . Now I can stick these words together to make a sentence, sentences to make a paragraph, paragraphs to make a book, etc, and I will still have an element in . (Incidentally, I can include capitals, punctuation and spaces, and the following argument is the same)

    OK, so I simply used zero as a delimiter to avoid under-counting, that is, I know that 1020 = AB and not L = 12, which could happen if 12 = AB or L. So we see there is no word, sentence, paragraph, library, or even collection of libraries (Congress of Libraries??) that cannot be expressed as an element in the countable set

    Now is the powerset on the natural numbers - it is the set of all subsets of . Cantor's diagonal argument can be used to show this is uncountable. So, let us say that in a complete theory of numbers, for each element (subset recall) of the powerset there must be at least one true statement (using words, sentences, paragraphs,....), so there must be uncountably many true statements of number theory.

    {Edit in red follows, thanks to Strange's eagle eyes} Now "removing" a countable set of any cardinality, even if it infinite, from an uncountable set set still "leaves" us with an uncountable set. Therefore, there must be uncountably many MORE potentially true statements of number theory than there are words, sentences, paragraphs, books or libraries (since these are countable).

    It follows that any system that tries to describe number theory as a complete set of true statements is doomed to failure. This is example of an incompleteness theorem.
    Last edited by Guitarist; February 2nd, 2012 at 01:34 PM.
    Wintermute likes this.
    Reply With Quote  
     

  8. #7  
    Brassica oleracea Strange's Avatar
    Join Date
    Oct 2011
    Location
    喫茶店
    Posts
    16,670
    Quote Originally Posted by Guitarist View Post
    Now "removing" a countable set of any cardinality, even if it infinite, from an countable set set still "leaves" us with an uncountable set.
    I assume that should be uncountable?
    Without wishing to overstate my case, everything in the observable universe definitely has its origins in Northamptonshire -- Alan Moore
    Reply With Quote  
     

  9. #8  
    Moderator Moderator
    Join Date
    Jun 2005
    Posts
    1,614
    Yes, well spotted. Edit progress
    Reply With Quote  
     

  10. #9  
    New Member
    Join Date
    Jun 2012
    Posts
    1
    I have a question/comment related to the first post on this thread. The question whether any other examples existed of "unprovable" statements other than the liar's paradox one that Godel referenced in the proof of his incompleteness theorem.

    If other such "unprovable" statements did exist (which I do not believe), how would you know when you encountered one? e.g. for years, Fermat's last Theorem may have been "unprovable" - but it finally was proven some years ago. Is Goldbach's Conjecture unprovable? how abut the various conjectures related to the infinite number of twin primes, etc.? Are they unprovable?

    This leads me to think that the only statements that are unprovable are only these self-referencing ones (for which there are an infinite number of, to be sure) - but are there any others? and how would you know if you encountered one?


    Can we say they're unprovable just because they have not yet been proven.

    My point is that it would be impossible to construct a list of all truths
    Reply With Quote  
     

  11. #10  
    Brassica oleracea Strange's Avatar
    Join Date
    Oct 2011
    Location
    喫茶店
    Posts
    16,670
    Quote Originally Posted by ggimpoli View Post
    Can we say they're unprovable just because they have not yet been proven.
    There are two classes of unprovable theorems: those we can prove are unprovable and those we can't.
    Without wishing to overstate my case, everything in the observable universe definitely has its origins in Northamptonshire -- Alan Moore
    Reply With Quote  
     

  12. #11  
    Forum Bachelors Degree
    Join Date
    Jun 2012
    Posts
    493
    Quote Originally Posted by ggimpoli View Post
    I have a question/comment related to the first post on this thread. The question whether any other examples existed of "unprovable" statements other than the liar's paradox one that Godel referenced in the proof of his incompleteness theorem.

    If other such "unprovable" statements did exist (which I do not believe), how would you know when you encountered one? e.g. for years, Fermat's last Theorem may have been "unprovable" - but it finally was proven some years ago. Is Goldbach's Conjecture unprovable? how abut the various conjectures related to the infinite number of twin primes, etc.? Are they unprovable?

    This leads me to think that the only statements that are unprovable are only these self-referencing ones (for which there are an infinite number of, to be sure) - but are there any others? and how would you know if you encountered one?


    Can we say they're unprovable just because they have not yet been proven.

    My point is that it would be impossible to construct a list of all truths
    But ,list or not...cardinality aside, Shouldnt there be a set containing all truths needed to describe everything in a certain moment?

    Isnt there a logical space? Containing all possibilities?
    Reply With Quote  
     

  13. #12  
    Forum Professor river_rat's Avatar
    Join Date
    Jun 2006
    Location
    South Africa
    Posts
    1,510
    In a vacuous way yes, for example consider the theory of arithmetic where we take as axioms all true statements about arithmetic (the so called true arithmetic). This is a complete theory and so everything that is true about the natural numbers is provable in it (kind of by design) but there is no way to determine if a general statement is an axiom of this theory.
    As is often the case with technical subjects we are presented with an unfortunate choice: an explanation that is accurate but incomprehensible, or comprehensible but wrong.
    Reply With Quote  
     

  14. #13  
    Forum Bachelors Degree
    Join Date
    Jun 2012
    Posts
    493
    Quote Originally Posted by river_rat View Post
    In a vacuous way yes, for example consider the theory of arithmetic where we take as axioms all true statements about arithmetic (the so called true arithmetic). This is a complete theory and so everything that is true about the natural numbers is provable in it (kind of by design) but there is no way to determine if a general statement is an axiom of this theory.
    Hi! You surprise me. How is a proof achieved? How do we search through the axioms? Youre not pulling my leg,are you?
    Sigh...I wish I were a Mathematician...First thing I would do would be to prove the Banach Tarski theorem wrong
    Reply With Quote  
     

  15. #14  
    Forum Professor river_rat's Avatar
    Join Date
    Jun 2006
    Location
    South Africa
    Posts
    1,510
    A proof of X in this theory consists of pointing at the axiom X if it is true and at the Axiom ~X if it is false. Hence the vacuous nature of the theory.

    Why do you want to prove the Banach-Tarski theorem wrong? That would be like proving the parallel postulate in Euclidean geometry?
    As is often the case with technical subjects we are presented with an unfortunate choice: an explanation that is accurate but incomprehensible, or comprehensible but wrong.
    Reply With Quote  
     

  16. #15  
    Forum Bachelors Degree
    Join Date
    Jun 2012
    Posts
    493
    Quote Originally Posted by river_rat View Post
    A proof of X in this theory consists of pointing at the axiom X if it is true and at the Axiom ~X if it is false. Hence the vacuous nature of the theory.

    Why do you want to prove the Banach-Tarski theorem wrong? That would be like proving the parallel postulate in Euclidean geometry?
    Isnt it the one where you disassemble a sphere and then use the pieces to build two spheres identical with the first?
    I either misunderstand or it cant be so, since then a perpeetum mobile seems possible.
    Just turn the second sphere into energy and repeat the process ad inf.

    Er... wait a minute... (pinching my arm...yes i AM on speaking terms with a mathematician...)

    Would you perhaps help me by checking an argument of mine for errors?

    Suppose:
    1 x = "x is not true"
    Then:
    2 x is true if and only if "x is not true" is true
    And:
    3 x is true if and only if x is not true
    Therefore:
    4 It is not true that x = "x is not true" (QED)

    Is the argument valid?

    Edit: Oh well if you understand Tarski then I might as well show the whole argument:

    Look at the following system:

    1 x is not true
    2 x = "x is not true"

    For some values of x sentence 2 is empirically true:_

    1 sentence 1 is not true
    2 sentence 1 = "sentence 1 is not true

    And out of 1 and 2 we get:
    3 sentence 1 is true

    but if sentence 2 is BOTH logically false and empirically true it is not well formed,
    and therefore sentence 3 doesnt follow after all! (QED)

    PS: If so far I am not in error then next stop is Goedel.

    A goedel sentence is a selfreferential sentence x such that x = "x is not provable"

    Let us see if such "undecidable" sentences may exist...Suppose:

    1 x = "x is not provable"
    Then we get:
    2 x is provable if and only if "x is not provable" is provable
    And since provable sentences are true we get:
    3 x is provable if and only if x is not provable

    And the conclusion is unavoidable (?):

    4 There is no sentence x such that x = "x is not provable"

    This is an indirect proof perhaps, but isnt it valid nonetheless?

    There are no undecidable sentences unless you break the laws of logic!
    Last edited by sigurdW; July 1st, 2012 at 02:40 PM.
    Reply With Quote  
     

Similar Threads

  1. boiling point and melting point examples
    By apjayanap in forum Chemistry
    Replies: 1
    Last Post: August 29th, 2010, 02:50 AM
  2. Replies: 25
    Last Post: March 20th, 2009, 09:48 AM
  3. Mean value theorem
    By myoplex11 in forum Mathematics
    Replies: 1
    Last Post: November 19th, 2006, 11:43 AM
  4. Fractals Examples
    By TonyVulcan in forum Mathematics
    Replies: 2
    Last Post: October 14th, 2006, 02:37 PM
  5. Examples of energy being changed to matter...
    By kingjacob in forum Physics
    Replies: 3
    Last Post: September 7th, 2006, 08:28 PM
Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •