Who's afraid of Kurt Gödel?
December 22, 2005 6:54 AM Subscribe
Help show me that Gödel's theorem isn't that big of a deal.
A while back, I was surprised by:
Infinity--more precisely the axiom of infinity--stalks every page. This axiom says that the collection of all natural numbers exists as a set, on a par with all other sets. It is a very convenient axiom, and almost no practicing mathematician hesitates to use it. But it is not indispensable, as Kronecker and Brouwer, the fathers of intuitionism, correctly saw. The so-called constructivists (who are the modern intuitionists and who generally wear the mantle only part time) have effectively shown that all modern mathematics, including measure theory(!) (but not logic itself) can be reconstructed without its aid. Therefore it is wrong for Deutsch to make heavy use of Gödel's theorem (which depends on the axiom of infinity) to reach such conclusions as "Mathematicians [have made the mistake of thinking] that mathematical knowledge is more certain than other forms of knowledge." "Mathematical knowledge may, just like our scientific knowledge, be deep and broad, it may be subtle and wonderfully explanatory, it may be uncontroversially accepted; but it cannot be certain." The fact is that Gödel's examples of true theorems that cannot be proved within the framework of the standard axioms (or extensions thereof) always differ in fundamental ways from the bulk of the theorems that excite mathematicians' interest.
(from here).
A lot of books get all excited about Godel's theorem. I've read some of them. But what I'm looking for now is something that illustrates the above. I have Just and Weese, but it's kind of dry, and I'm only guessing that it's relevant (having only read a chapter or two, and that some years ago). Is there anything a bit more populist and fun?
In particular I'd like to understand how "real" theorems are different from Gödel's examples. Also, how much does it "hurt" to not have logic?
An anti-GEB?
A while back, I was surprised by:
Infinity--more precisely the axiom of infinity--stalks every page. This axiom says that the collection of all natural numbers exists as a set, on a par with all other sets. It is a very convenient axiom, and almost no practicing mathematician hesitates to use it. But it is not indispensable, as Kronecker and Brouwer, the fathers of intuitionism, correctly saw. The so-called constructivists (who are the modern intuitionists and who generally wear the mantle only part time) have effectively shown that all modern mathematics, including measure theory(!) (but not logic itself) can be reconstructed without its aid. Therefore it is wrong for Deutsch to make heavy use of Gödel's theorem (which depends on the axiom of infinity) to reach such conclusions as "Mathematicians [have made the mistake of thinking] that mathematical knowledge is more certain than other forms of knowledge." "Mathematical knowledge may, just like our scientific knowledge, be deep and broad, it may be subtle and wonderfully explanatory, it may be uncontroversially accepted; but it cannot be certain." The fact is that Gödel's examples of true theorems that cannot be proved within the framework of the standard axioms (or extensions thereof) always differ in fundamental ways from the bulk of the theorems that excite mathematicians' interest.
(from here).
A lot of books get all excited about Godel's theorem. I've read some of them. But what I'm looking for now is something that illustrates the above. I have Just and Weese, but it's kind of dry, and I'm only guessing that it's relevant (having only read a chapter or two, and that some years ago). Is there anything a bit more populist and fun?
In particular I'd like to understand how "real" theorems are different from Gödel's examples. Also, how much does it "hurt" to not have logic?
An anti-GEB?
Read about ZF set theory as a grounded approach to constructing a theoretical system.
posted by ny_scotsman at 7:44 AM on December 22, 2005
posted by ny_scotsman at 7:44 AM on December 22, 2005
Also, this book: Realistic Rationalism may be what you're looking for. He argues from the point of view that says that mathematical objects are real objects, but which don't exist in the real world.
posted by bshort at 7:46 AM on December 22, 2005
posted by bshort at 7:46 AM on December 22, 2005
(forgot about this when I posted first...)
Check out why 2+2=4 on metamath.org for a wonderfully detailed look inside ZF theory (and much more). It doesn't address the eternal verities per se but at least you can play around with a lower bound on what you have to take on principle in order for lots of stuff to make sense.
posted by ny_scotsman at 8:03 AM on December 22, 2005
Check out why 2+2=4 on metamath.org for a wonderfully detailed look inside ZF theory (and much more). It doesn't address the eternal verities per se but at least you can play around with a lower bound on what you have to take on principle in order for lots of stuff to make sense.
posted by ny_scotsman at 8:03 AM on December 22, 2005
Response by poster: thanks, but zf includes the axiom of infinity (i believe), as does the proof linked to of 2+2. the quote i gave suggested that is unnecessary, but that you lost logic. so i don't think zf is exactly the answer here (but i may be wrong).
also, i was looking for a good "popular" book (the book i referred to is a grad text in set theory), if possible. actually, maybe i just need to reread the introduction to just + weese again, now that i actually take it down from the shelf and look at it...
posted by andrew cooke at 8:17 AM on December 22, 2005
also, i was looking for a good "popular" book (the book i referred to is a grad text in set theory), if possible. actually, maybe i just need to reread the introduction to just + weese again, now that i actually take it down from the shelf and look at it...
posted by andrew cooke at 8:17 AM on December 22, 2005
Wish you could link directly to the photos.
Gödel's theorem was a big deal when it was released. Keep in mind it basically destroyed several people's life work (Bertrand Russell was one) by showing that what they were trying to do was impossible (which was to construct a formal mathematical system, like a programming language, that could be used to prove any mathematical truth. They wanted to build a machine that you could turn on and eventually spit out all mathematically provable theorems)
I also don't think Gödel's theorem has anything to do with Infinity, by the way, from what I understand of it. (Also, Gödel has two incompleteness theorems).
The wikipedia entry on Gödel's incompleteness theorem has gotten a lot better since the last time I read it, the explanations there are quite clear.
It's a theory that caused the world's greatest mathematicians to give up their life's work, so I find it impossible to believe that it could be wrong in anyway. Russell et.al. would have found the errors if they existed.
As to whether the theorem is really that big a deal? Well, it certainly was to mathematicians at the time, but it really does speak to the structure of mathematics itself and what's possible to do with it. It might not seem like a big deal today (especially to non-mathematicians) but that's because nobody tries to do anything that the theorem says can't be done. (Just like no one tries to discover the luminous aether or phlogiston anymore)
posted by delmoi at 8:33 AM on December 22, 2005
Gödel's theorem was a big deal when it was released. Keep in mind it basically destroyed several people's life work (Bertrand Russell was one) by showing that what they were trying to do was impossible (which was to construct a formal mathematical system, like a programming language, that could be used to prove any mathematical truth. They wanted to build a machine that you could turn on and eventually spit out all mathematically provable theorems)
I also don't think Gödel's theorem has anything to do with Infinity, by the way, from what I understand of it. (Also, Gödel has two incompleteness theorems).
The wikipedia entry on Gödel's incompleteness theorem has gotten a lot better since the last time I read it, the explanations there are quite clear.
It's a theory that caused the world's greatest mathematicians to give up their life's work, so I find it impossible to believe that it could be wrong in anyway. Russell et.al. would have found the errors if they existed.
As to whether the theorem is really that big a deal? Well, it certainly was to mathematicians at the time, but it really does speak to the structure of mathematics itself and what's possible to do with it. It might not seem like a big deal today (especially to non-mathematicians) but that's because nobody tries to do anything that the theorem says can't be done. (Just like no one tries to discover the luminous aether or phlogiston anymore)
posted by delmoi at 8:33 AM on December 22, 2005
I recommend Raymond Smullyan's book, What Is The Name of This Book?. The last pages give a cogent presentation of Gödel's theorem. Smullyan notes, "my account of Gödel's method departs somewhat from Gödel's original one--primarily in that it employs the notion of truth, which Gödel did not do."
posted by gregoreo at 8:41 AM on December 22, 2005
posted by gregoreo at 8:41 AM on December 22, 2005
Wow, scratch the first line of my comment, I must have left that in my editor from earlier. *sigh*.
posted by delmoi at 8:47 AM on December 22, 2005
posted by delmoi at 8:47 AM on December 22, 2005
Response by poster: just to clarify, i guess i'm looking for a popular book exploring the implications of basing mathematics on a set of axioms that does not include the axiom of infinity. i am not looking for an explanation of godel's work.
or a quick argument showing why the text i quote is mistaken, of course.
apologies for not asking this sooner - i was hoping that leaving it more open would lead to further interesting avenues to explore. but at the moment this is heading rapidly towards a million people telling me how cool GEB is.
posted by andrew cooke at 8:49 AM on December 22, 2005
or a quick argument showing why the text i quote is mistaken, of course.
apologies for not asking this sooner - i was hoping that leaving it more open would lead to further interesting avenues to explore. but at the moment this is heading rapidly towards a million people telling me how cool GEB is.
posted by andrew cooke at 8:49 AM on December 22, 2005
GEB actually does address this question somewhat. In the sections on non-standard number theory (Chapter XIV: "On Formally Undecidable Propositions..."), Hofstadter shows how the unprovable propositions found by Gödel can actually be considered either true or false. Either choice yields a consistent mathematical system, just as changing geometrical axioms yields consistent (but non-Euclidean) geometries.
Especially see "Supernatural Theorems Have Infinitely Long Derivations" (p 454), which explains how Gödel's unprovable propositions can be considered theorems that have no finite proof, but that can be proven with the use of infinite proofs in a non-standard number theory system; and the section on ω-incompleteness, which explains somewhat how the unprovable propositions differ from other theorems.
posted by mbrubeck at 9:04 AM on December 22, 2005
Especially see "Supernatural Theorems Have Infinitely Long Derivations" (p 454), which explains how Gödel's unprovable propositions can be considered theorems that have no finite proof, but that can be proven with the use of infinite proofs in a non-standard number theory system; and the section on ω-incompleteness, which explains somewhat how the unprovable propositions differ from other theorems.
posted by mbrubeck at 9:04 AM on December 22, 2005
Ah, I see what you're asking for now. Not that it necessarily helps, but an alternative statement of the axiom of infinity is that "there exists a set that is a proper subset of its union" which at least dispenses with the natural numbers aspect. Hm. I suppose if you're looking for a book, popular or not, that develops a (correct) theory without including this axiom, you wouldn't find it in this library. Although the book that explains why it's required would certainly be there, probably twice!
posted by ny_scotsman at 9:23 AM on December 22, 2005
posted by ny_scotsman at 9:23 AM on December 22, 2005
Godel's theorem is a big deal, because it overturned Hilbert's program, and undermined the general idea that all knowledge could be formalized.
posted by orthogonality at 9:46 AM on December 22, 2005
posted by orthogonality at 9:46 AM on December 22, 2005
Not that it necessarily helps, but an alternative statement of the axiom of infinity is that "there exists a set that is a proper subset of its union" which at least dispenses with the natural numbers aspect.
Be careful, that's not equivalent without the Axiom of Choice.
andrew, I don't know of an actual popular exposition of finitist mathematics -- a place to start looking would be articles by Wilfried Sieg, who has given a number of papers and lectures on Hilbert's finitism program and relationships to constructivism and structuralism. I have a few papers/books at home as well which I'll post the names of after work today.
posted by j.edwards at 11:14 AM on December 22, 2005
Be careful, that's not equivalent without the Axiom of Choice.
andrew, I don't know of an actual popular exposition of finitist mathematics -- a place to start looking would be articles by Wilfried Sieg, who has given a number of papers and lectures on Hilbert's finitism program and relationships to constructivism and structuralism. I have a few papers/books at home as well which I'll post the names of after work today.
posted by j.edwards at 11:14 AM on December 22, 2005
If I'm reading what you guys are saying, you're talking about Gödel not applying to mathematical systems with a finite set of numbers. In other words, in a mathematical space where there was a 'largest number', Gödel doesn’t apply (because you can prove anything simply by testing your theory on every number).
That's cute, but it seems like a rather dull universe (although somewhat practical, because in the real world we are always working with finite amounts of stuff. Hmm.)
But Andrew, I definitely recommend you click around on Wikipedia and learn more about the mathematics at the time (like Hilbert's program, which I just found out about today) and how Godel's proof really demolished the whole thing.
posted by delmoi at 11:33 AM on December 22, 2005
That's cute, but it seems like a rather dull universe (although somewhat practical, because in the real world we are always working with finite amounts of stuff. Hmm.)
But Andrew, I definitely recommend you click around on Wikipedia and learn more about the mathematics at the time (like Hilbert's program, which I just found out about today) and how Godel's proof really demolished the whole thing.
posted by delmoi at 11:33 AM on December 22, 2005
delmoi - It sounds like you're referring to group theory. There are certainly unproven theorems in group theory even though you're dealing with finite constructs.
posted by bshort at 11:51 AM on December 22, 2005
posted by bshort at 11:51 AM on December 22, 2005
Response by poster: delmoi - if you are interested in the history of maths, you might enjoy this book. although i found it rather dry i'm going to look up "finitist" in the index tomorrow, when i get back home (hmmm. there seems to be a pattern here - maybe i should just finish the books on maths that i already own! on the other hand, exchanges like this help me cross connect things a bit more and so encourage me to trudge on...).
posted by andrew cooke at 11:56 AM on December 22, 2005
posted by andrew cooke at 11:56 AM on December 22, 2005
What makes Goedel's theorem important is that it answered famous unsolved problems and that it started new avenues of research. That's how all mathematical theorems are judged: by how much mileage other mathematicians get out of them. The importance of that theorem does not lie in any revelations about the human condition, limits of human knowledge, or life on Mars. (This is from a mathematician's point of view.)
As for math without the axiom of infinity, well, the vast majority of mathematicians think that all the axioms of ZFC are perfectly reasonable and very intuitive. If you drop some of the axioms, then many of the things that mathematicians believe to be true are all of a sudden impossible to prove, and many other bits become much more messy. So, most mathematicians would tell you that there is simply no good reason to drop any of the ZFC axioms. Still, many logicians research precisely this sort of thing: what can and can't be proved when you alter the axioms.
For example, my own field is ring theory. A ring is a set with some additional properties, so if you disallow infinite sets, then there will only be finite rings. While a lot can be said about finite rings, the vast majority of the things that make rings interesting would just disappear. The effect would be similar across pretty much all fields of math.
Finally, it is not true, as the passage quoted in the question states, that examples of true theorems that cannot be proved within the framework of the standard axioms always differ in fundamental ways from the bulk of the theorems that excite mathematicians' interest. For example, there is the Continuum Hypothesis. It states that there is no set whose size is strictly bigger than that of the set of natural numbers but strictly smaller than that of the set of real numbers. Both the Continuum Hypothesis and its negation are consistent with ZFC. (Of course, you need the axiom of infinity to even state the Continuum Hypothesis.)
posted by epimorph at 3:17 PM on December 22, 2005
As for math without the axiom of infinity, well, the vast majority of mathematicians think that all the axioms of ZFC are perfectly reasonable and very intuitive. If you drop some of the axioms, then many of the things that mathematicians believe to be true are all of a sudden impossible to prove, and many other bits become much more messy. So, most mathematicians would tell you that there is simply no good reason to drop any of the ZFC axioms. Still, many logicians research precisely this sort of thing: what can and can't be proved when you alter the axioms.
For example, my own field is ring theory. A ring is a set with some additional properties, so if you disallow infinite sets, then there will only be finite rings. While a lot can be said about finite rings, the vast majority of the things that make rings interesting would just disappear. The effect would be similar across pretty much all fields of math.
Finally, it is not true, as the passage quoted in the question states, that examples of true theorems that cannot be proved within the framework of the standard axioms always differ in fundamental ways from the bulk of the theorems that excite mathematicians' interest. For example, there is the Continuum Hypothesis. It states that there is no set whose size is strictly bigger than that of the set of natural numbers but strictly smaller than that of the set of real numbers. Both the Continuum Hypothesis and its negation are consistent with ZFC. (Of course, you need the axiom of infinity to even state the Continuum Hypothesis.)
posted by epimorph at 3:17 PM on December 22, 2005
OK, here's a more concrete example of what math without infinite sets would be like: calculus, as we know it, would die. Calculus mostly deals with functions on the set of real numbers. Well, without the axiom of infinity the real numbers would not form a set. (Actually, you may not even be able to define real numbers without that axiom.) So you couldn't make sense of sentence like "integrate f(x) = e^(-x) from zero to infinity", since it assumes that f is a function from the set of real numbers to the set of real numbers.
Whatever bits of calculus you could salvage would probably be of limited use to, say, engineers and physicists, not to mention mathematicians.
posted by epimorph at 4:15 PM on December 22, 2005
Whatever bits of calculus you could salvage would probably be of limited use to, say, engineers and physicists, not to mention mathematicians.
posted by epimorph at 4:15 PM on December 22, 2005
Response by poster: hi epimorph - what i'm interested in is how complete it's possible to be without the axiom of infinity. i've just been skimming through my basic intro to set theory over dinner and while they spend some time discussing the axiom of choice, they don't bother to question infinity. yet the quote says "all of modern mathematics". if that's the case then it seems quite odd, to me, that "everyone" is so happy to include it.
it just struck me as odd that there's that review - apparently written by a sane and reasonable mathematician - that happily discards an axiom of mathematics that (almost) everyone assumes is completely necessary. and that he can get away with it and still produce, apparently, a large fraction of what we have. don't you think that's odd?
and what about those other "necessary" axioms?
as for your final point - i'm more interested in what he's using for a definition of "interesting" rather than trying to find holes in what he says. after all, presumably he's aware of the continuum hypothesis. in other words: the fact that he writes that suggests that there is a definition of "interesting" for which it makes sense, and i'm curious what that might be.
(on preview - cool, thanks. that's exactly what i was looking for. although i'm not sure you're right. it's a pretty sketchy definition of "all of modern maths" that excludes real numbers. so i half suspect (no offence!) that there's some alternate approach, although i haven't a clue what it is.)
posted by andrew cooke at 4:25 PM on December 22, 2005
it just struck me as odd that there's that review - apparently written by a sane and reasonable mathematician - that happily discards an axiom of mathematics that (almost) everyone assumes is completely necessary. and that he can get away with it and still produce, apparently, a large fraction of what we have. don't you think that's odd?
and what about those other "necessary" axioms?
as for your final point - i'm more interested in what he's using for a definition of "interesting" rather than trying to find holes in what he says. after all, presumably he's aware of the continuum hypothesis. in other words: the fact that he writes that suggests that there is a definition of "interesting" for which it makes sense, and i'm curious what that might be.
(on preview - cool, thanks. that's exactly what i was looking for. although i'm not sure you're right. it's a pretty sketchy definition of "all of modern maths" that excludes real numbers. so i half suspect (no offence!) that there's some alternate approach, although i haven't a clue what it is.)
posted by andrew cooke at 4:25 PM on December 22, 2005
Response by poster: heh. the quote comes from dewitt (the famous physicist). it makes no sense for a physicist to be pushing the idea that calculus is impossible. and he gives as an example measure theory (integration)...
posted by andrew cooke at 4:34 PM on December 22, 2005
posted by andrew cooke at 4:34 PM on December 22, 2005
Hi Andrew. Foundations of mathematics really isn't my area, so I'll be the first to admit that what I say should be taken with a grain of salt.
But, to be fair, I never said that calculus would be impossible, just calculus as we know it. I can imagine some discrete version of it. Also, measure theory is only one ingredient of calculus.
In the end, I haven't encountered any respected mathematician who seriously questioned infinity. In fact, even the ones who just question choice are kind of looked at as lunatics.
posted by epimorph at 7:01 PM on December 22, 2005
But, to be fair, I never said that calculus would be impossible, just calculus as we know it. I can imagine some discrete version of it. Also, measure theory is only one ingredient of calculus.
In the end, I haven't encountered any respected mathematician who seriously questioned infinity. In fact, even the ones who just question choice are kind of looked at as lunatics.
posted by epimorph at 7:01 PM on December 22, 2005
Response by poster: incidentally, there's an example of the constructivist approach to real analysis in the wikipedia page on constructivism.
posted by andrew cooke at 2:12 AM on December 23, 2005
posted by andrew cooke at 2:12 AM on December 23, 2005
Response by poster: and this article gives a pretty good description of constructivist logic (and its limitations). it also shows the relationship to computing.
(and at one point there's a derivation of the axiom of choice (in a particular variety of modern constructive mathematics), but by that far down the page i was pretty much lost...)
posted by andrew cooke at 2:38 AM on December 23, 2005
(and at one point there's a derivation of the axiom of choice (in a particular variety of modern constructive mathematics), but by that far down the page i was pretty much lost...)
posted by andrew cooke at 2:38 AM on December 23, 2005
Response by poster: and a nice constructive maths faq
posted by andrew cooke at 2:42 AM on December 23, 2005
posted by andrew cooke at 2:42 AM on December 23, 2005
Response by poster: and, finally(?), that faq includes a passing reference to constructive zf set theory which, presumably, is zf without the axiom of infinity (and without the axiom of choice, if i understand the relationship between that and the excluded middle, which i probably don't, but never mind).
so it looks like the connection this approach has with computers (that proofs are effectively algorithms) has led to some kind of revival in its study.
which is nice.
posted by andrew cooke at 2:47 AM on December 23, 2005
so it looks like the connection this approach has with computers (that proofs are effectively algorithms) has led to some kind of revival in its study.
which is nice.
posted by andrew cooke at 2:47 AM on December 23, 2005
Response by poster: this thread continues at http://www.acooke.org/cute/MoreConstr0.html
posted by andrew cooke at 4:49 AM on January 21, 2006
posted by andrew cooke at 4:49 AM on January 21, 2006
This thread is closed to new comments.
It just means we can't know absolutely everything.
posted by bshort at 7:43 AM on December 22, 2005