Yesterday I answered one of Coupon Clipper‘s questions about Godel’s Theorem. Today I’ll tackle the other: Does Godel’s Theorem matter on a day-to-day basis to practicing mathematicians?
And the answer is: Of course not. Mathematicians care about what’s true, not about what’s provable from some arbitrary set of axioms. (Of course this is an overgeneralization; some mathematicians have built distinguished careers on worrying about what’s provable from various sets of axioms. But they are a small minority.) Godel’s Theorem says that not all true things are provable. But for the most part, we’re happy just to know they’re true.
The flashiest example I can give you—and one I’ve used on this blog before—is Fermat’s Last Theorem, which says that no equation of the form xn + yn = zn has any solutions, as long as n is at least 3 and x, y and z are non-zero. Proving this was the was most famous unsolved problem in mathematics for 350 years until it was solved (to much public fanfare) by Frey, Serre, Ribet and Wiles in the 1980’s and 1990’s.
We know from that work that Fermat’s Last Theorem is true. However, we still don’t know whether Fermat’s Last Theorem follows from the standard axioms for arithmetic. And—this is the point—very few mathematicians care very much, at least by comparison to how much they care about the theorem itself. (Here is one of my favorite papers on the subject. Tellingly, the author is a philosopher.)
In Chapter 10 of The Big Questions, you’ll find a description of a game called “Hercules versus the Hydra”. It turns out that Hercules always wins the game, no matter how stupidly he plays. This fact (that Hercules always wins) is known to be true and known to be unprovable from the standard axioms. Fermat’s Last Theorem, by contrast, is known to be true and might or might not be unprovable from the standard axioms. If that question gets settled, most mathematicians will be interested enough to sit up and take notice. But unlike the Last Theorem itself, few are motivated to work on it.
12pm NY and I’m first comment? unusual.
I’m mainly hanging out for the Dinesh debate (I understand you’re still waiting for the video).
In the meantime, this amused me immensely:
http://www.theonion.com/articles/god-cites-moving-in-mysterious-ways-as-motive-in-k,535/
Just to clarify. H vs H is known to be solvable by proofs using ZFC (more or less the generally more or less reluctantly accepted axiomatic basis of the set theory used in mathematics) but it is not known if it is provable from PA, the Peano Axioms that *seem* (and were once generally assumed) to be a basis for arithmetic. Is this correct?
It is more interesting that possible changes to ZFC (which abound) as ZFC has always been seen as a bit suspect, but the PA seemed rock solid.
Ken B: it is not known if it is provable from PA, the Peano Axioms
This is incorrect. It is known NOT to be provable from PA.
Dave:
“My ways are mysterious, sometimes even to Myself.”
You say that mathematicians don’t care much about Peano arithmetic, but do you say tha same about ZFC? Your source says that it is not clear that FLT has been proved in ZFC, and a lot of mathematicians believe that theorems should be provable in ZFC.
Roger: If it were to turn out that FLT has not been proved—or even more spectacularly, is unprovable—in ZFC, that mathematicians would be considerably more shocked than if the same were true of PA. But my guess is that nobody’s faith in the truth of FLT would be shaken. Instead, most mathematicians would stop believing that theorems should be provable in ZFC.
I’m having trouble with what mathematicians think about what is “true” versus what is “provable”. From my reading of TBQ, it seems that the mathematical definition of “truth” is “proof by consistency with a set of axioms presumed to be true”. Is that right? Is that not tautological?
My own definitions of truth are 1) logical deduction from axioms and 2) empirical induction from observation and experimentation (and therefore provisional).
I guess I am okay with truth based on the consistency of axioms that are empirically true (provisionally), but such truth is also provisional by extension.
Correct that definition of mathematical truth to be “derivable from a set of axioms presumed to be true and consistent”.
Neil: No, truth has nothing to do with derivability from axioms.
A sentence like “2+3=5” is true if it is the case that the number 2 plus the number 3 is equal to the number 5.
A sentence like “Every number is the sum of four squares” is true if it is the case that every individual number is the sum of four squares.
Et cetera.
Simple and obvious as this definition may look, it took Alfred Tarski to get it right.
Steve, you are taking an extreme view when you say that “truth has nothing to do with derivability from axioms”. I have never heard of a mathematician claiming that something was true, unless it was derivable from the axioms.
Roger: Every statement, of course, is derivable from axioms, because any statement can be taken as an axiom. But that is not what *makes* a true statement true. In fact, this does not even distinguish true statements from false ones—they’re *all* derivable from axioms.
Derivability (from known-to-be-true axioms) can be relevant to how we *know* that a statement is true, but not to why the statement is true in the first place—and the few mathematicians I’ve heard of who believe otherwise are far out of the mainstream.
“A sentence like “2+3=5″ is true if it is the case that the number 2 plus the number 3 is equal to the number 5.”
Thanks Steve. I appreciate your willingness to engage your reader on this, and I will reread those chapters of TBQ.
If I may, I would like to contend that your statement, quoted above, is empirical.
Someone, long ago, noticed that if you have two stones and add three more stones, you have five stones. He, or someone else, noticed that if you have two apples, and add three more apples, you have five apples. Eventually someone, incredibly brilliant, generalized this and claimed if we have two of ANYTHING and add three more of the same thing, we have five of that thing, whatever it is. And so we induct the truth of 2+3=5.
That, IMO, is an empirical statement, and provisional.
To make the point, sometime, long ago, someone noticed that a stone is in location A or it is in location B, but it cannot be in both, and she, or someone else, noticed that an apple is in location A or or in location B, but not both. Then someone, incredibly brilliant, generalized and said that ANYTHING is at location A or is in location B, but not both. But this brilliant person was eventually proved wrong, because later we discovered that an object, an electron, can be both in location A and in location B.
Thus, as an empiricist, I must hold open the possibility that someday some object, call it X, may be discovered such that when we have two X and add three more X, we do not have five X. Thus, 2+3=5 is an empirical statement, and provisional.
Perhaps I am crazy, and I do not expect X to be discovered in my lifetime, but I cannot foreclose the possibility.
As an Italian fellow once told me, “What is truth?”
Roger: “I have never heard of a mathematician claiming that something was true, unless it was derivable from the axioms.”
You’ve never met a mathematician who accepts Gödel’s theorem?
And what do you mean by “the axioms,” kemosabe?
Neil: It seems to me that numbers are very different from locations, in that locations are part of the *physical* world, so that we can learn about them through observation, whereas numbers exist in an ideal Platonic world, where our physical observations are irrelevant. Thus if we were to discover your object X, I would want to conclude not that 2+3 fails to equal 5, but that your object X does not obey the laws of arithmetic—though the laws of arithmetic themselves have not changed.
If you see this otherwise, then I think the following things are true: a) Your way of seeing it is perfectly reasonable. b) Nevertheless, I’m pretty sure it’s wrong. c) I can’t prove that to you. d) I think the great majority of mathematicians would agree with me. e) Point d) doesn’t prove anything, of course.
Bob, Goedel’s theorem is derivable from the axioms.
Steve, I guess that you are backing off your claim that “truth has nothing to do with derivability from axioms”. You seem to admit that we know that a statement is true if it is derivable from the axioms.
Roger: You seem to admit that we know that a statement is true if it is derivable from the axioms.
1) No. A statement is true if it is derivable from *true* axioms, not if it is derivable from *any* axioms. (And note the “if”, which is pointedly not an “if and only if”.)
2) And no again. *Truth* has nothing to do with derivability from axioms. Our *knowledge* of what’s true sometimes comes from derivability from axioms.
Roger: Let me say more—in a subject like, say, group theory or some branches of geometry, it’s often the case that the only statements we care about are statements of the form “Such-and-such is derivable from the axioms”. So the true statements we care about are in one-one correspondence with statements derivable from the axioms of the subject. But arithmetic isn’t like that, because arithmetic, unlike group theory, is about a specific pre-existing object (namely the natural numbers) which, unlike, say, a group or a model of euclidean geometry, is not defined by axioms in the first place.
Roger: “Goedel’s theorem is derivable from the axioms.”
1. That’s an elegant way to avoid my point.
2. Again with “the axioms”? What axioms?
Steve, I think you’re confusing Roger and I by jumping back and forth between faith & knowledge, truth & provability.
For example,
“…nobody’s faith in the truth of FLT would be shaken”
vs.
“We know from that work that Fermat’s Last Theorem is true. However, we still don’t know whether Fermat’s Last Theorem follows from the standard axioms for arithmetic.”
You also said:
“Godel’s Theorem says that not all true things are provable. But for the most part, we’re happy just to know they’re true.”
We can say we believe a thing to be true, and we can definitely say it either is or isn’t true, regardless of our belief. But why would you say you know something to be true if you can’t prove it? (formally speaking, that is — colloquially we use a lot of words imprecisely and everybody knows what we mean, but I believe you try to be formally precise on this blog.)
Bob, the most popular axiom system is ZFC.
Steve, I think that your view is in a very small minority among mathematicians.
jj: We can say we believe a thing to be true, and we can definitely say it either is or isn’t true, regardless of our belief. But why would you say you know something to be true if you can’t prove it?
I wouldn’t. We know that FLT is true because it’s been proved, and I believe it because I understand enough of the idea behind the proof that I think it’s probably right. But I still have no idea whether it can be proved *from the standard axioms for arithmetic*.
Roger: ZFC has been around for a century or so. The natural numbers have been around forever (if you’re a Platonist) or for hundreds of thousands of years (if you think they were invented by early humans). If a conflict arises between what we know about the natural numbers and what we can prove with ZFC, I have no doubt which one we’ll be quick to jettison.
ZFC has only been around for one century, but mathematical reliance on proof from axioms has been around for 23 centuries. You will have a tough time convincing me that some mathematical statement is true if you cannot provide a proof.
You will have a tough time convincing me that some mathematical statement is true if you cannot provide a proof.
Roger: Do you believe that every natural number can be reached from zero via a finite number of applications of the successor function? Not only can’t you prove that in first order Peano arithmetic, you can’t even *state* it in first order Peano arithmetic. And if you *could* state it, you still couldn’t prove it, because it does not follow semantically from the axioms. (That is, there are structures that satisfy all the axioms but do not satisfy this statement, so there is no possible sense in which the statement could follow from the axioms.) So by the conventional standards of proof, using the conventional axioms for arithmetic, I cannot prove this statement for you. But I bet you believe it.
How could I believe a statement that cannot be stated? While it cannot be stated in PA, it can be stated and proved in ZFC.
You act like all this Goedel stuff is a reason to reject axiomatization. If a statement is true in the sense of being true in every valid model, then there is a finite proof from the axioms. Nearly all of mathematics is based on proving theorems from the axioms. We have no other way of discovering mathematical truth.
Roger: We have no other way of discovering mathematical truth.
So you’re saying that in the absence of ZFC you’d have no way of knowing that the natural numbers consist of 0,1,2,…. and nothing else?
Roger: “the most popular axiom system is ZFC.”
So Truth is a matter of popularity?
Bob, I have my own opinions about truth. You can ignore what is popular if you wish.
Steve, a great deal was learned about N (nat. numbers) before PA and ZFC. Usually the knowledge was of the form of theorems proved from axioms. In some cases, there were gaps that were filled in later. In other cases, the arguments were determined to be wrong. Some cases are still open, like the Riemann hypothesis. I would say that we have no way of knowing the Riemann hypothesis unless someone proves (or disproves) it in ZFC.
Roger: I would say that we have no way of knowing the Riemann hypothesis unless someone proves (or disproves) it in ZFC.
And I would say that if someone proves the Riemann Hypothesis using the Grothendieck machinery (come to think of it, someone *did* prove a version of the Riemann Hypothesis using the Grothendieck machinery) then we will know that it is true *whether or not* the Grothendieck machinery can be formalized in ZFC. And I feel quite sure that nearly all mathematicians would agree with this, as nearly all mathematicians accept the vast array of theorems that *have* been proved with the Grothendieck machinery. There is nothing sacred about ZFC.
Your philosopher source (McLarty) says “While Deligne often uses universes he stresses in conversation that they are a convenience technically eliminable in favor of ZFC.” [top of p.14]
It appears to me that Deligne thinks that it is important that his use of the Grothendieck machinery can be formalized in ZFC.
If Deligne had expressed your opinion instead, and expressed doubt about whether his proofs could be formalized in ZFC, then I think that a great many mathematicians would have doubts about Deligne’s theorems.
Roger: But here, I think, is the key example: What about the statement that ZFC is consistent? Your willingness to work within ZFC suggests that you’re at least pretty sure of this statement, even though it’s not provable in ZFC. So there’s something that you seem to be pretty sure is true even though ZFC can’t prove it.
Yes, I am pretty sure that ZFC is consistent, even tho I cannot prove it within ZFC. It can be proved in larger axiom systems, so if you don’t mind those extra axioms for Grothendieck’s tools, maybe you won’t mind the axioms that allow proving that ZFC is consistent.
There is no math paper demonstrating the truth of the consistency of ZFC, except for those that derive it from axioms in a larger system, as above.
I might believe that S6 has no complex structure, but that does not make it a mathematical truth unless someone finds a proof. So you may have an unproved belief if you want, but it is certainly the case that mathematicians care deeply about having a finite proof from the axioms.
Now why am I reminded of good ol’ Brecht?
After the uprising on June 17th,
The Secretary of the Writers Union
Had leaflets distributed in the Stalinallee
Upon which was to be read that the people
Had forfeited the confidence of the government
And could only reclaim it
Through redoubled efforts. Would it not be easier
Still for the government
To dissolve the people
And elect another?
—Bertolt Brecht, “The Solution,” Buckow Elegies No. 9 (S.H. transl)
Let NN be the natural numbers existing as a platonic idea.
Let “NN” be the natural numbers defined by some set of axioms.
We can BELIEVE in some properties of NN.
We can KNOW some properties of “NN”.
We can BELIEVE that NN = “NN”
But we can’t KNOW anything about NN.
jj:
Let “NN” be the natural numbers defined by some set of axioms.
I have no idea what this means.
Steve, you seem to be palming a card here, specifically that you’re assuming you somehow know, for an arbitrary statement, what is “true”. You bring in Tarski for support in the sense that Tarski in some sense defined the difference between that which can be proven in under a formal system and that which is true. Now, you don’t specify how you’re referring to Tarski, but I presume you’re meaning via model theory; the thing being that while model theory does make that distinction, it doesn’t tell us how to tell what is “true” — it just tells us that there is a correspondence between the statements of a formal system and statements which we know, using something outside the system, to be “true”.
Thus, for example, we have a sentence “2+3=5”; we have a formal interpretation of that as “the third successor of the second successor of 0 is the same construct as the fifth successor of 0” via Peano; and we can show that correspondence seems to match what we find to be “true”.
What it doesn’t do is tell us anything about what is “true”, and in fact we can easily find examples of systems in which what is “true” in one system isn’t necessarily “true” in another.
The hidden assumption here appears to be essentially Platonic: that there is a single, ideal Truth to which we can refer.
As an assumption, an axiom, this seems perfectly reasonable, but it is an assumption, and a somewhat controversial one. Certainly it’s one you can’t use model theory to support, since we know (cf. Robinson’s nonstandard analysis versus standard analysis) that it’s perfectly possible to have one formal system with models M_0 and M_1 in which statements that are referred to as “true” in one system aren’t considered “true” in the other.
Oh, wait, one other thing. You’re asked “Does Godel’s Theorem matter on a day-to-day basis to practicing mathematicians?”, to which you answer “no.”
The answer is actually “yes”, at least unless you’re artificially restricting the class of ‘working mathematicians.”
Now, do people doing analysis usually care? Nope, hardly ever, just like they don’t usually really care if you can get to the standard axioms at the front of Apostol from Whitehead and Russell. But it matters dramatically, for example, to logicians; it’s a central result — along with its morphisms to Turing’s Theorem and Chaitin’s algorithmic complexity — in theory of computer science, and the metamathematical tool of the “diagonalization” method gets practically beaten to death in a good CS theory course.
Charlie Martin:
The hidden assumption here appears to be essentially Platonic: that there is a single, ideal Truth to which we can refer.
As an assumption, an axiom, this seems perfectly reasonable, but it is an assumption, and a somewhat controversial one.
It’s better, I think, not to use the word “axiom” here, since the word is already being used in this discussion to refer to the axioms of some formal system like Peano arithmetic, and what you’ve got in mind is something else altogether. Let’s stick with “assumption”.
it’s perfectly possible to have one formal system with models M_0 and M_1 in which statements that are referred to as “true” in one system aren’t considered “true” in the other.
Sure. But what I’m talking about here is truth within the standard model of the natural numbers.
Now you might say that the existence of the standard model is an assumption, and so it is, in exactly the same sense that the existence of the external world or of conscious minds other than your own is an assumption. But, just like those assumptions, it’s one that we all learned by age six that we can’t possibly live without.
So to summarize, when I say “true”, I mean “true about the natural numbers”, and when I say “the natural numbers”, I mean the numbers 0,1,2,3, et cetera. No first order logical system can formalize what “et cetera” means here, but every six year old knows what it means perfectly well. It’s that six year old understanding I’m appealing to.
(PS: This is as good a place as any to mention that you don’t need Godel to know that no first-order system can distinguish a unique model of the natural numbers; Lowenheim-Skolem is enough for that.)
Charlie Martin:
You’re asked “Does Godel’s Theorem matter on a day-to-day basis to practicing mathematicians?”, to which you answer “no.” The answer is actually “yes”, at least unless you’re artificially restricting the class of ‘working mathematicians.”
This is exactly why I qualified my statement thus:
(Of course this is an overgeneralization; some mathematicians have built distinguished careers on worrying about what’s provable from various sets of axioms. But they are a small minority.)
ive missed a week and am still catching up.
/agree neil
forever is a long time. im thinking natural numbers had a pretty ancient origin in that several species exhibit ‘self-awareness’ and are thus cognisant of 0, 1, and at least 2.
too bad plato isnt still around to argue with.