Author
|
Topic: Kurt Gödel--Separating Truth from Proof in Mathematics (Read 1039 times) |
|
the.bricoleur
Archon
Posts: 341
Reputation: 8.44
Rate the.bricoleur
making sense of change
 
 
|
 |
Kurt Gödel--Separating Truth from Proof in Mathematics
« on: 2002-12-06 04:56:28 » |
 |
I suppose this could just have easily gone into the Philosophy forum...
Portraits of science:
Kurt Gödel--Separating Truth from Proof in Mathematics
Keith Devlin
FULL ARTICLE HERE - Science
In 1931, a young Austrian mathematician published a paper that sent shock waves through the mathematical community and forced mathematicians to take a fresh look at their discipline. The mathematician was Kurt Gödel, and the result proved in his paper became known as the Gödel Incompleteness Theorem, or more simply Gödel's Theorem--although it was by no means the only major theorem he proved during his highly successful career. He is also known as one of the inventors of the theory of recursive functions (which formed part of the foundation for computers).
Gödel was born on 28 April 1906, in what was then Brünn in Austria, now Brno in the Czech Republic. By all accounts he was an outstanding pupil in high school and a star student at the University of Vienna, where he continued after graduation to obtain a doctoral degree in 1929. He went straight to a faculty position in Vienna, and it was there that he proved his Incompleteness Theorem. Gödel remained in Vienna until 1940, when he fled the worsening Nazi atrocities to take up a position at the Institute for Advanced Study in Princeton, which he had already visited in 1934. He remained at Princeton until his death on 14 January 1978. It was an unlikely death for the man who was arguably the world's foremost expert in logic. A hypochondriac for much of his adult life, as he grew older, Gödel became convinced that he was being poisoned. He eventually stopped eating altogether, and starved to death.
Gödel's decidedly illogical end did nothing to diminish his reputation. When Time magazine conducted a poll 2 years ago to determine the most influential thinkers of the 20th century, Gödel was one of just two mathematicians who made the top 20, along with Alan Turing.
The Incompleteness Theorem forced mathematicians to question what it means to say something is true in mathematics. The resulting change in our understanding of mathematics was every bit as dramatic as the change in our conception of geometry that followed the discovery of non-Euclidean geometries in the 19th century.
Both of these major discoveries involved axiomatic systems, and neither can be properly understood without an appreciation of what mathematicians means by the word "axiom" and the role axioms play in mathematics. A misunderstanding of the nature of axioms is what lies behind a significant amount of nonsense that has been written about Gödel's Theorem over the years.
In brief, Gödel's Theorem says that in any axiomatic mathematical system that is sufficiently rich to do elementary arithmetic, there will be some statements that are true but cannot be proved (from the axioms). In technical terminology, the axiom system must be incomplete.
-----
Bricoleur.
|
|
|
|
|
Walter Watts
Archon
Gender: 
Posts: 1571
Reputation: 8.89
Rate Walter Watts
Just when I thought I was out-they pull me back in
|
|
Re:Kurt Gödel--Separating Truth from Proof in Mathematics
« Reply #1 on: 2002-12-07 11:39:02 » |
|
The Epimenides Paradox
Consider Statement A.
Statement A: "Statement A is not true."
Is Statement A true?
Statement A is not true. Argument 1 explains why.
Argument 1: SUPPOSE Statement A is true. Then the proposition that Statement A states is true. But Statement A states that Statement A is not true. So, Statement A is not true, contrary to our initial supposition. So, IN FACT, Statement A is not true.
Unfortunately, Statement A can't be not true either.
Argument 2:
2.1 SUPPOSE Statement A is not true.
2.2. Then the proposition that Statement A states is not true.
2.3 But Statement A states that Statement A is not true.
2.4 So Statement A is not not true, contrary to our initial supposition.
2.5 So, IN FACT, Statement A is not not true.
Your mind should be blown. You should not be saying, "That's puzzling." You should be saying, "My mind is exploding."
Argument 1 proves that Statement A is not true. Argument 2 proves that Statement A is not not true. We have proved a contradiction, which is impossible.
A fundamental principle of logic is the Law of the Excluded Middle, which states that every statement is either true, or not true, and never both. It is just a straightforward consequence of the definition of the word "not." For any well-defined characteristic (say, "onchyness"), and for any thing (say, "Ralph") , if Ralph is not onchy, then...Ralph is not onchy!
However important you think this paradox is, it is more important. If contradictions are possible, then anything's possible.
So how can we resolve the paradox?
Inadmissible Statements
One approach is never to utter or think Statement A or statements like it. Then we never have to worry about the paradox.
It's easy to avoid Statement A, but how do we know what statements are similar enough to Statement A to cause a problem? Strategy Alpha will keep us safe.
Strategy Alpha: Never make any statement that refers to a statement.
That rules out Statement Alpha and other statements liable to cause the same problem.
Unfortunately, Strategy Alpha rules out many useful and harmless statements. For example: Statement B: Two plus two is five. Statement C: Statement B is not true. According to Strategy Alpha, Statement C is inadmissible--we can't say Statement B is false. So Strategy Alpha is too stringent.
Statement A not only refers to a statement, it refers to itself, Statement A. Perhaps the root problem is this self reference.
Strategy Beta: Never make a statement that refers to itself.
Strategy Beta does rule out Statement A, but it suffers from the opposite problem to Strategy Alpha: it's too weak to prevent the paradox.
Statement D: Statement E is not true. Statement E: Statement D is true.
Statement D can't be true. Argument 3: SUPPOSE that Statement D is true. Then Statement E is not true. Then Statement D is not true--which contradicts our original supposition. So, IN FACT, Statement D is not true.
But Statement D can't be not true. Argument 4: SUPPOSE that Statement D is not true. Then Statement E is true. Then Statement D is true--which contradicts our original supposition. So, IN FACT, Statement D is not not true.
Again we face paradox. Hofstadter illustrates this version of the paradox with Escher's drawing of two hands drawing each other.
Preventing a statement from referring to any other statement is too strong. Preventing a statement from referring to itself is too weak--if we only prevent it from directly referring to itself. We need to rule out indirect self reference as well.
Strategy Gamma: Don't make any statement that refers to any statement that...that refers to any statement that refers to the original statement.
That'll do it.
But there are still two problems with Strategy Gamma.
1.To implement Strategy Gamma we have to keep careful track of all our statements to make sure that there are no chains of self reference. That vigilance could be irksome for any lengthy argument; but, if we ignore Strategy Gamma, we can't be sure we won't be led into contradiction.
2.Strategy Gamma only avoids the Epimenides Paradox. It is an emergency stopgap. What we ultimately want is to resolve the paradox. The Epimenides Paradox appears to prove that contradictions are possible, or that the Law of the Excluded Middle is false. But if that's true, then we can never be sure that avoiding the Paradox is enough to avoid paradox; all our arguments are suspect.
How can we resolve the paradox?
Meaninglessness,
or, "It depends what your definition of is is."
Statement F: Statement F is true.
Statement F doesn't lead us into any paradoxes. Supposing it's true only confirms that it's true. Supposing that it's not true only confirms that it's not true. But we still have the problem of decidng which it is--is Statement F true or not true?
It seems that there's no way to tell. How can that be? What extra information could possibly turn up that would help us to decide?! Since Statement F is only about Statement F, and we know Statement F, it seems we should be able to decide, right now and for sure, whether or not it's true. F is for Fishy.
Perhaps Statement F is meaningless: it doesn't express any proposition at all. Perhaps Statement A is meaningless. Perhaps that's the resolution of the paradox--Statement A is neither true nor not true, just meaningless.
To accomodate this possibility, from now on let's consider not "Statements" but "Sentences".
Sentence A: Sentence A is not true.
Unfortunately, it is not proper to say that Sentence A is neither true nor not true, but meaningless.
Sentence G: Zebras are white.
You might think Sentence G is both true and not true. Argument 5: Zebras are partially white; therefore Sentence G is true. Zebras are only partially white; therefore Sentence G is not true. Therefore, Sentence G is both true and not true.
We seem to have violated the Law of the Excluded Middle again.
Similarly, you might think that Sentence G is neither true nor not true. It's not true, because zebras are only partially white; it's not not true, because zebras are partially white.
Nevertheless, Sentence G does not pose a contradiction. The Law of the Excluded Middle says that Ralph is either onchy or not onchy; but it applies only if onchyness is well defined.
Sentence H: That suit is smart.
Argument 6: The suit looks good; therefore Sentence H is true. The suit does not have a high IQ; therefore Sentence H is not true. Therefore, Sentence H is both true and not true.
Argument 6 doesn't overturn the Law of the Excluded Middle, since it uses two different meanings for the word "smart". If we specify that "smart" means "good-looking", then Sentence H is just true. If we specify that "smart" means "intelligent", then Sentence H is just not true.
Similarly, but more subtly, the seeming contradiction in Argument 5 stems from a shift in the definition of "white". If we define "white" to mean "completely white" (ignore the circularity, you know what I mean) then Sentence G is just not true. If we define "white" to mean "partially white" then Sentence G is just true. As long as we stick to a single definition, we don't face any contradiction.
Similarly, but more subtly, when we deal with Sentence A we must be careful about our definition of the word "true".
Sentence I: Green virtue swims under fastness.
Is Sentence I true or not true?
Definition i: "True" means "expressing a correct proposition".
According to Definition i, Sentence I is not true, since, being meaningless, it doesn't express any proposition at all.
Definition ii: "True" means "not expressing an incorrect proposition".
According to Definition ii, Sentence I is true, since it doesn't express an incorrect proposition, since it doesn't express any proposition at all.
Even though Sentence I is meaningless, we can still determine whether or not it's true, so long as we define carefully what we mean by "true".
Let us adopt Definition i, which seems more natural.
Recall that, in our attempt to resolve the Epimenides Paradox, we supposed that Sentence A is neither true nor not true, because it is meaningless. With Definition i in hand, however, we can see that "meaninglessness" is not a distinct third possibility. Rather, meaninglessness is a form of untruth.
If Sentence A is meaningless, then, using Definition i, Sentence A is not true. But we have seen that supposing that Sentence A is not true implies, via Argument 2, that Sentence A is not not true. Thus, our attempt to use meaninglessness to resolve our dilemma fails. The paradox lives.
Or does it?
Meaninglessness, Mark II
Let us from now on adopt Definition i of "true".
And suppose that Sentence A is meaningless.
Then Sentence A is not true.
Earlier, we saw in Argument 2 that supposing that Sentence A is not true implies that Sentence A is not not true, enveloping us in contradiction.
Argument 2 seems ironclad, but in fact it is flawed, as we can see now that we recognize the possibility of meaninglessness.
The flaw is step 2:
2.2 Then the proposition that Sentence A states is not true.
If Sentence A is meaningless, then Sentence A doesn't state any proposition at all--it's just a string of words. Therefore 2.2 doesn't hold, therefore Argument 2 doesn't hold, and therefore no contradiction arises.
To summarize.
1.Sentence A is meaningless.
2.Therefore, Sentence A is not true.
3.And Argument 2, which attempts to prove that Sentence A is also not not true, fails: Argument 2 refers to the proposition which is expressed by Sentence A, but Sentence A doesn't express any propositions.
Indeed, we can now prove that Sentence A is
1.not true, and
2.meaningless.
Argument 7:
7.1 Sentence A is either not true or not not true, but not both. (Law of the Excluded Middle)
7.2 Sentence A is not true. (By Argument 1. Do you see why Argument 1 still holds even though Argument 2 does not?)
7.3 If Sentence A is meaningful, then Sentence A is not not true (by Argument
2)--contradicting 7.2.
7.4 Therefore, Sentence A is meaningless.
Thus, we have resolved the Epimenides Paradox.
Or have we? In fact, meaninglessness embroils us in even worse confusion than before! See why?
Meaninglessness: Ugh
There are two problems with the meaninglessness approach.
First: Sentence A is weird, but it doesn't seem meaningless. It has a clear subject, a sentence. And it has a clear predicate adjective, untruth. And we know that truthfulness is just the kind of thing that we ordinarily talk about when we talk about sentences. So we have an independent argument that Sentence A is perfectly meaningful.
I merely mention this first problem, because the second problem is decisive anyway.
Namely: We have decided that Sentence A is meaingless and not true. I.e., we have concluded i. Sentence A is a meaningless sentence. ii. Sentence A is not true. We think that i and ii are both true. But expand i: i'. "Sentence A is not true" is a meaningless sentence.
Return to Argument 7, which we had hoped had settled this whole matter; reexamine 7.2. Behold! It's Sentence A! But how can an argument employ a sentence that that same argument proves is meaningless!? It can't.
So what do we do now?
|
Walter Watts
Tulsa Network Solutions, Inc.
No one gets to see the Wizard! Not nobody! Not no how!
|
|
|
rhinoceros
Archon
Gender:
Posts: 1318
Reputation: 8.39
Rate rhinoceros
My point is ...
|
|
Re:Kurt Gödel--Separating Truth from Proof in Mathematics
« Reply #2 on: 2003-01-20 07:31:27 » |
|
[rhinoceros]
Gödel's Theorem is very important for anyone interested in the nature of scientific knowledge and truth, but it has been improperly used in too many inappropriate contexts to "prove" various assertions. It is important to understand what is really proven by the theorem and what is just an assertion.
Gödel's proof was essentially based on a mathematical formulation of the "Liar Paradox" which Walter analyzed.
Here are some important excerpts from the Science article.
<quote from the article>
At the time Gödel proved this theorem, it was widely believed that, with sufficient effort, mathematicians would eventually be able to formulate axioms to support all of mathematics. The Incompleteness Theorem flew in the face of this expectation, and many took it to imply that there is a limit to the mathematical knowledge we may acquire. Few mathematicians think that way now, however. The change in our conception of mathematical truth that Godel's theorem brought about was so complete, that today most of us view the result itself as merely a technical observation about the limitations of axiom systems.
<end quote>
[rhinoceros]
Here is a description of "Hilbert's program", a Positivist attempt at formalizing all mathematics in an axiomatic way:
<quote from article>
Following his work on the axioms for geometry, Hilbert put forward a view of mathematics that was to gain considerable acceptance. According to this view, which became known as formalism, mathematics should be regarded as being, at heart, nothing other than a collection of formal games, each one played according to completely specified rules.
To do Euclidean geometry, for instance, was to play the Euclidean geometry game. In that game, you start with the axioms for Euclidean geometry and then deduce all the truths of Euclidean geometry by means of mechanistic manipulations of symbols according to totally specified rules. Nothing could be used that was not specified by the axioms or the manipulation rules. In particular, no intuition about the nature of points or lines could or should be used. As Hilbert himself remarked, you could replace all talk about points and lines by reference to beer mugs and bar tables, provided you formulated the axioms in terms of those objects, and the resulting theory would be identical in all respects except for the actual words being used.
By removing all intuitions so that points and lines are no different from beer mugs and bar tables, the reasoning went, mathematics would be forever free from the dangers of unrecognized and possibly misleading assumptions. It would, in principle, be possible to design mechanical devices--which, of course, have no intuitions--to follow the rules and deduce all the truths for you. (This, remember, was before computers were invented.)
This approach to mathematics, to formulate all the axioms you need to deduce all the truths in a particular branch of mathematics mechanistically, became known as the Hilbert Program. For many, the search for axioms became something of a Holy Grail, although Hilbert, who had great respect for the role played by human intuition in the practice of mathematics, was not one of them, and never himself proposed that the program to which others attached his name should be carried out.
One of the most sustained efforts to carry out the Hilbert Program was made by the English philosophers Bertrand Russell and Alfred North Whitehead. Their mammoth, three-volume work, Principia Mathematica, published from 1910 to 1913, was an attempt to develop basic arithmetic and logical reasoning itself from axioms.
<end quote>
[rhinoceros]
Here is what Gödel did:
<quote from article>
It was the axiom system in Principia Mathematica that Gödel took, by way of an exemplar, to demonstrate beyond any doubt that the goal of the Hilbert Program was unattainable. He called his dramatic paper "On formal undecidable statements of Principia Mathematica and related systems." At the time that Gödel proved it, the Incompleteness Theorem gained a reputation of being difficult to follow. But that has long ago given way to a realization that it is really a rather simple result. The complexities of Gödel's original proof are largely irrelevant, a consequence of the particular way he presented the argument. In essence, Gödel took the familiar Liar Paradox and showed how to reproduce it within any axiom system that supported arithmetic.
The Liar Paradox, which goes back to ancient Greece, arises when a person stands up and says "I am lying." If the person is lying, then the statement is true, so they are not lying; and if they are not lying, the statement is false, so they are lying. This is a seemingly inescapable paradox. Gödel took a similar statement, "This statement is not provable," and showed how it could be formulated as a mathematical formula within arithmetic.
This required, first of all, coding statements as numbers--a process known as Gödel numbering. At the time, this was regarded as a deep and difficult step, but today any number of spy movies have depicted the way in which English words and sentences can be encoded as sequences of numbers, often as part of the process of encrypting messages. Gödel's next step was to show how the concept of provability could be captured within arithmetic. This was a somewhat deeper move, but to today's mathematicians it too seems fairly routine.
Once the coding had been completed, the noose was tight. If one assumed that the axiom systems were consistent (that is, they did not lead to any internal contradictions), the statement clearly could not be provable (since it declared its own unprovability). Hence it was true--but unprovable.
<end quote>
[rhinoceros]
And this is what Gödel's Theorem implies:
<quote from article>
To those mathematicians (the formalists) who believed that mathematical truth was the same as provability--that the true statements of mathematics are precisely the ones you can prove from the axioms once you have formulated them all properly--Gödel's theorem was devastating. Today, however, as I remarked earlier, mathematicians regard it simply as confirming the limitations of what can be achieved with axiom systems.
But they are able to do so only because contemporary mathematics has learned the lesson that Gödel's Theorem taught us. Gödel's result may not have changed mathematics very much. But it changed the way we view it. His selection as one of the most influential thinkers of the 20th century is undoubtedly well deserved.
<end quote>
|
|
|
|
|
|
Logged
