Gödel's Incompleteness Theorem
From SkepticWiki
Contents |
[edit] The Incompleteness Theorem
- For any formal theory in which basic arithmetical facts are provable, it is possible to construct an arithmetical statement which, if the theory is consistent, is true but not provable or refutable in the theory.
Or more informally,
- In any consistent formal system, there are true statements that can neither be proven true, nor false.
And even more succinctly,
- A formal system is either incomplete, or inconsistent.
[edit] Gödel's Second Theorem
- If a formal system can prove its own completeness, then it is inconsistent.
[edit] History
The Incompleteness Theorem was proven by Kurt Gödel in 1931. According to legend, Von Neumann, who heard the lecture in which it was announced, quickly realized the "second" Theorem as a corollary. Gödel had already found the second result independently. It basically demolished hope for David Hilbert’s “Program” to prove the completeness and consistency of the existing mathematical systems. Particularly, the “Principia Mathematica”, a massive attempt by Russell and Whitehead to axiomatize mathematics was shown to be essentially incomplete. The most famous known “unprovable” mathematical proposition may be Cantor’s “Continuum Hypothesis”.
[edit] Proof Outline
The proof of the Incompleteness Theorem follows from the construction of a Gödel sentence for the formal system. That sentence, interpreted at a meta-logical level, asserts that
- This statement cannot be proven in the formal system.
If the statement can be proven in the formal system, then it is false, and hence a false statement was proven, and the system therefore inconsistent. On the other hand, if the statement cannot be proven, then it is true, and it serves as an example of a true statement that cannot be proven. The system is therefore incomplete.
Gödel showed that any system which can represent integer arithmetic can express the Gödel sentence. There are three main parts to this demonstration:
- If a system can represent integers, then it can represent mathematical statements
- Provability in a such a formal system can be represented in that system,
- It is possible for an expression to describe its own construction, which is interpreted as the “This statement” phrase.
One interesting idea is to create an augmented formal system with this Gödel sentence added as an axiom. (The formal system referred to in the Gödel sentence is still the original system, so the new system is not necessarily inconsistent). For this new system, another Gödel sentence can be constructed, showing that the new system is likewise either inconsistent or incomplete.
[edit] Implications for Materialism
The functioning of certain types of physical machines, (such as modern computers) can be modeled by formal systems of logic. As a consequence, there are certain facts concerning these machines which are true, yet unprovable. Gödel’s theorem has a parallel in Computer Science, known as the Halting Theorem, due to Alan Turing.
Additionally, physical machines have the limitations exposed by the Incompleteness Theorem. It remains an open question whether the physical universe can be modeled as a formal logical system, or a great computing machine. If it can, then the limitations of the Incompleteness Theorem are inherent limitations of the physical universe.
[edit] Controversial Interpretations
To the layman, the rendition of “Not all truths can be proven” captures the spirit of of the Incompleteness Theorem, at least within the realm of formal systems. Extended to logic in general, this sentiment appeals to the romantic side of the philosopher, especially one that regards mathematics and logic as cold and uninspiring.
Inevitably then, the Incompleteness Theorem has been cited as the basis for a rejection of logic as a path to knowledge. It should be pointed out that while the Theorem demonstrates the limits of mathematics and logic, these tools still offer some truth, and so have much to offer by continued pursuit.
The fact that we can show that the Gödel sentence is true, yet the formal system cannot, seems to point to the ascendancy of the human mind over formal logic, and by extension, the superiority of intelligence over the machine. One objection to this is that technically, we have no way of knowing that the Gödel sentence is true; this fact depends on the consistency of the system.
The capabilities of the human mind are still the matter of much debate, and it is unclear whether or not they can be modeled by a formal system. The idea that minds can be modeled by a formal system is known as the Church-Turing Hypothesis.
The opposite view, that human minds transcend the capabilities of formal systems is advocated by J.R. Lucas in his book Minds, Machines, and Gödel(1961). Both sides are addressed and criticized by Douglas Hofstadter in Gödel, Escher, Bach, an eternal Golden Braid(1979).
Whatever the capabilities of the human mind, they should yet be subject to their own Gödel sentence. For example, “Lucas cannot believe this sentence” is true, yet Lucas cannot believe it, therefore his own mind is incomplete with respect to the truth. However, anyone else may see that it is true, therefore, by Lucas's own argument, anyone else’s mind is superior to Lucas's.
There is a great tendency among the romantic-minded to associate the “unprovable truths” suggested by the Incompleteness Theorem with such concepts as Beauty, Love, God, etc. However, the Theorem speaks only about the limitations of formal logical systems, which are not currently used to model such concepts.
There are claims that ancient Zen and Taoist masters were aware of Gödel’s result long before it was proven. Naturally, this depends on the degree of similarity one is able to find in the supposed correspondence between the traditional teachings and modern metamathematical concepts.
[edit] Discussion
Gödel's Theorems have roots in a classic logical paradox attributed to Epimenides of Crete, who lived in the 6th Century BCE. His statement was:
- "All Cretans are liars"
While this is not a paradox in a technical sense, a typical paraphrase is:
- This statement is false.
Which is apparently neither true nor false, hence the paradox. This statement lies outside the realm of "true-and-false statements" in the same way that the Gödel sentence lies outside the realm of "decideable statements".
Since formal systems are not necessarily able to express "This statement" directly, we can make a statement indirectly refer to itself as
- The statement "The statement a, when substituted for the variable in itself, is false.", when substituted for the variable in itself, is false.
Formal systems representing integer arithmetic are not necessarily capable of expressing the idea of "truth". However, they can represent "provability". Thus we can write
- The statement "The statement a, when substituted for the variable in itself, is not provable.", when substituted for the variable in itself, is not provable.
which is equivalent to the Gödel sentence. Note that there is a lot of hand-waving in this overview: the notions of "provable", "substitution", "statement", etc., must all be defined in terms of simpler constructs in a formal system.
[edit] External Links
[edit] Further Reading
- A popular, but very roundabout introduction, which also touches on similarities to Buddhist philosophy: Hofstadter, Douglas; Gödel, Escher, Bach, an Eternal Golden Braid (1979); ISBN 0394756827
- A classic introduction with a minimum of prerequisite math knowledge: Ernest Nagel and James R. Newman; Gödel's Proof (1958, 1986); ISBN 0814703259
- An introduction to mathematical logic text that includes the deep details of proving Gödel's incompleteness theorems: Elliott Mendelson; Introduction to Mathematical Logic, Fifth Edition (2010); ISBN 9781584888765
- A controversial interpretation of the Theorem, relating consciousness to quantum mechanics: Penrose, Roger; The Emperor’s New Mind (1989); ISBN 0140145346
