Does Gödel Matter?(slate.com)
slate.com
Does Gödel Matter?
http://www.slate.com/id/2114561/
52 comments
Isn't this broader than the limitations of first order logic? After Turing we know that no matter what formal system of axioms and rules of inference one choses(as long as these can be mechanically done) then there will be some true statements the system wont be able to see. (does the nth turing machine stop?, does a particular diophantine eqn have integer solutions?)
Can they be used indirectly, i.e. X is the case because of Y, where Y is a non-standard proof?
I've read the book the article ostensibly reviews, and to be honest it's not much cop. It's full of, frankly, a load of rubbish about post-modern thought and the extent to which Gödel's work might vindicate it. There are certainly interesting aspects to it, but it's neither a good biography nor a particularly good introduction to incompleteness, and is liable to merely frustrate anyone possessed of a passing acquaintance with either subject.
I rather enjoyed the book, but it is largely because I knew what I was getting into. It's a pop science book, written by a person with a philosophical background, and embellished in the Hollywood-esque fashion, pitting the good guy--Goedel, the misunderstood genius--against the bad guy--Wittgenstein and the logical positivists--in a no-holds-barred showdown of ideas that lie at the heart of all truth and mathematics!
Obviously, it's a stretch at times, and there a good deal of rigor lost, but it's a pretty juicy story. If I wanted a biography, I would read one specifically about Goedel, and not one about Incompleteness. If I wanted to learn about the theorems themselves, I would pick up a copy of his paper or one of the many readable expositions of his work. But I wanted a fun read that explained why so many philosophers and nonmathematicians were interested in this rather esoteric bit of mathematics, and I certainly got that from the book.
Nonetheless, if you want a better book by the author, I recommend The Mind-Body Problem over this one.
Obviously, it's a stretch at times, and there a good deal of rigor lost, but it's a pretty juicy story. If I wanted a biography, I would read one specifically about Goedel, and not one about Incompleteness. If I wanted to learn about the theorems themselves, I would pick up a copy of his paper or one of the many readable expositions of his work. But I wanted a fun read that explained why so many philosophers and nonmathematicians were interested in this rather esoteric bit of mathematics, and I certainly got that from the book.
Nonetheless, if you want a better book by the author, I recommend The Mind-Body Problem over this one.
I read the book, and it was sometimes boring, still there's a lot of positive things makes you continue with the book. I got to learn about the works of Godel, Escher and Bach. And then about the patterns which exist in nature, or any work, where we never thought it could be a pattern.
Anyways, I'm not a mathematician or a physicist to comment on Godel's work. I think the book is worth reading, whether it contributed to computer science or not, i do not know.
Didn't he put forward two theorems? One about the undecidable statements as described in the article, but the other was much "worse": the consistency of mathematics can not be proven. That is for any axiom system with a certain minimal strength (like strong enough to derive natural numbers) it can not be proven that the axioms don't contradict each other.
Hopefully I am citing it right, as I am too lazy to look it up. But I think that is more of a ticking bomb sitting in the guts of mathematics. It could happen that one of these days the whole building of mathematics collapses because a contradiction in the axioms emerges. Apparently the common way to deal with it is to just deem it very unlikely since things went fine for centuries, and there is not much that can be done about it anyway.
Must finally read Gödel's proofs again, have been meaning to do so for ages :-/
Hopefully I am citing it right, as I am too lazy to look it up. But I think that is more of a ticking bomb sitting in the guts of mathematics. It could happen that one of these days the whole building of mathematics collapses because a contradiction in the axioms emerges. Apparently the common way to deal with it is to just deem it very unlikely since things went fine for centuries, and there is not much that can be done about it anyway.
Must finally read Gödel's proofs again, have been meaning to do so for ages :-/
The second theorem says that the consistency of a system cannot be proved within that system (sufficiently strong, etc).
If a contradiction is discovered in set theory, either it will be fixed by a change to the axioms, or another set of foundational axioms altogether will become the standard foundation of mathematics. Perhaps the canonical example of this is naive set theory itself - paradoxes were discovered, but set theory was interesting enough that mathematicians looked for alternate definitions that did not contain the paradoxes, and they succeeded.
There are two things to note here. First, axiomatization was a useful tool in distinguishing various types of set theory and defining the ones that did not contain the (known) paradoxes. Second, the full formal treatment of these set theories came relatively late to mathematics, as did widespread use of formal, axiomatic methods in general. Rigorous axiomatic formalisms are very useful mathematical tools, but mathematics got along without them for a long time (not even Euclid counts, by modern standards) and can do so again if necessary. It is unlikely that this will happen, not because axiomatics can be proved to always work or because mathematics cannot get along without it, but because it is too useful a tool to abandon easily.
This was really Godel's point: mathematics is not identical with formalism. They stand and fall separately. This is not to say that mathematics could never collapse for any reason, only that it would take a lot more than finding a paradox at the center of ZFC to make it happen.
If a contradiction is discovered in set theory, either it will be fixed by a change to the axioms, or another set of foundational axioms altogether will become the standard foundation of mathematics. Perhaps the canonical example of this is naive set theory itself - paradoxes were discovered, but set theory was interesting enough that mathematicians looked for alternate definitions that did not contain the paradoxes, and they succeeded.
There are two things to note here. First, axiomatization was a useful tool in distinguishing various types of set theory and defining the ones that did not contain the (known) paradoxes. Second, the full formal treatment of these set theories came relatively late to mathematics, as did widespread use of formal, axiomatic methods in general. Rigorous axiomatic formalisms are very useful mathematical tools, but mathematics got along without them for a long time (not even Euclid counts, by modern standards) and can do so again if necessary. It is unlikely that this will happen, not because axiomatics can be proved to always work or because mathematics cannot get along without it, but because it is too useful a tool to abandon easily.
This was really Godel's point: mathematics is not identical with formalism. They stand and fall separately. This is not to say that mathematics could never collapse for any reason, only that it would take a lot more than finding a paradox at the center of ZFC to make it happen.
"This was really Godel's point: mathematics is not identical with formalism. They stand and fall separately. This is not to say that mathematics could never collapse for any reason, only that it would take a lot more than finding a paradox at the center of ZFC to make it happen."
That's significant because another great mathematician David Hilbert challenged mathematicians to come up with a complete and consistent set of axioms for all of mathematics. This was a great hope at one time that was shattered by Godel. Most people don't really talk about this old program anymore (except as a historical curiosity) because there is utterly no hope in it at all. The other implications that people try to draw from Godel's work is probably a consequence of the fact that his work sounds like it says so much more than it actually does when it's translated into normal English (and out of math-speak).
That's significant because another great mathematician David Hilbert challenged mathematicians to come up with a complete and consistent set of axioms for all of mathematics. This was a great hope at one time that was shattered by Godel. Most people don't really talk about this old program anymore (except as a historical curiosity) because there is utterly no hope in it at all. The other implications that people try to draw from Godel's work is probably a consequence of the fact that his work sounds like it says so much more than it actually does when it's translated into normal English (and out of math-speak).
Hm, I thought set theory already contains arithmetic, so wouldn't Goedel's proof show that such axioms without paradoxes can't be found? I thought that is why he is so famout - for years it had been the goal of mathematics to find the ultimate axioms, and then Goedel showed that it can't be done, ever.
The second theorem tells us that we can't prove the consistency of set theory without using an even more powerful system. This doesn't mean that set theory is inconsistent, it just means that we can't prove its consistency in any meaningful way. So yes, Gödel indeed shows that there are no 'ultimate axioms' that contain everything of interest in mathematics.
Although it does lead to a mathematically uninteresting paradox: if you let A be the axioms of set theory and you add an axiom P which states that A proves x and not x, (i.e. set theory is inconsistent) then A' = A and P is still consistent.
Consistency is overrated. General relativity and quantum mechanics are inconsistent with each other but at the same time they are extremely precise when applied to an appropriate domain (I remember watching a lecture where Feynman wrote down a number with 20 or so digits representing conformity of theory prediction with experiment).
To fill in some of the details: the so-called 'Second Incompleteness Theorem' states that recursively inumerable systems containing arithmetic are insufficient for proving their own consistency. It is possible to prove the consistency of arithmetic, but to do so you must use an even more complex system of axioms whose consistency can itself only be proved with an even more complex system, and so on.
So strictly speaking, the theorem doesn't rule out consistency proofs, but it does rule out proving the consistency of complex systems by simpler systems, meaning that the consistency of the consistency proofs can't be trusted any more than the consistency of the original system!
So strictly speaking, the theorem doesn't rule out consistency proofs, but it does rule out proving the consistency of complex systems by simpler systems, meaning that the consistency of the consistency proofs can't be trusted any more than the consistency of the original system!
Even though they're not axiomatizable, natural numbers rest on reality - a contradiction would let us make two apples from one.
Banach-Tarski paradox: http://en.wikipedia.org/wiki/Banach%E2%80%93Tarski_paradox.
Which rests on the grossly-unphysical "Axiom of Choice". That doesn't disprove cousin_it's point. Though it's still an interesting link, if that's why you're posting it.
Almost all people use mathematics where "Axiom of Choice" is set to be true. It is grossly-unusual to consider systems without that axiom.
If you are not a mathematician chances are you've never encountered a system based on axioms without "Axiom of Choice" (for systems where it is applicable at all).
If you are not a mathematician chances are you've never encountered a system based on axioms without "Axiom of Choice" (for systems where it is applicable at all).
I agree it's "grossly-unphysical", but you can do hardly any math without it. Now try to do physics (or computer science) without math.
[deleted]
A view which Gödel, an ardent Platonist, would have no doubt agreed with.
Do they, though? Is there infinity in reality?
Infinity is not a number.
Infinity is not a natural number (as is in Peano arithmetic) but in many cases it can be treated as an ordinary number e.g., for some problems on a complex plane.
You are in a good company thinking that infinity cannot be ever treated as a number http://scienceblogs.com/goodmath/2008/10/infinity_is_not_a_n...
You are in a good company thinking that infinity cannot be ever treated as a number http://scienceblogs.com/goodmath/2008/10/infinity_is_not_a_n...
It is. Just depends which field. Surreals, superreals, hyperreals... People have been taking the reals and adding infinity all the time.
Also, there are the cardinal numbers, for which the interesting ones consist entirely of infinity.
Also, there are the cardinal numbers, for which the interesting ones consist entirely of infinity.
I know, but there are more numbers than real things, or at least maybe they do. Perhaps numbers fail only in extremely large regions that we don't perceive in everyday life. (Unlikely I know, just nitpicking really).
Reality is a scary word.
Are there negative numbers? Zero? Imaginary unit?
There were times when people even didn't know a concept of zero.
A concept of infinity is really useful and it is used almost everywhere.
Are there negative numbers? Zero? Imaginary unit?
There were times when people even didn't know a concept of zero.
A concept of infinity is really useful and it is used almost everywhere.
I still don't think we have grasped the importance of Gödel's incompleteness theorem. For example, indirectly it means that we can't ever solve the halting problem. Personally, I also think it applies to physics, especially the idea to find a theory of everything. I think theory of everything won't be possible simply because the incompleteness theorem states that "given any system of axioms that produces no paradoxes, there exist statements about X which are true, but which cannot be proved using the given axioms." (where X can be numbers, computer programs or ...)
This is exactly the kind of thinking that the article argues against. Remember that Goedel is speaking within the context of formal systems, so there is relatively little impact to any area outside of the small field of philosophy of mathematics. Anybody who tries to extrapolate beyond those bounds is either mistaken or misled as to what Goedel's incompleteness theorems actually imply. There is a much more thorough and eloquent explanation in the following link. [http://www.ams.org/notices/200604/fea-franzen.pdf]
Hell, even Einstein, who was close friends with Goedel and familiar with the result, was searching for a more fundamental physical theory than quantum mechanics, so clearly he did not believe it was a lost cause.
Hell, even Einstein, who was close friends with Goedel and familiar with the result, was searching for a more fundamental physical theory than quantum mechanics, so clearly he did not believe it was a lost cause.
Do you know of anyone who has rigorously determined how Goedel's theorems apply to anything outside of mathematics?
While his theorems show the shortcomings of a certain approach to math, I don't think math is the only area where this approach is applied. For instance, granting Goedel has shown math is Platonic, i.e. it is about independently existing entities, not formal structures, then why does it make sense to say the mind that can grasp math is itself a formal system, i.e. the assumption behind strong AI?
So, it is more accurate to say Goedel's work is restricted to domains where formalization (of the correct sort) is applied, which covers more ground than just the philosophy of mathematics.
While his theorems show the shortcomings of a certain approach to math, I don't think math is the only area where this approach is applied. For instance, granting Goedel has shown math is Platonic, i.e. it is about independently existing entities, not formal structures, then why does it make sense to say the mind that can grasp math is itself a formal system, i.e. the assumption behind strong AI?
So, it is more accurate to say Goedel's work is restricted to domains where formalization (of the correct sort) is applied, which covers more ground than just the philosophy of mathematics.
What you say in your last statement is true and helps to clarify a subtle point. I tend to shove all of that stuff (logic, set theory, problems of undecidability, etc) into the nondescript box labeled "philosophy of mathematics." When I meant a field was "small," it was not meant to be pejorative. Philosophy of mathematics is a rich and productive field with many applications within its varied fields. The main problems I see are the ones described the article I linked, in that people attempt to apply the theorems to things like physics, politics, law, or postmodern philosophy.
Of course Goedel's theorems do not totally exist in a bubble that only contains arcane mathematical incantations. For instance, Goedel's theorems imply (like the halting problem) that you cannot create a compiler that would be able to determine whether a program will not terminate and reject it, by considering what happens when you feed it a Goedel statement. However, this problem is something that I would also classify under "philosophy of mathematics."
Also, I hope I did not provide any implication that my view (or any view, for that matter), is the final word on the subject. I'm not dead-set in my own beliefs on incompleteness and if you can provide a convincing argument of a rigorous, nonmathematical application of Goedels theorems, I'd be more than happy to change my mind.
There is considerable discussion as to what exactly the incompleteness theorems imply, and there are many eminent minds on the many different sides of the argument. For instance, I believe Stephen Hawking is somebody who believes that physics cannot ultimately be formulated into a final number of finite principles. Do I believe this to be a rigorous application of Goedel's incompleteness theorems? No. Do I believe that this can be applied to fields outside a relatively restricted problem space? No. Does this mean I'm right? Of course not.
As to your point about Strong AI, I don't want to open that can of worms in this thread. I'm not yet convinced that the human mind is equivalent to any finite state machine, so I'm afraid that we don't even agree upon its the basic premises. However, I would love to discuss it any time outside of the thread.
Of course Goedel's theorems do not totally exist in a bubble that only contains arcane mathematical incantations. For instance, Goedel's theorems imply (like the halting problem) that you cannot create a compiler that would be able to determine whether a program will not terminate and reject it, by considering what happens when you feed it a Goedel statement. However, this problem is something that I would also classify under "philosophy of mathematics."
Also, I hope I did not provide any implication that my view (or any view, for that matter), is the final word on the subject. I'm not dead-set in my own beliefs on incompleteness and if you can provide a convincing argument of a rigorous, nonmathematical application of Goedels theorems, I'd be more than happy to change my mind.
There is considerable discussion as to what exactly the incompleteness theorems imply, and there are many eminent minds on the many different sides of the argument. For instance, I believe Stephen Hawking is somebody who believes that physics cannot ultimately be formulated into a final number of finite principles. Do I believe this to be a rigorous application of Goedel's incompleteness theorems? No. Do I believe that this can be applied to fields outside a relatively restricted problem space? No. Does this mean I'm right? Of course not.
As to your point about Strong AI, I don't want to open that can of worms in this thread. I'm not yet convinced that the human mind is equivalent to any finite state machine, so I'm afraid that we don't even agree upon its the basic premises. However, I would love to discuss it any time outside of the thread.
I checked your profile and you don't have any contact information. I'm curious about what you think the mind is. Most seem to think it is an "emergent property" of the brain.
Finding better models and understanding things at a deeper level is never a lost cause and even if we know that we can't find a complete set of axioms for all existing math theories, we still try to understand math better. For example, the string theory people are trying to find an answer for everything (and it seems to be much more complex than 42 :-p). In this context, David Hilber tried to do the same for math (namely find a set of axioms for all existing theories) and Gödel proved that this was a lost cause. Does Gödel's incompleteness theorem apply to physics as well? I can't really grasp it, but my intuition says it does - because why would the formal system of TEO have more simple properties than the formal systems for arithmetic or Turing machines...?
There is a much more thorough and eloquent explanation in the following link. [http://www.ams.org/notices/200604/fea-franzen.pdf]
Thanks for the link.
Thanks for the link.
My instincts agree with you, but the rational part of my mind can't distinguish statements that are affected by Gödel's theorem from those that are not.
Chaitin agrees with you:
http://www-2.dc.uba.ar/profesores/becher/ns.html
Note, the article is for the lay reader, but the gist is a correct representation of Chaitin's views. For more rigor, see:
http://en.wikipedia.org/wiki/Chaitin%27s_constant
Chaitin wrote a freely available book about his views:
http://plus.maths.org/issue37/features/omega/feat.pdf
A bit more discussion here:
http://news.ycombinator.com/item?id=378658
http://www-2.dc.uba.ar/profesores/becher/ns.html
Note, the article is for the lay reader, but the gist is a correct representation of Chaitin's views. For more rigor, see:
http://en.wikipedia.org/wiki/Chaitin%27s_constant
Chaitin wrote a freely available book about his views:
http://plus.maths.org/issue37/features/omega/feat.pdf
A bit more discussion here:
http://news.ycombinator.com/item?id=378658
[deleted]
Does it really mean that a theory can't be found or just like with "everything else", we can only be 99.99999999% sure and never reach 100%?
Does it necessarily mean that the imcompleteness theorem extends to all systems?
The article linked somewhere else in this thread:
http://www.ams.org/notices/200604/fea-franzen.pdf
seems to say that it doesn't extend to other "systems".
I think physics would be very happy to come up with a theory of "almost everything", like set theory is for mathematics. That would be a huge step forward, and would be completely unaffected by Godel's theorem.
Also, the halting problem's insolvability is straightforward to see without knowing any of Godel's work. :)
Also, the halting problem's insolvability is straightforward to see without knowing any of Godel's work. :)
It is easy to exhibit an uncomputable function, the busy beaver function is the standard, easy example. It is immediately obvious that a solution to the halting problem make the busy beaver problem computable: just stick to running the programs that halt and pick the largest output. The unsolvability of the halting problem is way easier than Godel.
Well, it wouldn't be much of a braid with just Escher and Bach, now would it?
Escher and Bach, a semi-permanent silver braid.
No, I think that'd just be a twisted pair! :0
Yes.
Extending the standard model to include gravity, and thereby creating a "TOE" (Theory of Everything), is not I think going to be hurt by Godel. Because for TOE to work, all it need do is make predictions over and above the standard model, which can be verified by experiment, but also be consistent with all predictions of the standard model. If it can do this, it will stand as a TOE, at least until it disagrees with prediction, if and when that would happen. In other words, a TOE need not be "provable to be consistent in all it axioms". All it needs to do is include the Standard Model's predictions, then, make a few new ones to include gravity. Like one nice prediction would be to have the value of 10^-120 plank units for the energy density of "dark energy" arising naturally and nicely from someplace. That would be a good prediction, just as an example. If a TOE (inclusive of the standard model, plus a description of gravitons which delt with infinities), could regurgitate all standard model predictions, plus just make one prediction more (like setting the energy density of dark energy without having to appeal to the anthropic principle, mind you), then we got a good TOE. "Provable?" No. But it lives to fight another day, which is the best we can ask of a theory anyway.
That's interesting, and I do think that something empirical needs to come into play in order to escape issues with formalism without cheating (Sorry about the incredible vagueness of this sentence). However, what makes me wary of proof by prediction is that it has failed in the past and it is all too obvious why.
At the time, proponents of the Ptolemaic system were able to create a very complicated model that predicted the movements of planets reasonably well (don't know exactly who it was). So judging them by their predictions might have lead to the conclusion that the earth was indeed at the center of the universe.
Also, just try to write unit tests to "prove" that some piece of code is correct with regard to concurrency. What if a particular problem occurs so rarely that it is very unlikely to be caught in any empirical test? What if its occurrence depends on factors that are not well known or hard to replicate?
The problem with predictive models is that they sometimes break down unexpectedly. That doesn't make them useless, but it makes the distinction between logical proof and empirical proof all the more useful.
At the time, proponents of the Ptolemaic system were able to create a very complicated model that predicted the movements of planets reasonably well (don't know exactly who it was). So judging them by their predictions might have lead to the conclusion that the earth was indeed at the center of the universe.
Also, just try to write unit tests to "prove" that some piece of code is correct with regard to concurrency. What if a particular problem occurs so rarely that it is very unlikely to be caught in any empirical test? What if its occurrence depends on factors that are not well known or hard to replicate?
The problem with predictive models is that they sometimes break down unexpectedly. That doesn't make them useless, but it makes the distinction between logical proof and empirical proof all the more useful.
The equation whose roots are the Godel numbers of the proofs that it have no solutions has non-standard solutions. That is why there is no proof that it has no solutions. But the non-standard solution is the Godel number of, err, well what exactly? The trouble with the extra, non-standard numbers is that you cannot reach them by counting, so the proof they number is only finite in the non-standard interpretation. You cannot write it out. It doesn't count because we require that proofs be finite, and by finite we mean finite in the ambient meta-theory, which takes the standard model of the natural numbers.
It would be much better to sumarise Godel's theorem as showing that first order logic fails to tie down the nature of infinity.
Do we care about non-standard arithmetic? If memory serves, there are proofs that non-standard arithmetic is not computable. I can see why Bernie Madoff might find that convenient, but the rest of us can regard the uselessness of non-standard arithmetic as mathematically proven.
Godel's proof shows that first order logic is limited by the existence of mathematical monstrosities that we cannot use (because their arithmetic is not computable) and never encounter (because you cannot reach them by counting)