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 Incompleteness Theorem

  1. Sep 18, 2003 #1
    This may be a misconception, but it seems to me that the theorem disproves the possibility of a ToE. If I'm not mistaken, then it seems odd that physicists continue to look.

    edit: Should this be in the Logic forum instead?
     
    Last edited: Sep 18, 2003
  2. jcsd
  3. Sep 18, 2003 #2

    Tom Mattson

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Yep!
     
  4. Sep 18, 2003 #3
    Theory of Everything is just an attention-getting title for any theory that purports to render strong, weak, electromagnetic and gravitational interactions from a single scenario. I take Murray Gell-Mann's advice on this one- forget that name! There isn't really a (permanent) "everything" out there.

    I expect any such unification theory to presume the full scope of number theory before it even gets started. So there are effectively-undecidable true propositions already in number theory without even dealing with matters of physics.
     
  5. Sep 18, 2003 #4

    MathematicalPhysicist

    User Avatar
    Gold Member

    why should it "presume the full scope of number theory"?
     
  6. Sep 18, 2003 #5

    Tom Mattson

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    OK, now for a longer response.

    It does not disprove the possibility of "ToE" as physicists use the term, because the "E" does not refer to "Everything including the theory itself (as a formal system)". The "E" refers to "Every known physical interaction". Basically, Goedel's theorem says that any formal system is either inconsistent or incomplete.

    Inconsistent means that, for some statement X that can be derived from the theory, it is also possible to derive ~X from the theory. Incomplete means that there are statements in the formal system that cannot be proved from within the formal system itself.

    That said, string theory (as well as most other physical theories) are consistent, but incomplete. However, that is an openly acknowledged feature of all quantitative physical theories. And that's OK, because the theories of physics do not rely on their own axioms for confirmation, they rely on experimental evidence for it.
     
  7. Sep 18, 2003 #6
    I might have said that better: "the logic capable of producing the full scope of number theory".

    Even a geometric theory needs a foundation that includes some kind of complete metric function. Maybe one of those Lego-inspired theories manages to escape that prerequisite. I just don't know. Maybe you can tell me.
     
  8. Sep 18, 2003 #7
    quartodeciman, are you saying that any ToE would have to take for granted the validity of numerical (metric) systems? Surely you realize that that is true of all Scientific endeavors. Science is not the only way we gain knowledge, and is thus subject to its own set of constraints (one of which is that it relies on Inductive Logic, and another of which is that it relies on the validity of numbers).
     
  9. Sep 18, 2003 #8

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You may find it interesting to reflect upon the fact that euclidean geometry is both consistent and complete.
     
  10. Sep 18, 2003 #9
    Not just take for granted, but essentially depend upon them to produce results that cover that "everything" implied in calling it unification. Of course, it would be a good retort to me to say that a physical theory might not have to recapitulate this logic to apply to its proper domain. In that case, the theory by itself would not necessarily be subject to Gödelian limitations. But it is hard to conceive doing without a law of large numbers and other stuff like that. How far must a theory go to be considered satisfactory?

    Mentat: You answered a questions looming in my mind: somebody is a "Gamma Wave". :)
     
  11. Sep 18, 2003 #10
    It seems to me that if you can simulate any physical system by replacing the parts with numbers and letting them interact, every once in a while there'd be a system whose outcome would be reperesented by sqrt(-1) or something. I have a hard time discussing this, it's a bit absract.
    How can euclidean geometry be consistent and complete? What about the classical figure of trig relationships, the one with a circle, triangle, and a bunch of lines, because if you draw a triangle in this figure with two 90 degree angles, the third is zero and infinitly far away, making tan(90) not real (divide by zero)?
     
  12. Sep 19, 2003 #11
    That cannot be true, can it? IIRC, that is exactly the illustration that Hofstadter used in Godel, Escher, Bach: An Eternal Golden Braid. In it the incompleteness of deductive logic was shown using Euclidean geometry (specifically, Euclid's law that any two sides of a triangle who are equal to the same are equal to each other).
     
  13. Sep 19, 2003 #12
    LOL!

    And here I was trying to make an important point.
     
  14. Sep 19, 2003 #13

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Either you are remembering incorrectly or he is talking about a different kind of incompleteness (unrelated to the meaning of incompleteness in Godel's theorem).


    Incidentally, I just came across this even more interesting statement at http://www.mmsysgrp.com/QuantumGravity/lucasmath.htm

     
  15. Sep 19, 2003 #14
    How can that be? What about finding the tan(90)? Sure, for all intents and purposes it is infinity, but in actuallity it is divide by zero. If tan(90) is decidable, then (anynumber)/0=infinity, which means infinity*0=(anynumber)! We know that any number times zero is zero, so how can infinity be any different?! Doesn't this prove that geometry is complete and inconsistent?
     
  16. Sep 19, 2003 #15
    Jonathan,

    'geometry is complete' means that, metamathematically, every statement well-formed within the system is either true within the system itself or else its negation is true within the system. An example of an 'incomplete' system is geometry without any axiom about parallel lines at all. This is incomplete, because it can be modified by adding an independent euclidean parallel axiom to its given set of axioms, and it can be alternatively modified by adding some independent non-euclidean parallel axiom (e.g. lobatchevskian) to its given set of axioms, each case producing a new refined consistent system. If that parallel-neutral geometry had been complete, a contradiction could have been raised in one of these two refinements. That didn't happen, so the parallel-neutral geometry must be incomplete.

    The answer to your objection about the tangent of 90º (and all 90º + multiples of 360º)1 is that these numbers are just not in the domain of the normal tangent function. That is an entirely different matter from the issue of whether any well-formed statements within the system of geometry might be neither true nor false.

    Also, my earlier use of the term 'complete' in the phrase 'complete metric' is something entirely different. It's about existence of limit points to Cauchy sequences of points coming from a metric space ('metric' means a properly-specified 'distance' function for pairs of points). Unfortunately, mathematicians get lazy and start reusing their invented vocabularies, to the confusion of many (me included). :)

    {EDIT} an improvement:
    1(and all 90º + integer multiples of 180º)

    Regards,
     
    Last edited: Sep 19, 2003
  17. Sep 19, 2003 #16
    Hi guys,
    Hope you don't mind if I butt in. I have just recently heard about this theorem in my math class, and when I first heard of it, it amazed me. I don't quite understand how a system can be incomplete. Say I give a set of axioms, itn't it true that these axioms alone define my system? You can't say that my system is incomplete just because you can think of another axiom to add to my list such that it does not conflict with the one I already have.

    For instance, let me propose the following math system:
    E={all natural numbers}
    A={1>0}
    O= {a*b=1 for all a,b in E}
    A is the set of axioms, O the set of operations. Now, from this system you can prove just a couple theorems. For example, you can prove 1*0>0. But you may say my system is incomplete, because you can add the axioms "if a>b and b>c then a>c" and "2>1" without contradicting any of my already proven theorems. Now you can prove 2>0, but you can't contradict any other theorem or axiom from before (I think - I haven't put too much thought into this - for the sake of argument, suppose I'm right). But the point is, if I don't include certain things in my list of axioms, that simply means that they aren't a part of my system - they are neither true nor false in my system. They don't exist and don't belong. I hope you understand my blabbering.
    So, what's the deal?

    ....
    Also, if ANY system is incomplete or inconsistent, then how do we know that any particular theorem we work with in any system is not both true and false in that system? How do we that differential calculus for example isn't based on at least one inconsistent theorem or axiom?
     
  18. Sep 19, 2003 #17

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You're forgetting one important thing of a theory... its language. The language of your theory includes things like the symbol '>' and natural number constants like '2' and '0'... so the proposition '2>0' is a well-formed statement in the language of your theory, and since neither this statement nor its negation can be proven in your theory, your theory is thus incomplete.
     
  19. Sep 20, 2003 #18
    So, just to make sure I understand, a system is incomplete if there exists a well-formed statement that cannot be proven or disproven by the axioms of the system?
    Say I modified E to be E={0,1}. It is easy to list all statements of the language when there are so few elements. You can have,
    1>0
    1*1=1
    1*0=0
    0*1=1
    a*b>0 in general
    a*b>1 in general
    0>0
    1>1
    Of these statements, at least 0>0 and 1>1 cannot be proven or disproven. So the system is incomplete, right?
    I suppose you could get really particular and make a system with only one well-formed statement, which also happens to be an axiom. Would that trivial system be subject to Godel's Theorem?
     
  20. Sep 20, 2003 #19

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Because you can find a statement like '0>0' that can be neither proven nor disproven, the system is, indeed, incomplete.

    Incidentally, that is not all of the statements of the language; don't forget the logical connectives like 'and' and 'or', and formulas you can make out of variables and quantifiers.
     
  21. Sep 20, 2003 #20
    We don't, except inasmuch as someone has produced a viable meta-argument for consistency. Even that is NOT complete assurance. Formal demonstrations of consistency are normally always demonstrations of relative consistency (B is consistent if prior system A is presumed consistent). In the end, consistency is a logical question and we must assume that our prevalent system of logic in use only produces consistent results. Usually that logic is taken to be predicate calculus and axiomatized set theory. At the bottom, we end up having to trust something.

    The following is a pretty good position paper. I used to know who made this website, but it was a long time ago and I have forgotten. The short paragraph in the paper about General Relativity theory is not germane to the subject of logical consistency. Singularities forecast by GR are not themselves in the domain of GR, though they can be supposed from outside, in spacetime regions that are not singular. That is not essentially different from the case of Newtonian Gravitation with point-sized gravitational mass-charges. The effects outside can be dealt with; the point-masses themselves can't be dealt with in NG. That rolls back to my earlier comment about the limited domain of the tangent function. --->

    http://www.mathpages.com/home/kmath372.htm [Broken]
    Certainty in Mathematics and Physics

    If you like to read stuff --->

    http://plato.stanford.edu/entries/set-theory/#9
    too much ado about Set Theory {SEoP}

    No. That is decidability/undecidability and is the real subject of the first Gödel theorem. This says that there exists a true statement (true in the system) but no demonstration of it or its negation exists.

    more bedtime reading -->

    http://www.wikipedia.org/wiki/G%F6del's_incompleteness_theorem
    Wikipedia: Gödel's Incompleteness Theorem
     
    Last edited by a moderator: May 1, 2017
  22. Sep 20, 2003 #21
    quart, it seems that you and Hurkyl disagree.
    Here's what I don't get:
    How can we say something is a mathematical truth if we don't prove it? What do you mean by "true in the system"? If you can demonstrate its negation, certainly it's not true in the system!?
    I mean, just because we know intuitively that a+b=b+a doesn't make a mathematical truth, does it?
     
  23. Sep 20, 2003 #22

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    If quartodeciman is sure, go with what he says. Unfortunately, I don't have a solid reference on this stuff lying around that I can use to double-check myself.
     
  24. Sep 20, 2003 #23
    I may have to back down a little. The web is not being kind to my searches for a set of simple, sweet definitions.

    Gödel's famous paper was entitled "On Formally Undecidable Propositions of Principia Mathematica and Related Systems". In it he established the existence of a metamathematical statement that asserts that some statement in formal arithmetic cannot be proven. So that metamathematical statement is true in the metalogic that describes arithmetic statements. But in the process of building his demonstration he established an exact one-to-one mapping for converting metamathematical statements like this one into actual statements within formal arithmetic (about numbers and arithmetic expressions). This mapping (call it Gödel imaging) guarantees that true metamathematical statements always map to true arithmetic statements. So if Gödel's proven metamathematical statement is true, then the image in arithmetic for that metamathematical statement is a true statement of arithmetic. Guess what the image of Gödel's result is: the very arithmetic statement Gödel's result was talking about, that cannot be proven. So that arithmetic statement (some unimaginably horrible complex arithmetic relationship) is true but not provable (in fact, it is true BECAUSE it is not provable). If arithmetic is a consistent system, then the negation of the image must be false. Arithmetic is not necessarily a Gödel incomplete system because of this, but it is a Gödel undecidable one. WHEW! Sorry for all that!

    Now to back down. David Hilbert thought that every problem was ultimately solvable, so he defined "complete" to mean that every statement or its negation can be proven in the system. Call that "Hilbert completeness". There are plenty of repetitions around for that definition. Also, there are other definitions for "decidable". Some come from Alan Turing's work and the subject of computability. A system is decidable (in this definition) if there exists an algorithm for testing statements within the system and this algorithm is guaranteed to terminate eventually with a YES or NO answer as to the truth of the statement. Maybe "provable" might be a better term for me to use than "decidable". That would take us into logical proof theory. OY VEH!

    As a matter of fact, the arithmetic of simple integers is demonstrably an unprovable system, without needing a metamathematical proof. The case in point is a cute little item called Goodstein's theorem. A chosen positive integer is expanded into a polynomial of base 2 and all the exponents are expanded into expressions of 1 and 2. A new number is produced by raising all 2s to 3s and subtracting 1 from the resulting polynomial. Then the resulting value is expanded into a polynomial of base 3. This process is iterated again and again, expressing everything in a new base number, substituting each occurrence of the base number by the next higher integer and subtracting by 1 again. Goodstein's theorem concludes that the sequence of polynomials and numbers must eventually reduce to 0. Somebody proved that Goodstein's theorem cannot be proven in the usual simple arithmetic, but it can be proven in transfinite ordinal arithmetic, which has a more advanced logic (with transfinite set theory). Since it always holds for all normal ordinal numbers, then it is true in simple arithmetic, but can't be proven there.

    links:

    http://www.u.arizona.edu/~miller/thesis/node3.html [Broken]
    explanation of Goodstein's Theorem

    http://www.u.arizona.edu/~miller/thesis/node10.html [Broken]
    proof of GT in transfinite ordinal theory
     
    Last edited by a moderator: May 1, 2017
  25. Sep 20, 2003 #24

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    The thing that bugs me about the "true but unprovable" statement is this...


    Suppose we have a consistent system S, and a statement P with the property that neither P nor ~P is provable in S.

    The system (S + P) must be consistent; any contradiction derived in (S + P) would trivially yield a proof of ~P in S, violating the hypothesis.

    Similarly, the system (S + ~P) must also be consistent.


    Because of this, it doesn't seem to make sense to say that any statement of a system is "true but unprovable"; such a claim can only be made in the context of different system.
     
  26. Sep 21, 2003 #25
    "true but unprovable" ... bugs me

    Rightly so. "Unprovable" means unprovable in some particular system. A refinement of a system by adding more axioms and rules might make one of Gödel's pair p|~p provable. We expect to get new truths from a system through deductions. But we must specify what the system includes.


    first---

    I suppose a dumb, simple-minded example might start with a little finite set {a , b}, where a and b are specified to be distinct elements. A binary operation "*" might be specified for these elements: * == {<<a, a>, a>, <<b, b>, b>, <<a, b>, b>, <<b, a>, b>}.

    So the following statements are logical atomic TRUE statements in this system:

    a * a = a, b * b = b, a * b = b, b * a = b.

    The axioms might be specified as:

    a = a, b = b, a * a = a, b * b = b. (note: no mention of anything like "a * b" or "b * a" in these axioms)

    The deduction rules might allow substitutions of equalities and consequences of applied modus ponens.

    This happens to be (by specification) a semigroup under *, but not a group. {a} and {b}, with the appropriate parts of *, form separate subgroups.

    OK. a~=b, a * b = b and b * a = b are true in this system, but I don't think they can be proven using these axioms. It's not a provable system.

    But we already know the logical atomic truths of this system, so we can deduce basic logical molecular truths from these by enjoining them and their negations into complex expressions. It is as complete (in the sense of Gödel) as propositional logic and predicate logic allow it to be.

    Adjoin some more axioms (like a * b = b and b * a = b) and you might get a new system that is provable.

    done---


    Gödel admits that you can add the independent p (or else its negation ~p) as a new axiom to an arithmetic system and make a new system that is equally as consistent as the starting system. But now (since the new system still has the power to generate arithmetic) he will create a new imaging into the new system and recreate his result. Another true but unprovable statement is revealed.
     
    Last edited: Sep 21, 2003
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook