Posted on 02/15/2005 2:39:04 PM PST by snarks_when_bored
John Patrick Naughton Rebecca Goldstein's new book is about the mathematician Kurt Gödel. 
elativity. Incompleteness. Uncertainty.
Is there a more powerful modern Trinity? These reigning deities proclaim humanity's inability to thoroughly explain the world. They have been the touchstones of modernity, their presence an unwelcome burden at first, and later, in the name of postmodernism, welcome company.
Their rule has also been affirmed by their oncesworn enemy: science. Three major discoveries in the 20th century even took on their names. Albert Einstein's famous Theory (Relativity), Kurt Gödel's famous Theorem (Incompleteness) and Werner Heisenberg's famous Principle (Uncertainty) declared that, henceforth, even science would be postmodern.
Or so it has seemed. But as Rebecca Goldstein points out in her elegant new book, "Incompleteness: The Proof and Paradox of Kurt Gödel" (Atlas Books; Norton), of these three figures, only Heisenberg might have agreed with this characterization.
His uncertainty principle specified the inability to be too exact about small particles. "The idea of an objective real world whose smallest parts exist objectively," he wrote, "is impossible." Oddly, his allegiance to an absolute state, Nazi Germany, remained unquestioned even as his belief in absolute knowledge was quashed.
Einstein and Gödel had precisely the opposite perspective. Both fled the Nazis, both ended up in Princeton, N.J., at the Institute for Advanced Study, and both objected to notions of relativism and incompleteness outside their work. They fled the politically absolute, but believed in its scientific possibility.
And therein lies Ms. Goldstein's tale. From the late 1930's until Einstein's death in 1955, Einstein and Gödel, the physicist and the mathematician, would take long walks, finding companionship in each other's ideas. Late in his life, in fact, Einstein said he would go to his office just to have the "privilege" of walking with Gödel. What was their common ground? In Ms. Goldstein's interpretation, they both felt marginalized, "disaffected and dismissed in profoundly similar ways." Both thought that their work was being invoked to support unacceptable positions.
Einstein's convictions are fairly well known. He objected to quantum physics and its probabilistic clouds. God, he famously asserted, does not play dice. Also, he believed, not everything depends on the perspective of the observer. Relativity doesn't imply relativism.
The conservative beliefs of an aging revolutionary? Perhaps, but Einstein really was a kind of Platonist: He paid tribute to science's liberating ability to understand what he called the "extrapersonal world."
And Gödel? Most lay readers probably know of him from Douglas R. Hofstadter's playful bestseller "Gödel, Escher, Bach," a book that is more about the powers of selfreferentiality than about the limits of knowledge. But the latter is the more standard association. "If you have heard of him," Ms. Goldstein writes, perhaps too cautiously, "then there is a good chance that, through no fault of your own, you associate him with the sorts of ideas  subversively hostile to the enterprises of rationality, objectivity, truth  that he not only vehemently rejected but thought he had conclusively, mathematically, discredited."
Ms. Goldstein's interpretation differs in some respects from that of another recent book about Gödel, "A World Without Time: The Forgotten Legacy of Gödel and Einstein" by Palle Yourgrau (Basic), which sees him as more of an iconoclastic visionary. But in both he is portrayed as someone widely misunderstood, with good reason perhaps, given his work's difficulty.
Before Gödel's incompleteness theorem was published in 1931, it was believed that not only was everything proven by mathematics true, but also that within its conceptual universe everything true could be proven. Mathematics is thus complete: nothing true is beyond its reach. Gödel shattered that dream. He showed that there were true statements in certain mathematical systems that could not be proven. And he did this with astonishing sleight of hand, producing a mathematical assertion that was both true and unprovable.
It is difficult to overstate the impact of his theorem and the possibilities that opened up from Gödel's extraordinary methods, in which he discovered a way for mathematics to talk about itself. (Ms. Goldstein compares it to a painting that could also explain the principles of aesthetics.)
The theorem has generally been understood negatively because it asserts that there are limits to mathematics' powers. It shows that certain formal systems cannot accomplish what their creators hoped.
But what if the theorem is interpreted to reveal something positive: not proving a limitation but disclosing a possibility? Instead of "You can't prove everything," it would say: "This is what can be done: you can discover other kinds of truths. They may be beyond your mathematical formalisms, but they are nevertheless indubitable."
In this, Gödel was elevating the nature of the world, rather than celebrating powers of the mind. There were indeed timeless truths. The mind would discover them not by following the futile methodologies of formal systems, but by taking astonishing leaps, making unusual connections, revealing hidden meanings.
Like Einstein, Gödel was, Ms. Goldstein suggests, a Platonist.
Of course, those leaps and connections could go awry. Gödel was an intermittent paranoiac, whose twisted visions often left his colleagues in dismay. He spent his later years working on a proof of the existence of God. He even died in the grip of a perverse esotericism. He feared eating, imagined elaborate plots, and literally wasted away. At his death in 1978, he weighed 65 pounds.
But he was no postmodernist. Late in his life Gödel said of mathematics: "It is given to us in its entirety and does not change, unlike the Milky Way. That part of it of which we have a perfect view seems beautiful, suggesting harmony." That beauty, he proposed, would be mirrored by the world itself. These are not exactly the views of an acolyte devoted to Relativity, Incompleteness and Uncertainty. And Einstein was his fellow dissenter.
The Connections column will appear every other Monday.
Ping
"Later" ping
Perhaps you'll be more specific about what it is you're calling 'nonsense'?
Completeness is a vital, crucial, essential theoretical attribute that is necessary in the design of algorithms. Without proof of its existence, algorithms are rendered useless.
Goedel's ideas surrounding his proof of the incompleteness of formal reasoning systems are as important if not more important than any philosopher of any age including Einstein.
His philosophy is not antiscience but is rather a view on its limitations inside a particular theory. Theories can be expanded to be more general but they may never capture everything.
Completeness then defines what a theory can ascertain and ensures that it ascertains all that is specified in its scope. To say a theory is complete is to say at once that it is reliable and valid within its ***scope***.
I would think that Goedel's theorem would keep scientists humble, as mentioned in post #6.
Rebecca Goldstein is the author of four novels, including THE MINDBODY PROBLEM, and a collection of short stories, STRANGE ATTRACTORS. Her work has won numerous prizes, including two Whiting Awards. In 1996, she was named a MacArthur Foundation Fellow. She holds a Ph.D. in philosophy from Princeton University, where her work was concentrated in the philosophy of science and was supported by a National Science Foundation fellowship. She resides in Cambridge, Massachusetts.
I'm reasonably certain that you are unfamiliar with Godel's Proof.
There is nothing leftwing or nihilistic in Godel's lucid, brief proof for the incompleteness of any noncontradictory formal system.
It was part of Symbolic Logic II when I was an undergrad.
Nothing communist about Godel.
I can't believe that I have to post this.

