Goedels Incompleteness Theorem

[Curious6]

I just read an article about Goedel's Incompleteness Theorem, and if I have correctly understood it, it basically means all theorems that we have and that can ever be made are either incomplete or inconsistent. This is also sometimes given as a reason to state that a TOE is impossible because it would be incomplete and/or inconsistent. However, my question is: are all theories really incomplete then, will we never know anything for sure or fully? Will an eventual quantum theory of gravity also be considered incomplete. It is quite a disturbing thought actually, and I would just like to know something more about this.

 

[HallsofIvy]

Goedel's incompletness theorem is a statement about the fundamentals of mathematics, it is NOT a theorem about physics. it is at least theoretically possible to have a physics theorem that does not correspond to ANY mathematical model. That would be a problem with the mathematics, not the physics.

By the way, most "working" mathematicians believe that the axiomatic theory of natural numbers is consistent, but not complete. "Not consistent" would mean that no theorem means anything, while "Not complete" means that it is not possible to prove EVERYTHING but that the proofs you have are valid.

 

[Curious6]

OK, thanks for the reply HallsofIvy. If I've understood what you've said, the Incompleteness Theorem does not mean that the proofs we have are invalid, just that it is impossible to achieve a total proof for a theory. However, you mention that it is 'theoretically possible to have a physics theorem that does not correspond to any mathematical model', but as far as I'm aware, most, if not all physics theories correspond or are built on mathematical models. Does this mean they are then inherently inconsistent or incomplete, or maybe both?

 

[salamander]

Don't know anything about Goedels theorem. However I can't help getting the feeling that you are impling this: if Goedels theorem is right, it would mean the theorem had to be either inaccurate or inconsistent or else it would be the only complete theorem, and thus violating itself... how does that make sense, really?

Cheers... ;)

 

[pervect]

Don't know anything about Goedels theorem. However I can't help getting the feeling that you are impling this: if Goedels theorem is right, it would mean the theorem had to be either inaccurate or inconsistent or else it would be the only complete theorem, and thus violating itself... how does that make sense, really?
Cheers... ;)

Actually, I don't think this problem occurs. I'm not a mathemetician, so I may have some of the language wrong, but basically Godel's proof used only constructivist methods, so you can't apply the theorem to Godel's proof.

 

[Integral]

Gödel's incompleteness makes NO statement about the truth or falseness of ANY single theorem. It does make a statement about sufficiently powerful formal SYSTEMS. In general it shows that any useful system will contain statements which cannot be proven, true or false. The common example is self referential:
"This statement is false"
I can formulate this statement but I cannot prove it true or false.

If you want a through lay mans development of Gödel's incompleteness read Gödel, Esher,Bach: An Eternal Golden Braid by Douglas R. Hofstadter. Warning! it is not a trivial read.

EDIT: Oh yeah, this is a math disscussion. Physics relies upon Math for its formal system therefore this is math.

 

[Hurkyl]

The real trick used by Godel is to create a statement that effectively says "I cannot be proven". If you can do so, this statement must be true and unprovable.

Actually, if you can create a statement that effectively says "I am false", then that will turn out to be an actual logical contradiction.

 

[TenaliRaman]

if one is inclined towards computer science, then he may like to think of halting problem ... since it has close resemblance with the way godel's incompleteness theorem was proved ... ofcourse the original proof was more mathematically driven than just picking sentences right from the air.

 

[pervect]

Gödel's incompleteness makes NO statement about the truth or falseness of ANY single theorem. It does make a statement about sufficiently powerful formal SYSTEMS. In general it shows that any useful system will contain statements which cannot be proven, true or false. The common example is self referential:
"This statement is false"
I can formulate this statement but I cannot prove it true or false.

If you want a through lay mans development of Gödel's incompleteness read Gödel, Esher,Bach: An Eternal Golden Braid by Douglas R. Hofstadter. Warning! it is not a trivial read.

EDIT: Oh yeah, this is a math disscussion. Physics relies upon Math for its formal system therefore this is math.

