Does Gödel's Incompleteness Theorem Disprove a Theory of Everything?

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?

Originally posted by Jonathan
edit: Should this be in the Logic forum instead?

Yep!

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.

Originally posted by quartodeciman


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.

why should it "presume the full scope of number theory"?

OK, now for a longer response.

Originally posted by Jonathan
This may be a misconception, but it seems to me that the theorem disproves the possibility of a ToE.

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.

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.

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).

You may find it interesting to reflect upon the fact that euclidean geometry is both consistent and complete.

...ToE would have to take for granted the validity of numerical (metric) systems?

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". :)

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)?

Originally posted by Hurkyl
You may find it interesting to reflect upon the fact that euclidean geometry is both consistent and complete.

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).

Originally posted by quartodeciman
Mentat: You answered a questions looming in my mind: somebody is a "Gamma Wave". :)

LOL!

And here I was trying to make an important point.

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).

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

Even more surprising Tarski has shown that geometry and the elementary algebra of real numbers, with addition and multiplication, but without the general notion of natural number, is complete and decidable."

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?

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º)¹ 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:
¹(and all 90º + integer multiples of 180º)

Regards,

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?

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.

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?

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.

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?

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
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}

...a system is incomplete if there exists a well-formed statement that cannot be proven or disproven by the axioms of the system?

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

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?

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.

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
explanation of Goodstein's Theorem

http://www.u.arizona.edu/~miller/thesis/node10.html
proof of GT in transfinite ordinal theory

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.

"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.

I see what I was missing; I was considering "complete" to be a statement about a set of axioms, not about a structure.

Originally posted by Hurkyl
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).

My apologies. What he was actually showing was the incompleteness of Deductive Logic itself, using the basic principle of Euclidean Geometry to illustrate the point. Whether Euclidean Geometry is complete or incomplete wasn't addressed, but rather was used as a means to show the incompleteness of Deductive Logic.

I repeat that different usages of 'complete' and 'incomplete' abound. The next book or paper you find is apt to attach these terms strictly to issues of proof. I scoured my meager library of books on the subject, and most of them support this usage. Eliot Mendelson of "Introduction To Mathematical Logic" even talks about "absolute incompleteness" within the context of systems that contain the power of producing arithmetic.

Remember, if you use 'complete' and 'incomplete' this way, proof is a matter of BOTH axioms and rules.

I think it was Haskell Curry who wrote in his book ("Foundations of Mathematical Logic", which I don't have) that underlying mathematical philosophy influences how the subject is perceived. A platonist (like Gödel) is apt to believe in truths of mathematics being out there beyond the realm of demonstrations. A formalist (like Hilbert) is apt to see the totality of mathematics strictly in terms of what can be raised in demonstrations. Intuitionists-constructivists are even more strict about what can actually be proven. The terms 'complete' and 'incomplete' may be used differently according to the philosophy of the person.

Hurkyl wroteYou may find it interesting to reflect upon the fact that euclidean geometry is both consistent and complete.

.


Yes, I find that very interesting. Do you have a reference for that statement? Consistency I would accept but I thought that it could be shown that the completeness of Euclidean geometry was equivalent (through Cartesian coordinate geometry) to the completeness of algebra which was itself equivalent to the completeness of the natural numbers which is what Goedel proved must be either inconsistent or incomplete.

the completeness of algebra which was itself equivalent to the completeness of the natural numbers

Are you sure on that?


While the real numbers contain the natural numbers, I don't think it's possible to construct a logical predicate that says "x is a natural number" using just the language of the arithmetic of the real numbers. (all of my ideas on doing this require some set theory)


Anyways, I can't find the text where I recall reading this for the first time, but some internet searching yields http://www.math.hawaii.edu/~dale/godel/godel.html#TarskiUndefinability, http://www.math.psu.edu/simpson/papers/philmath/node15.html and http://www.mmsysgrp.com/QuantumGravity/lucasmath.htm .