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. May 10, 2003 #1


    User Avatar
    Science Advisor

    Greetings !

    O.K. first of all I'd like to say I only
    had the MOST superficial look at it as
    possible and I'll probably pass out
    if I even see the tiniest fraction of
    the math involved in the actual proof.
    So, since my humble doubts that I wish
    to express here are complete BS, this
    thread will at least, hopefully, benefit
    those of you whoos acqaintance with this
    is as pathetic as mine. Enjoy the reading.

    Now, to the subject, here's a couple of links :

    My pathetic understanding :
    As I see it through a partial glance
    at the above explanations Godel's Theorem
    is basicly a mathematical Liar's Paradox
    (A liar says: I'm a liar).
    Here's the G sentence (which supposedly contains
    it in mathematical form) from the first link :
    " G: The arithmoquine of "The arithmoquine of
    a is not a valid TNT theorem-number" is not
    a valid TNT theorem-number. "

    What's unclear to me ?

    Well, the following: What is a liar in math ?
    How can you use "a" in math if it's not valid ?

    I understand you can say 1 does not equal 2.
    But, how can you use it for a more constructive
    argument ? You're turning a contradiction into
    a part of an argument and you can't do that.
    To me, it seems like using nothing in physics
    to explain physical effects - you just can't do
    that, it makes no sense within the system.

    A statement/number/whatever in math has definite
    values/value ranges - true/false, real number/
    natural number/...
    BUT, if it's INVALID - it's NOT an axiom.
    It can NOT be used to construct an argument
    WITHIN that abstract system. Can it ?

    So, you see my pathetic dillema here with
    the certain simple solution that I'm simply
    too stupid or lazy to get. Feel free to humiliate
    me in public so that I may learn something.

    Thanks !

    Live long and prosper.
    Last edited: May 10, 2003
  2. jcsd
  3. May 11, 2003 #2
    Godels theorema states that any formal system of logic (f.i. mathematics) can not be both complete and consistent.
    That is because in any formal system we can find 'statements' that can not be expressed using the logic rules of that system, but which are nevertheless true, which means the system can not be complete.
    If we try to 'complete' the system though, by adding such statements, it can be shown that inconsistencies occur. As in the example fo the TNT number G, which claims that itself can not be a number within TNT. But when we add G to TNT, is is a TNT number, so that makes an inconsistency!
    So this means that it is impossible to create a formal system of logic that is both complete and both consistent. Of course for that it also must be proved that there are not formal systems of logic which are stronger then TNT.
  4. May 11, 2003 #3
    I don't understand it.
    That's interesting that it relates to the liars paradox I was just thinking about that last week. The old question that if everything the liar says is a lie how can they say "everything I say is a lie", and this be true? Then I got a notion that this statement could be true and still be a lie. The reason is that following the reasoning of it forms a contradiction and paradox which is in itself a form of lying, so that a complete liar could make this truthfully lying statement and still be lying.
  5. May 11, 2003 #4


    User Avatar
    Science Advisor

    Re: Re: Godel's Theorem

    Greetings !
    I still don't get it. If G IS a TNT number
    then it is false to claim it is not. If G
    is NOT a TNT number then it is equivalent to
    saying 1=2 and then using this in other
    operations like an axiom, despite the fact
    that it clearly contradicts other axioms
    of the same system. I just can't see how
    you can arrive at that contradiction within
    the enitial axioms of math.

    Now, I'll try another approach here in my
    (probably very pathetic to those who know this
    stuff ) attempt to understand this subject:
    I want to construct an abstract system.
    So, what do I do ?
    I first define some end-points or
    entities/relations. In math these are
    stuff like numbers, numerical operations and
    much more.
    Why did I also call them end-points ?
    Because within the arguments of my abstract
    system they are the most basic consituents
    that can not be expalined. Why did I put the
    entities and the relations together ?
    Because entities and relations are just
    matters of perspective.

    Now, provided that I did all of the above
    I am now facing a potential dillema:
    How can I know for certain = prove that
    none of the exioms contradict each other ?
    And, if it is at all possible then - can
    I do this within the system itself ?
    Also, in general, how do I even begin to
    construct such an argument and how deep
    do I need to go to try and prove it (in
    terms of the system's practice complexity) ?

    Thanks !

    Live long and prosper.
    Last edited: May 11, 2003
  6. May 11, 2003 #5
    Re: Re: Re: Godel's Theorem

    The problem with the number "G" is that "G" claims about ITSELF that it is not part of TNT. If we ADD G to TNT , we have a inconsistency.
    If we do NOT add G to TNT, it is shown that TNT is incomplete.
  7. May 12, 2003 #6


    User Avatar
    Science Advisor

    Re: Re: Re: Re: Godel's Theorem

    Greetings heusdens !
    How's that ?
    Why would it be incomplete without G ?
    Why would it be complete if we add something
    invalid to it ? Is there even such a notion as
    invalid that is possible to observe from
    WITHIN the system (math) ? For example, can
    I say (in the real world) that I add "nothing"
    to my drink and stir it ?

    Thanks !

    Live long and prosper.
  8. May 12, 2003 #7
    Re: Re: Re: Re: Re: Godel's Theorem

    Your intend of this post was to clearify the theorema of Godel, right?

    Well the theorema itself is a long mathematical proof of some number system TNT. You would have to work out the proof of this theorema yourself, to know all the details.

    What comes up as a conclusion of the theorema, is that for any formal system, it can be proved that either the formal system is incomplete, or the formal system is inconsistent.

    A nice book about Godel's theorema is the book "Godel, Escher and Bach" from Douglas Hofstaedter.

    Remember that G is not just a number, but is a statement, expressed in formal notation of TNT, but is coded in numbers.
  9. May 12, 2003 #8
    Being probably even more pathetic than you older guys and risking to get laughed out of the room, I'd add this slightly different view that helped me understand Godel intuitively.
    - No theory can proove itself true without external reference.
    This includes our very own logical reasoning system, it can be used, but it cannot be used to proove it itself to be valid.

    How do you know theory is true? You need external referee that decides whether its true or false. How does that external referee know that its correct? For that you'd need yet another external referee, ad infinitum. If there is no external referee, you can't possibly know whether your theory is true or false.

    Any theory can be traced back to fundamental assumption that cannot be proved, its incomplete.
    The only way to 'proove' itself is via circular reasoning, which is inconsistent.
    So, there are only 2 possibilities: either incomplete, or inconsistent.

    Hopefully it wasn't way off topic.
  10. May 12, 2003 #9


    User Avatar
    Science Advisor

    Greetings !

    heusdens, from your response and suggestions
    I see I've reached the limmits of your credible
    explanation ability on this subject.
    I'd like to thank you very much for your
    input which got this thread "going"
    and for your suggestions and hope to
    see you posting more here ! :smile:
    (Maybe I'll follow them, but my laziness
    and more practical reasons, which are still
    mostly the result of laziness , compell
    me to attempt to seek an expert explanation
    here first, where it's potentially a lot
    easier to find it and there's interaction.)
    Nope, that was very good and I fully
    agree with it. Further more, I think it
    was important to mention the above
    precisely due to the reason that this
    may be a confusing point in terms of
    its relevance to this discussion.

    Basicly, I understand that Godel proves
    his point WITHIN math. Now, if I were to
    explain the existence of my abstract system
    I created then like wimms mentioned above -
    that would be impossible and I'd need an
    external system (me in this case).

    As I understand it so far - Godel's Theorem
    is WITHIN math and it is NOT an attempt to
    justify that system's premises. It is just
    mathematical operations that lead to the
    inconsistency. That is why I do not understand
    how it is possible. If you consider some effects
    of an external system - like internal axiom
    justification attempts then you can't say
    the system is internally inconsistent, can you ?
    I mean, if I were just to USE the system's
    axioms (add, multiply, devide and much more)
    why should I arrive at any inconsistency ever ?
    Perhaps I would, but then it seems more
    reasonable to check the realtions between all
    my axioms first before assuming some Universal
    rule that says that any system (2 or more axioms)
    is INTERNALLY inconsistent. btw, is the above
    rule precisely the one that Godel's Theorem
    proves ? Or is it more subjective - just math ?

    In addition, the strangest thought occured
    to me - can we at all explain Godel's result ?
    Does it have equivalent verbal explanations ?

    P.S. Again, if to the experts my stupidity at
    this point appears to be infinite then I truely
    ask you to forgive my ignorance and remember that
    in such case my remarks should at least seem
    humorous to you - and humour is very healthy. :smile:

    Live long and prosper.
  11. May 13, 2003 #10


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Incompleteness theorems are hands down the most subtle mathematical proofs I have ever encountered, so none of you should feel the least bit foolish for not completely understanding it!

    I'm not entirely familiar with Godel's theorems; the proof I studied was based on computation theory, though the result and the idea are similar.

    Anyways, this is where you're getting confused. "Proof by contradiction" is an integral part of mathematics (unless you're a constructivist).

    Formally, the relevant deduction looks like this:

    P => Q
    P => ~Q

    In words, this says:

    If P implies Q is true and P implies Q is false, then P is false; basically, if the truth of P implies a contradiction, then P must not be true (and thus must be false).

    Looking at it backwards might help. We know that Q is either true or false.

    If Q is true, then the only way "P => ~Q" can be true is if P is false.
    If Q is false, then the only way "P => Q" can be true is if P is false.

    Therefore P must be false.

    The usual structure of a proof using this deduction goes as:

    Assume P is true.

    ... some work ...

    Therefore Q is true.

    ... some work ...

    Therefore Q is not true.

    This is a contradiction, therefore our assumption was wrong, so P must be false.

    Part of Godel's proof uses this structure. If you assume G is provable, then it's trivial to prove G is provable. However, by the construction of G, you can also prove G is not provable. Therefore the assumption must be incorrect, and G is not provable.

    You are right, it relates very strongly to the liar's paradox, in that both rely heavily on self-reference as part of the proof.

    The formal version of the liar's paradox goes like:

    Define P(x) := ~x(x)
    Define Q := P(P)
    Assume Q is true, then P(P), therefore ~P(P).
    Thus Q is false.
    Therefore ~P(P), therefore P(P), therefore Q is true.

    And this is an honest to goodness contradiction.

    The resolution was to rewrite formal logic so that propositions are not allowed to operate on propositions. In particular, when we define P(x), x cannot be a proposition, so we cannot write x(x).

    The trick to Godel's proof is that he finds an indirect way to write propositions about propositions, by encoding propositions into numbers, with which propositions are allowed to operate. Fortunately, one cannot encode "true" and "false" into TNT, otherwise we'd have the Liar's paradox all over again.


    You're incorrectly applying what "TNT number" means.

    Something is a "TNT number" if and only if it can be deduced from the axioms.

    Assume G is a TNT number, then G is deducible from the axioms, and thus G must be true. However, that implies G is not a TNT number, which is a contradiction, therefore our assumption is incorrect and G must not be a TNT number.

    Now, if G is not a TNT number, G is true, but G is not deducible from the axioms. That is not the same thing as saying G is false!.

    In fact, if you assume "P is not deducible from the axioms" to be equivalent to "P is false", you derive a contradiction (as you eloquently put as saying G is equivalent to 1=2). However, that is still an assumption, and because it leads to a contradiction we've proven it false.

    Godel's theorem says that for any sufficiently powerful (consistent) theory, there exists a true statement that is not provable.

    That's an independant question, and my thoughts on this subject would be beyond the scope of this thread. (I've always wanted to say that! )

    The definition of a "complete" theory is that all true statements are provable. Because G is a true statement in TNT, but isn't provable from the axioms, TNT must be incomplete.

    Incorrect. If a theory is not powerful enough to encode the pseudostatement "This statement is not provable", then Godel's proof cannot work.

    For a concrete example, Euclidean geometry is a complete theory. Euclidean geometry even satisfies a stronger requirement; within Euclidean geometry not only are all true statements provable, but all statements are either true or false. I can't remember the technical term for this (other than decidibility, but that's not the one of which I'm trying to think), can anyone help me out with that?

    In traditional formal logic, "Inconsistent" simply means that there exists a statement P such that P is provable and ~P is provable. It's certainly possible to choose a set of axioms where this is possible. E.G.

    (1) All the axioms of arithmetic
    (2) 1 = 2

    The axioms of arithmetic allow us to prove (1 = 2) is false, while the next axiom allows us to prove (1 = 2) is true, thus this system is internally inconsistent.

    Do you mean something like

    "There exists a true statement that can't be proven"

    or something else?
  12. May 13, 2003 #11


    User Avatar
    Science Advisor

    Thanks Hurkyl ! :smile:

    But wait ! So, you're saying that Godel's
    theorem is only applicable to some advanced
    fields of relativly modern mathematics ?
    Could it also be the result of these fields
    being incomplete ?
    I see why what I said about 1=2 is inapplicable
    here. Indeed it is often used in proof by contradiction.

    I'm sorry but I did not follow you from the
    "however" sentence, what'd'ya mean by "that implies" ?

    Thanks again !

    Live long and prosper.
  13. May 13, 2003 #12


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Going by the proof in my computability theory text, a theory only has to be powerful enough to make propositions about the natural numbers involving addition and multiplication.

    Examples of theories not powerful enough are Euclidean geometry, and the natural numbers with addition alone.

    Because G effectively says "I'm not deducible from the axioms", if G is true then it's not deducible from the axioms.
  14. May 13, 2003 #13


    User Avatar
    Science Advisor

    Well, can't you just check G ?
    I mean, if it's right then the TNT
    is wrong. Also, if the TNT required
    that G be deduced then G without deduction
    is not a valid input thingy, is it ?
    (I still don't get it... )

    Thanks either way ! :smile:

    Live long and prosper.
  15. May 13, 2003 #14


    User Avatar
    Staff Emeritus
    Gold Member

    I think you are getting confused because you haven't disentangled a couple of concepts.

    When you have an axiomatic system (i.e., basic statements plus some rules to get new statements), there are two features of it that are of interest:

    1. Its consistency, and
    2. Its completeness.

    The first one means that you cannot obtain contradictory statements by correctly following the rules.

    Regarding the second, a system is said to be complete if all truths that can be represented on it can be obtained using its axioms and rules.

    Let me put it this way.

    Imagine a chess board. The initial positions of the pieces are the "axioms", and the rules of the game are the "logic rules".

    From there, you can reach ("proof") many positions (i.e., you can obtain them by allowed moves from the initial positions in the board), but there are also many positions you can imagine with the pieces that cannot be achieved using the rules (a simple example is having all bishops in white squares).

    These positions are the equivalent of the proposition G. The system can represent the proposition, but it cannot be proven using the system's rules.

    Going back to your questions:
    It may be possible to check G, but that is not the issue. The point is that G, though correct, cannot be proven using the system's "rules"

    You have the right idea here, just instead of "wrong", you want to say "incomplete".

    TNT does not "require" G to be deduced. TNT allows many deductions, and G is one of the true propositions that can be written in TNT, but that cannot be proven by it.

    I hope that helps.
  16. May 17, 2003 #15


    User Avatar
    Science Advisor

    Greetings !

    Thanks ahrkron !

    I think I'm starting to get this now.
    Your chess example with the bishops
    really helped a lot ! So now I see
    why I can not obtain a truth value
    for such a statement too - and hence
    the inconsistency ! :smile:

    I have a follow-up question then:
    Are there generally understood and
    defined rules to indicate when a system
    is or is not sufficiently complex ?
    I mean, rules that do not only apply
    to mathematical theories but to any
    axiomatic system ?

    Thanks !

    Live long and prosper.
  17. May 19, 2003 #16


    User Avatar
    Science Advisor

    Oops... Sorry about that, in retrospective I saw
    that ahrkron already posted this just above
    the example which cleared it up for me. It's
    just that I didn't get it before that.
    Thanks again ! :smile:
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?