As I recall, (it's been awhile), the formal system that's needed to accept Godel's proof does not need to be a system that's powerful enough that one could apply Godel's theorem to it. Basically Godel carefully avoided "controversial" assumptions like the law of the excluded middle when formulating his proof.

 

[humanino]

Can we say : Godel's theorem justify the need for human-mathematicians ? A (Turing) machine would not be able to prove everything, and the human imagination fills in the missing new postulates the theory needs in order to grow.

This is the way I understand Godel's work, as an answer to Hilbert's old mechanical view of the mathematics.

 

[marlon]

Is this Godel theorem not the same as falsification ?

A theory is good until we find experiments that have outcomes which are not predicted by the theory. Newtonian mechanics is ok for low speeds but when looked at with light speeds it predicts false results. Just like with QM and Newtobian mechanics ?

This theorem teaches us that we must consider regions in which models of nature are valid, right ?

marlon

 

[humanino]

Not quite sure Marlon. We are physicists ! Godel deals with pure model, outside of the physical world. He was even worse than a regular mathematician : he was a logician :surprise: :yuck: :tongue2:

 

[marlon]

Not quite sure Marlon. We are physicists ! Godel deals with pure model, outside of the physical world. He was even worse than a regular mathematician : he was a logician :surprise: :yuck: :tongue2:

personally, i don't see much good in a theorem that states that no theory is ever complete and so on. It is like saying that fysics describes nature. It does not provide a new insight, it just states what everybody with an IQ over 70 allready knows. This is the same Godel that thought he found a solution to the Einsteinequations by using an absolute reference frame right? I never liked him, he was a very depressed individual, trust me...

marlon

 

[marlon]

The Only Thing Incomplete To The Theorem Of Godel Is The Theorem Itself !

 

[humanino]

(...) it just states what everybody with an IQ over 70 allready knows. This is the same Godel that thought he found a solution to the Einsteinequations by using an absolute reference frame right? I never liked him, he was a very depressed individual, trust me...

The Only Thing Incomplete To The Theorem Of Godel Is The Theorem Itself !

Marlon, you are hilarious :rofl: :rofl: :rofl:
Fortunately I'm not at work, everybody would have noticed me laughing.
And this is the same crazy Einstein friend.

 

[marlon]

Marlon, you are hilarious :rofl: :rofl: :rofl:
Fortunately I'm not at work, everybody would have noticed me laughing.
And this is the same crazy Einstein friend.

The only usefull theory on how physics works comes from Einstein : imagination is more important than knowledge.
And Popper learned us the principle of falsification, which gives a very good insight on how science is to be constructed, i think...


Godel is also useful : he shows us how it should NOT be done...


Keep on laughing, it is good for the bloodpressure.

Good night and "see" you tomorrow evening Humanino

nice talking to you

bonne nuit et à demain

marlon (le plus grand admirateur de Godel, celui qui a voulu battre Einstein mais qui a en vérité seulement battu lui-même...)

 

[humanino]

Marlon was earlier reffering to Godel's solution of Einstein equation, which exhibits a global rotation. Einstein before beleived it was impossible. This in turn helped understand the Mach principle.

Some Mathematicians claim Godel's theorem is useless because it is a technical proof (which makes it unusually short for such an important theorem/theory, only a few pages. But technical !) and it would kind of lie outside the rest of usefull mathematics. Indeed, Godel's proof is rather a philosophical lesson to us.

"95% of mathematicians don't care about what logician or philosophs might do"

(Dieudonné 1982)

quoting Solovay :
"The general feeling is that Godel's theorem concerns only logicians"

(Kolota 1985)

I found those in Delahaye's 1994 "Information, complexité et hasard"

The "Undecidables" of Godel are of two kinds : the first is basically "I am not demonstrable inside the system" (lier paradox). The second is more interesting, because it makes no call to self-reference. Undecidables of the second kind are equivalent to those of the first kind, but mean "the system is consistent". One can build a Turing machine which, given any consistent system, can build undecidables of the second (or first) form.

For those who are still interested, I keep on. The $$\omega$$ number, called Chaitin number, gives the probability that a Turing machine terminates when it is given a random program. $$\omega\in[0,1]$$. A formal system S can furnish only a finit number of digits for $$\omega$$. The number of digits is bounded from above by an independent constant plus the complexity of the formal system. Any proposition in S giving $$\omega$$'s digits is an Undecidable of Godel. The knowledge of $$\omega$$ would allow one to solve most of the famous mathematical conjectures, such as : Is Fermat's great theorem demonstrable in Peano's arithmetic ?

I find it fascinating. But one must be aware, that extracting such proofs from $$\omega$$ might require a lot of computation time

 

[master_coda]

The "Undecidables" of Godel are of two kinds : the first is basically "I am not demonstrable inside the system" (lier paradox). The second is more interesting, because it makes no call to self-reference. Undecidables of the second kind are equivalent to those of the first kind, but mean "the system is consistent". One can build a Turing machine which, given any consistent system, can build undecidables of the second (or first) form.

Of course, this only applies to systems that are powerful enough to formulate such statements.

 

[matt grime]

I think, Marlon, you need to learn a distinction between a mathematical theory and a physical one.

There are "proper mathematical" statements that are undecidable in ZF(C):
Continumm Hypothesis, which we'll state as there exists a set S and injections N to S to R (N naturals, R reals) and such that S has no bijections to N or R.

Conway also formulated a whole family of Collatz type conjectures which are undecidable.

 

[marlon]

I think, Marlon, you need to learn a distinction between a mathematical theory and a physical one.

There are "proper mathematical" statements that are undecidable in ZF(C):
Continumm Hypothesis, which we'll state as there exists a set S and injections N to S to R (N naturals, R reals) and such that S has no bijections to N or R.

Conway also formulated a whole family of Collatz type conjectures which are undecidable.

Pfff, to be honest i am not convinced. These mathematical facts you are reciting will undefinately be true. Yet Godel his "work" gives a redundant view on how science in general must work. That is all i am saying. Talking about injections and stuff will not change this view.

regards
marlon

 

[master_coda]

Pfff, to be honest i am not convinced. These mathematical facts you are reciting will undefinately be true. Yet Godel his "work" gives a redundant view on how science in general must work. That is all i am saying. Talking about injections and stuff will not change this view.

Godel's theorem wasn't talking about how science works. His theorem was about formal systems. And anyone who thinks the theorem is obvious clearly doesn't even know what the theorem actually is.

 

[Galileo]

And Popper learned us the principle of falsification, which gives a very good insight on how science is to be constructed, i think...

Yeah, Popper said a theory has to be falsifiable or it isn't scientific...

His own theory of falsifiability isn't falsifiable.

 

[matt grime]

Pfff, to be honest i am not convinced. These mathematical facts you are reciting will undefinately be true. Yet Godel his "work" gives a redundant view on how science in general must work. That is all i am saying. Talking about injections and stuff will not change this view.

regards
marlon

Would you post what you think Goedel's theorem states? Because you obviously are thinking of a different one from the one the rest of us know...

 

[Eye_in_the_Sky]

Three questions for marlon

1) Do you feel that natural numbers {0,1,2,3, ...} are fairly straightforward objects?