js1138's Law: The first to post a negative comment on a science thread hasn't read the article.
Depressing, innit? ;)
Ping
Math threads never get very many pings. They're worth posting from time to time, but you can't expect a whole lot of action.
One function it is impossible to calculate is the interaction (or interference, if you will) upon the observed by the observer. Since you can't predict the latter wouldn't you end up with a model that is unstable over time? Or is it merely a function with infinite solutions (or do they only seem infinite?).Either way, it seem incomplete to me.
No problem.
...Godel's lucid, brief proof for the incompleteness of any noncontradictory formal system...
Two (friendly) comments. First, Gödel's proof was stunning, but not brief (nor was it lucid in the ordinary meaning of that word). Second, the formal system has to be strong enough to express natural number arithmetic with multiplication; systems weaker than that—say, systems that include only the operation of addition—can be proved to be both complete and consistent.
Here's a useful link to an article by R.B. Braithwaite which provides some background and details on Gödel's Incompleteness Theorem:
"On Formally Undecidable Propositions Of Principia Mathematica And Related Systems"
Russel countered with his Theory of Types, but it was thoroughly unsatisfactory and you could tell his heart wasn't in it. That idea essentially ruled out selfreference; that is, metastatements of the order of "this statement is false" were illegal. But in fact there turned out to be no reliable way of deciding where the boundary between statement and metastatement really lay; in fact, there isn't one, as Russell concluded himself.
But that does not invalidate logical systems per se, as the postmodernists fervently believe, it simply dictates that they have boundaries. It does not state that there is no truth or logic, or that all points of view are therefore equally valid, quite the opposite, in fact. It simply states that formal logical systems have limitations. Most adults should be able to live with that.
What Godel showed was twofold: first, that within any formal logical system of sufficient power, a statement could be made that was true but undemonstrable (incompleteness) and second, that a statement could be formulated following that system's rules that could be shown both true and false (incoherence).
Two (friendly) comments. First, it's important to say "undemonstrable within the system" rather than simply "undemonstrable". Second, it's not quite accurate to say that "a statement could be formulated following that system's rules that could be shown both true and false (incoherence)"—if that were true, the system would be inconsistent, which nobody desires. The aim of the constructor of a formal logical system is to rule out the possibility of contradiction, but at the same time to insure the possibility of proving the greatest number of true propositions. What Gödel showed was that if a system has the expressive resources needed to formulate the axioms of natural number arithmetic with multiplication, then it is impossible to prove within the system every true proposition without incurring the penalty of inconsistency, i.e., the ability to 'prove' a contradiction (such as, 1=2). Since no formal system constructor wants an inconsistent system, (s)he's forced to give up the hope of being able to prove every true proposition within that system.
In short, in a 'strong enough' system, the penalty for completeness is inconsistency, and the penalty for consistency is incompleteness.
Of course, by expanding the system to include new axioms, propositions which were previously known to be true but unprovable, become provable. But, again, in the expanded system, new propositions can be formulated which can be known to be true, but turn out to be unprovable within the expanded system. And so on ad infinitum.
One function it is impossible to calculate is the interaction (or interference, if you will) upon the observed by the observer.
Heisenberg's Uncertainty Principle gives one a quantitative grip on the observer's disturbance of the observed. Take your pick:
Do people actually study this stuff anymore?
I think the author over reaches in some areas, which is what most nonmathematicians are wont to do with Gödel.
The implication that Gödel's Theorems suggest that mathematical truths exist which can never be proven at all is stretch. Godel says a particular formal system is unable, based on its axioms, to prove all true statements deriveable in the system. That doesn't mean you can't prove the statement starting with some OTHER set of axioms.
For that matter, how would it make sense to have a truth that can NEVER be proven true (in ANY axiom system)? How, exactly would we know it's "really" true?
In a more practical sense, what's the difference between a Gödel statement and an assertion we just aren't smart enough to prove? Both are unproven, and we don't know why we can't prove it (it might be false, or it might be Gödelian  we just don't know).
My sense of the article is that is just one more example of the postmodern lunatics hijacking technical work and massaging it for their own purposes, which is to cast doubt upon scientific/mathematical epistemology in favor of illdefined, subjective "other ways of knowing" excreta.
One last comment whilst I'm on my rant: Gödel's findings have very serious implications for metamathematicians, but I can't see where it poses any serious problem for ordinary mathematicians: they use theorems they prove to prove other things. Those theorems they CAN'T (or haven't yet) proven, Gödelian or not, never get used in either case, so what difference does it make in terms of the body of truth we've proven? None! What's proven is proven, and Gödel doesn't stand in the way at all.
I was also going to add the requirement, conveniently left out of the article, that the formal system must include the Peano Axioms (or their equivalent) in order that Gödel's Theorem apply, but I see you have elsewhere addressed this issue yourself. Geometry is an example of a mathematical axiom system to which Gödel does not apply.
Thanks for the ping!
Do people actually study this stuff anymore?
You betcha. Here's part of a course description written by Richard Grandy for a philosophy course he taught at Rice University in the Spring of 2003. The course was called "Incompleteness, undecidability and computability" (ahem, my underlining, of course):
The central focus of this course is Godel's Incompleteness Theorem which states that in any consistent formal system which is adequate for arithmetic there is a true but unprovable sentence. Three concepts are involved in the theoremdiagonal arguments, Goedel numbering and algorithms. Diagonal arguments and Goedel numbering coalesce in producing the infamous sentence which "says of itself" that it is unprovable. The concept of an algorithm is crucial in the general statement of the theorem because it applies only to formal systems. A formal system is one for which there is an algorithm to determine what is an axiom and what is a correct application of a rule of inference. Until we understand exactly what an algorithm is, the scope of the theorem is unclear.
A closely related result is Turing's theorem that for any class of algorithms to calculate functions of natural numbers there is a function which is not computable by an algorithm of that class. Church advanced the thesis, Church's thesis, that any computable function is computable by a specifiable class of algorithms. Thus combining these we can describe a function which is absolutely uncomputable.
Following the Snark theory that what you prove three times is true, we will prove Goedel's theorem by at least three different methods. One will be a nonconstructive method, based on Turing's theorem and using a diagonal argument, which shows that some sentence is true and unprovable but gives no clue as to how to find it. Another will be a version of the original argument which painstakingly produces the sentence in question via Goedel numbering. I believe it is important to slog through the details of this construction to truly understand the theorem, though most students only appreciate this experience later.
Goedel also proved a less wellknown Second Incompleteness Theorem, stating that a consistent formal system cannot prove its own consistency. We will explain why someone might have thought that a formal system could have proved its own consistency, and why it turns out it cannot. Having slogged through a detailed proof of the first theorem makes understanding the second theorem almost a snap. The reason it is not quite a snap is that it turns out to be somewhat subtle what it means to prove consistency.
We will also prove a more general form of Goedel's first theorem, after we understand the Kleene Hierarchy. Problems for which there is a decision procedure are the first stage of the hierarchy; problems for which there is either a proof procedure or a refutation procedure (but not both) are the next two stages. There are infinitely many higher stages of undecidability. The generalized Goedel theorem says that even if we had a nonformal system whose axioms were at some stage of this hierarchy, the system would be incomplete! The usual Goedel's theorem is just the simplest case of the general theorem.
Other topics will emerge as we discuss the main themes. We will investigate various definitions of "algorithm" and show that they are equivalent, giving support to Church's Thesis. We will show that there is no algorithm for determining if a sentence is a logical truth (as promised in 305). We will balance precariously exploring the edge of expressibility as we describe noncomputable functions, argue that some sentences are true but unprovable, and describe some sets which are undefinable. All of these verge on effing the ineffable.
We will also spend some time on philosophical implications, or alleged philosophical implications, of the mathematical results. Roger Penrose has advanced arguments, based on Goedel and Turing's results, which he claims show that human capacities exceed those of computers. (His arguments are certainly overstated. He bases his claims on an alleged general human ability to see that the Goedel sentence for a formal system is true. At this point you will be one of a very very few humans who are able to construct the Godel sentence.) We will critically examine his arguments that you can also see that it is true, drawing on our deep understanding of Godel's theorem developed from the earlier exercises. As a result of this course you will either cease to be a computer (if he is right) or you will understand why Penrose's argument is wrong. You will also learn how many Goedel sentences there are and why Godel's theorem is very unlike the Heisenberg principle, to which it is often compared.
As time permits, we will also discuss systems which, in some respect, avoid Godel's theorem, and possibly look at some consistency proofs for number theory in order to understand how those proofs go beyond the deductive power of number theory.
The proof of Gödel's Incompleteness Theorem is so simple, and so sneaky, that it is almost embarassing to relate. His basic procedure is as follows:
 Someone introduces Gödel to a UTM, a machine that is supposed to be a Universal Truth Machine, capable of correctly answering any question at all.
 Gödel asks for the program and the circuit design of the UTM. The program may be complicated, but it can only be finitely long. Call the program P(UTM) for Program of the Universal Truth Machine.
 Smiling a little, Gödel writes out the following sentence: "The machine constructed on the basis of the program P(UTM) will never say that this sentence is true." Call this sentence G for Gödel. Note that G is equivalent to: "UTM will never say G is true."
 Now Gödel laughs his high laugh and asks UTM whether G is true or not.
 If UTM says G is true, then "UTM will never say G is true" is false. If "UTM will never say G is true" is false, then G is false (since G = "UTM will never say G is true"). So if UTM says G is true, then G is in fact false, and UTM has made a false statement. So UTM will never say that G is true, since UTM makes only true statements.
 We have established that UTM will never say G is true. So "UTM will never say G is true" is in fact a true statement. So G is true (since G = "UTM will never say G is true").
 "I know a truth that UTM can never utter," Gödel says. "I know that G is true. UTM is not truly universal."
Yes, in new theoretical mathematical and statistical systems, completeness or incompleteness of the system is one of the first results that is sought after to render a new theory admissible.
For example, in the design of algorithms, completeness and incompleteness of new designs must be established early for the designs to be accepted in the literature.
To see this do a google search of 'completeness algorithm' and you will see hundreds of research results that discuss consistency, satisfiability and so on for proposed algorithms.
Do a google search of 'completeness computer science' and you will see hundreds of research results that discuss soundness and completeness, decidability and so on of computing theories.
Completeness is at the heart of proving valid and reliable computer algorithms or computing theory. Without completeness, algorithms and computation can return nonsensical results and contradictions in their output.
Any algorithm, system of computing, system of search, system of matching, system of conditional and relational database output and so on must be sound, consistent, valid, reliable, and most importantly COMPLETE. Otherwise the system is limited and will not guarantee an answer even though an answer or resolution exists.
However, completeness of a system, if that system is not sufficiently restricted, can lead to that system degenerating. As an easy example, a system that allows division by zero allows one to conclude 1=2, and hence any number equals any other number, a complete breakdown in utility of the system for say purposes of accounting or measurement.
Yes, for an incomplete system one can expand the set of axioms to satisfy completeness but one must keep expanding the set of axioms until the number of axioms is infinite in number.
This is a frequent method used to prove incompleteness of a system, by showing it requires an infinite number of axioms. Start with a finite set of axioms and then show that a new axiom must be generated and added to the set for each new proposition to be proved by the system, and that the number of such axioms can be put in onetoone correspondence with natural counting numbers.
Thanks for the links.
It's hard to believe that this all seemed 'brief and lucid' to me in 1967. ;^)
It's hard to believe that this all seemed 'brief and lucid' to me in 1967. ;^)
Man, don't I know what you mean! (smile)
We will also spend some time on philosophical implications, or alleged philosophical implications, of the mathematical results. Roger Penrose has advanced arguments, based on Goedel and Turing's results, which he claims show that human capacities exceed those of computers. (His arguments are certainly overstated. [snip]
Right. Grandy sounds quite sensible. Probably a fun course to have taken.
Having taken a course very similar to the one Grandy describes, I am leary of taking any course in mathematics taught by the Philosophy Department. It was the worst course I ever took. Perhaps his course is the exception....
Not a mathematician or logician, but my understanding of it is that there are propositions such that it can be proven that there's no way to prove them either that proposition or its negation. Since either a proposition or its negation must be true, there are therefore true statements that are unprovable. That's the difference between such statements and ones for which a proof just hasn't been found yet. The former are fundamentally unprovable and the latter are not necessarily unprovable. I think that also gives us a sense in which we could possibly state that there are true statements that could NEVER be proven true. I'm not saying that Godel actually showed this, but if someone could find a statement such that both that statement and its negation were unprovable in any formal system, then we would know that there's at least one true statement that's unprovable in any formal system. We just wouldn't know whether that true statement is our original proposition or its negation.
Well, fair's fair  every other Department smuggles in unasserted philosophical assumptions into their coursework! ;^)
Grandy's probably an exception. He's a trained logician and a managing editor of the Notre Dame Journal of Formal Logic.
...there are propositions such that it can be proven that there's no way to prove them either that proposition or its negation.
Right, those are 'undecidable' propositions (within a particular formal logical system). Gödel propositions are of that type. Indeed, the title of Gödel's famous incompleteness paper is "On Formally Undecidable Propositions of Principia Mathematica and Related Systems". See post #18 above.
Ugh! Goldstein is a bloody philosophy Ph.D.
Chances are that what she knows about physics and mathematics would comfortably fit in a thimble. ><
And don't even get me started on the mystic spin these kooks try to apply to quantum mechanics.
Sure, we don't know EXACTLY how a particular particle will behave, but uncertainty is measured in a very definite, quantifiable way. Moreover, the laws of quantum mechanics that govern the statistical behavior of objects are precise to any scale on which we wish to test them. They are as hard, absolute and unchanging as the speed of light. Sure, no one can say where a given electron is at a specific moment, but we can tell you pretty much everything about its average position, momentum, velocity, and etc.
The math folks have already thrashed that silliness about Godel's proof.
This book and its accompanying article, are pure 100% unadulterated bunkum!
Snark theory, eh? Where's the Inquisition when you need 'em? ;)
Well, you're right. Maybe not 100% bunkum.
We probably ought to read it first before going that far, but it isn't promising. :P
Heck, I rolled my eyes up when she tried to equate either special or general relativity with "cultural" relativity. What the devil?!
I think (I hope!) that that's the reviewer, Rothstein, putting his spin on things. If not, then that's bad, very bad...
Sorry if I jumped the gun, for some reason the article just pushed my buttons. :)
Have you ever read "Heisenberg's War?" It is a book that makes a case for Heisenberg stopping the Nazi bomb project by sending it down dead end paths until the High Command got fed up and put it on the back burner. I always thought he has gotten a raw deal from history's judgement.
Sorry if I jumped the gun, for some reason the article just pushed my buttons. :)
Understood. We've all had that experience!
Have you ever read "Heisenberg's War?" It is a book that makes a case for Heisenberg stopping the Nazi bomb project by sending it down dead end paths until the High Command got fed up and put it on the back burner. I always thought he has gotten a raw deal from history's judgement.
I need to read that. At the moment, I lean towards the view that Heisenberg shouldn't be completely cleansed of his Nazi connections. Why? Because of Niels Bohr's complete break with Heisenberg after Heisenberg's 1941 visit to Bohr in Nazioccupied Denmark. Bohr was among the most gentle, compassionate and philosophical of men; for him to have broken with his former student and colleague so abruptly and so totally suggests that, at least in Bohr's eyes, Heisenberg was more of a collaborator with the Nazis than he, Heisenberg, wanted to let on after the war.
I'd like to be convinced that I'm wrong about this, but unless more archival material turns up, we may never know what really happened.
Snark theory, eh? Where's the Inquisition when you need 'em? ;)
Savonarola was a punk!
(But when he reached for that redhot poker, folks got real cooperative...)
Yes, Pressberger arithmetic (multiplication by any number but not mulitplication in general) is consistent. Also, Euclidean geometry (and by construction, Riemannian and Bolyai geometries) are consistent.
Note that Principia Mathematica used both "and" and "not" as a complete system. Somehow, Russell and Whitehead missed out on using the Sheffer stroke ("nand") or "nor." Either of these would be more minimal than PM's usage but equally difficult to read. More modern logic books use at least: and, or, not, implies, equivalent, and some add nand and nor.
Note that Principia Mathematica used both "and" and "not" as a complete system. Somehow, Russell and Whitehead missed out on using the Sheffer stroke ("nand") or "nor." Either of these would be more minimal than PM's usage but equally difficult to read. More modern logic books use at least: and, or, not, implies, equivalent, and some add nand and nor.'
Sheffer published his article in 1913, after the first (and, as it turned out, only) three volumes of Principia Mathematica had been published. Somewhere in a box lies my copy of Principia Mathematica to *56, so I can't verify the accuracy of the following statement, but I think it's correct:
This insight [i.e., that propositional logic can be derived using the Sheffer stroke as the sole primitive operation] is discussed in the Introduction to the Second Edition, on pp. xiii to xvi.
BTW, thanks, too, for your post #48.
Disclaimer: Opinions posted on Free Republic are those of the individual posters and do not necessarily represent the opinion of Free Republic or its management. All materials posted herein are protected by copyright law and the exemption for fair use of copyrighted works.