Does Gödel Matter?
slate.com
slate.com
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)
You're thinking of the wrong book...
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.
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 :-/
Also, there are the cardinal numbers, for which the interesting ones consist entirely of infinity.
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...
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.
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).
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!
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.
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).
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.
Thanks for the link.
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.
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.
Also, the halting problem's insolvability is straightforward to see without knowing any of Godel's work. :)
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:
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.