By Noel Weichbrodt
In this paper, I examine the death of the modernist dream in mathematics (and by extension in logic and in computer science) of creating an axiomatic formal system, such as math or logic, capable of delivering every truth possible in that system. I will also take a look at what has happened in mathematics and logic since Gödel delivered his knockout blow to the modernist dream, as well as give an idea of the main figures in mathematics and logic in the last century. Along the way, I will try to note the various ways mathematics and logic are shifting from a modernist philosophy of science to a postmodernist philosophy of science.
It is a well known claim that the mathematics project (along with physics) was being wrapped in the late 1800s by the likes of Georg Cantor, Bertrand Russell, and Lord Whitehead. Cantors project was to reconstruct all of mathematics into set theory, an abstract, axiomatic formal system that made it possible for all of math to be justified from its own starting axioms.1 Russell attempted the same thing with Whitehead in their Principia Mathematica. All that remained was a few problems with infinite numbers in set theory, and mathematics would be a complete, formal, axiomatic system that, in the words of David Hilbert, could be checked for errors by a mechanical error-checker.2 This system called mathematics was so precise and complete that there were no unknowns, no uncertainties left in the mathematical world. It was black and white. Hilbert would give a lecture in the last decade of the nineteenth century that detailed what he saw as the 23 remaining problems in mathematics to be solved in the new century. Every mathematical problem, it seemed, would have a solution that would be found just around times corner.3 Mathematics was so perfect that it had become the only absolute, beautiful thing in the world. Herman von Neumann, who later on was to become influential in computer science, said that math had become their [the mathematicians] religion.4
What I am attempting to get across with all this is that mathematics at the turn of the century was the culmination of a dream. Here, at the end of the nineteenth century, after two hundred years of dramatic work, was something scientific, empirical, certain, objective, true, and beautiful. They had found what Descartes called divinely implanted truths in mathematics using the light of reason alone. Humanity had supplanted a divine Person with a divine System. This divine System, a universal that was true no matter where in the world you were, no matter what your views about things was, showed an objective correspondence between knowledge and science. Mathematics, as the divine System, was autonomous of the knower, but once it was known its inherent harmony and beauty could be seen by all. Mathematics = Truth, as proved by Reason. Mathematics was complete and consistent .5
All this is now a little naive. There is no foundation for truth within any developed system, because any developed system can be coaxed to talk about itself, self referentially. To see what I mean by self reference, consider the statement This statement is false.6 Here, the developed system is English, and the self reference is in the the statement calling into question its own truthfulness. What the crafty Austrian Kurt Gödel did was coax mathematics in his mind-blowing 1931 paper On Formally Undecidable Propositions of Principia Mathematica and Related Systems to make the same statement as I just made. 7
Gödel did not stumble blindly onto this idol-slayer of a theorem on his own, a truth Derrida et al would be glad to tell you. Kurts work was based on a conjecture by Hilbert, paradoxes discovered by Russell, and methods found by Cantor. Remember Hilberts 23 Problems? Well, problems 6 and 10 were picked up by Gödel as challenges.8 Gödel also picked up on Russells paradoxes, such as Consider the set of all sets. Is there a bigger set? And Cantors diagonal slash method provided Gödel with a way to make a mathematical statement refer to itself.9 Gödel proved, in elementary number theory under a modified formal axiomatic system put forth by Russell and Whitehead, that mathematics was either incomplete or inconsistent.10
Chaitin summarizes the result of Gödels findings as this. So there are two possibilities. Either its provable or its unprovable Well, if its provable, and it says its unprovable, were proving something thats false. And if its unprovable and it says its unprovable, what it states is true, and and we have a hole. Instead of proving something false, we have incompleteness a true statement that our formalization has not succeeded in capturing.11
What Gödel did cannot be underestimated. The Modernist hope in mathematics was dashed on realitys rocks by Gödel. Penrose calls Gödels incompleteness theorem the most fundamental contribution to mathematics ever found. Gödel established that no formal system can find all the true principles in the system.12 Chaitin notes that von Neumann, Hilbert, and other mathematicians were in a terrible state of shock at Gödels theorem. The divine System has be ruined, and now I want to kill myself.13 Hofstadter says Gödel showed that metamathematics (philosophy of mathematics) could be imported into mathematics14 and that Gödels theorem, like Zen, attempts to break the mind of logic with paradoxes.15
That I would mention Zen at this point should show how far from the the primarily white, European, male, Deist Enlightenment dream Gödel and his obscure theorem have brought us. The new generation of mathematicians is struggling to find out exactly where their discipline now fits, since its place as objective arbiter of truth has been displaced. The philosophical underpinnings of mathematics and logic do not move easily, and once uprooted take a while to find new foundations. And math, like most other disciplines affected by post modernity, has splintered into several camps, each working out their meaning independent of each other and of a metanarrative.
Hofstadter stands in one of those camps. He takes Gödels theorem and finds the path for creating the first self-aware machines. At the core of Gödels theorem are two ideas, he says. One is introspection or self-awareness where a formal system can speak about itself. The other is that a single string/theorem in a formal system can speak about itself.16 Because these formal systems can be coaxed into self-awareness, cannot we also create machines that can be coaxed into self-awareness?
Since we are in the postmodern age, Penrose can claim the exact opposite thing using the same proof. He says [Gödel appears to show that] no system of rules can ever be sufficient to prove even those propositions of arithmetic whose truth is accessible in principle, to human insight and intutionwhence human intuition and insight cannot be reduced to any set of rules.17 So Gödels theorem shows that self-awareness cannot be reproduced by any mechanical system, but instead depends on the complexities and unknowables in the human mind to begin.
In a third camp is Chaitin, who is finding that randomness and unpredictability are found at the heart of mathematics, computer science, physics, and any other formal system.18 God, to rephrase Einstein, does play dice with the universe. Incompleteness is a symptom of underlying randomness in the structure of mathematics. There are cases where mathematical truths have no structure at all where its completely accidental.19 He is exploring the implications of this underlying randomness in his Algorithmic Information Theory, with interesting results for computer science.20
In a final camp are most mathematicians. They shake their heads at the crazy messes that metamathematicians have gotten themselves into, and simply continue to do their work like Gödel had never been born and Russell and Whitehead were still working it all out for them in Principia Mathematica. They say it doesnt apply to the problems I care about, and thereby deny like any good postmodern the parts of the metanarrative that they do not like.21
In summary, I have taken you through three distinct phases. First, we examined the Enlightenment hope found in Hilbert, Cantor, and Russell in mathematics as the ultimate guardian of science. Then, we looked at Gödel and his revolutionary theorem, and the knockout blow it delivered to the Enlightenment hope. Last, four differing camps in modern mathematics were discussed, and a diversity of reactions to Gödels work was found. Where will mathematics find its moorings? Will metamathematics ever regain its footing after Gödel? I think we will find out in another century!
1 Chaitin, Gregory A Random Walk in Arithmetic. New Scientist 125, No. 1709 (24 March 1990), p. 44-46.
2 I, and Chaitin, find it amusing that this wildly wrong idea nevertheless resulted in the biggest revolution of the twentieth century: the general purpose computer. The general purpose computers genesis was as Hilberts mechanical error checkera job impossible for it to do!
4 Chaitin, Gregory A Century of Controversy Over the Foundations of Mathematics. Lecture at Carnegie Mellon Universtiy School of Computer Science, 2 March 2000. Edited transcript available at http://www.cs.auckland.ac.nz/CDMTCS/chaitin .
5 Douglas Hofstadter, Gödel, Escher, Bach. Basic Books, 1979. p. 101. He defines completeness as all statements which are true and can be expressed as well formed strings of mathematics are theorems of mathematics. Consistency is defined as every theorem coming out true upon interpretation.
6 This is the well known Liars Paradox, taken from a transcript of Chaitins Paradoxes of Randomness Summer Adventure Seminar Series Lecture given 8 August 2001 at the IBM Watson Research Center. Transcript available at his site, noted above. An closer equivalent English statement to what Gödel did would be This statement is unprovable.
7 A nicely formatted HTML version of this paper, which includes Braithwaites introduction, is available at http://www.ddc.net/ygg/etext/godel .
8 Chaitin, A Random Walk. #6: establish the fundamental axioms of physics. #10: Are diophantine equations solvable? Is there a way of deciding whether or not an algebraic equation has a solution in whole numbers?
9 Hofstadter summarizes Cantors diagonal slash as showing that there exists in an infinite list r(N) a set d that is not in r(N) by arranging r(1), r(2) r(n) in rows and taking one number from each row in a diagonal fashion.
10 For a neat two page reiteration of Gödels theorem, see Roger Penrose Shadows of the Mind, Oxford University Press, 1994, p. 74-75.
11 Chaitin, A Century of Controversy Over the Foundation of Mathematics. p. 9.
12 Penrose, p. 65.
13 Chaitin, A Century of Controversy Over the Foundation of Mathematics. p. 10.
14 Hofstadter, p. P-5.
15 Ibid, p. 246.
16 Hofstadter, p. 438.
17 Penrose, p. 65.
18 Chaitin, A Random Walk, p. 4.
19 Chaitin, A Century of Controversy Over the Foundation of Mathematics. p. 21.
20 Gregory Chaitin, Algorithmic Information Theory. Cambridge University Press, 1987.
java source for an adventure game that takes place at and around Lookout Mountain. Features special appearances by the Pit of Despair, the Slough of Despondency, the Handy Andy, and Rock City.
see more code