2) Do feel that they are simple enough that, at least "in principle", they are definable by a finite set of axioms?

3) Do you care?

... Please answer "yes" or "no" to each question.

 

[humanino]

Hey guys, go easy on Marlon !
His opinion is that Godel's theorem is obvious. I feel that all mathematical theorems are obvious once you understand them.

A formal system is either consistent or complete not both. Since one only cares about consistent systems, one if doomed to work with uncomplete systems. That is all. It is a technical road to get there. But once you're up there, it does not look very impressive.

 

[matt grime]

Why is it obvious that a formal system (containing the natural numbers) must be consistent, or complete (why can't it be neither?) and that it is not possible to be both? What heuristic argument do you have for it? The theorem may be obvious once you understand it, however Marlon clearly doesn't even know the statement of the theorem so he cannot be in a position ot understand it. His views appear to based on the idea that you cannot experimentally prove a theory, only disprove it or validate it. That has nothing to do with Goedel.

 

[master_coda]

A formal system is either consistent or complete not both. Since one only cares about consistent systems, one if doomed to work with uncomplete systems. That is all. It is a technical road to get there. But once you're up there, it does not look very impressive.

Of course, there are non-trivial systems which are consistent and complete. So perhaps you don't understand the theorem either, since you seem to think it says something that it does not.

 

[humanino]

Of course, there are non-trivial systems which are consistent and complete. So perhaps you don't understand the theorem either, since you seem to think it says something that it does not.

So I correct myself : any system able to define natural numbers bla bla bla
Please master_coda, what kind of consistent and complete system has been seriously investigated ? (this is a real question, I'd like to learn.)

 

[master_coda]

So I correct myself : any system able to define natural numbers bla bla bla
Please master_coda, what kind of consistent and complete system has been seriously investigated ? (this is a real question, I'd like to learn.)

Euclidean geometry.

 

[humanino]

Why is it obvious that a formal system (containing the natural numbers) must be consistent, or complete (why can't it be neither?) ...

If a formal system is not consistent, then it is complete.
[A & no(A)] implies B (whatever B)

... and that it is not possible to be both?

This is precisely Godel's theorem. I say "any demonstration is obvious once you know how to demonstrate it". I claim that mathematics are obvious. The reason for that, the reason why mathematics are so easy compared to physics, is that in mathematics, one knows what one is talking about. There are definitions. In physics, we can only applies clever ideas to model reality.

I actually went through Godel's demonstration. Several times. It's technical, but one can understand every single step.

Now one can understand Godel's argument without understanding the technical demonstration. Actually, I would probably never have undestood the technical part of it, without the first section of the article, where he explains the "lier paradox" thing. Even though, of course, I had already heard it somewhere else, would it just be in the beginning of my book where Godel's article is reprinted.

In my previous post where I quote Delahaye's 1994 book, I think I clearly showed that many very respectable mathematicians dare saying they don't care about Godel's theorem. So I personnaly forgive Marlon for making fun of it. I thought he was joking, that's all. Besides, he and I are physicists. I talk for myself, but I am just here to learn, so I want people to correct me whenever I post something wrong.

 

[humanino]

Euclidean geometry.

Yes, Ok right. Hilbert himself worked on the fondation of it. That is what led him to his program of automatic-mathematic demonstrations somehow.

But apart from that ? This is only one single counter-example. Has anybody since we know Godel's theorem been developping a consistent and complete categorie of formal system ?

 

[humanino]

I found the "Presburger arithmetic"
http://en.wikipedia.org/wiki/Presburger_arithmetic
which is consistent and complete ! But "not as powerful as Peano arithmetic"

 

[master_coda]

Yes, Ok right. Hilbert himself worked on the fondation of it. That is what led him to his program of automatic-mathematic demonstrations somehow.

But apart from that ? This is only one single counter-example. Has anybody since we know Godel's theorem been developping a consistent and complete categorie of formal system ?

The theory of real-closed fields was proven to be complete and consistent well after Godel's theorem was published.


Of course, if you actually understood the theorem in any meaningful way then you would already know of examples of complete and consistent systems. However you seem to think that you understand math because you know how to regurgitate explanations that other people have produced.

I'm at a loss to understand why you think the study of physics is any less trivially obvious. After all, physics is nothing more than inventing mathematical theories and testing if they correspond to reality. You've already demonstrated that the math part is obvious, and tests can be understood just as easily - I just have to memorize all the steps of the test. In fact, this applies just as well to all fields of science.

I can certainly see the usefulness of your use of the word "understanding". It reduces every piece of knowledge that ever has been or ever will be discovered to being easy to understand, and obvious. It doesn't allow for any interesting distinctions, but at least it make it easier for me to dismiss areas of study that I have little knowledge of.

 

[marlon]

1) Do you feel that natural numbers {0,1,2,3, ...} are fairly straightforward objects?

2) Do feel that they are simple enough that, at least "in principle", they are definable by a finite set of axioms?

3) Do you care?

... Please answer "yes" or "no" to each question.

Hello my dear friends. I think you will be very happy to see i am back (?)
My answers :
1)YES
2)NO
3)YES

regards
marlon

 

[master_coda]

I found the "Presburger arithmetic"
http://en.wikipedia.org/wiki/Presburger_arithmetic
which is consistent and complete ! But "not as powerful as Peano arithmetic"

That's exactly the point. If it were as powerful as Peano arithmetic, then it would be incomplete. How interesting or useful a theory is has nothing to do with how powerful is, so I don't quite see why you think "less powerful" is a problem with a theory.