Once I read couple of easy books, I get an innate craving to do some penance. Perhaps in that mood, I was browsing the math section of the local library where I came across "Incompleteness: The Proof and Paradox of Kurt Gödel" by Rebecca Goldstein. Had to pick it up. :-)
David Hilbert is a venerable German mathematician of last century. As one of the early God Fathers of modern mathematics, Hilbert first proposed a set of problems (called Hilbert's Problems) to the math community that got the ball rolling. These 23 most influential unsolved problems he listed at the International Congress of Mathematicians in Paris in 1900 is widely recognized as an exemplary compilation of open problems put together by an individual.
In 1920 with the gravitas of an elderly statesman he proposed a research project (in metamathematics, as it was then termed) that became known as Hilbert's program. It set out a commendable goal for the field of mathematics as a whole saying any dependency on intuition or appeal to intuition to prove theorems in math should be gotten rid of. One can easily understand how elegant and noble this goal is to seek a complete and consistent set of axioms using which everything in mathematics can be built/proven. People including Hilbert were working on these ideas for a while, when Kurt Gödel, a very quiet, reclusive, reticent, introverted mathematical logician enters the picture and rigorously proves two theorems named after him.
Gödel's First Incompleteness Theorem: For every consistent arithmetic system, there is always an arithmetic statement that is clearly true but can not be proven within that system.
You can think of Liar's paradox that says "This sentence is False" as the English language example. Gödel went around constructing fiendishly clever Gödel numbering (naturally he wasn't the one who named it thus) and used it to say something like this:
G, an arithmetic proposition, is unprovable in the system.
The negation of G amounts to the proposition:
G is provable in the system.
Now if G is indeed provable, then the negation is true. But whenver a negation of a proposition is true, that implies original proposition is false. But if we examine the original proposition, that also means it is true. So, if G is provable then it is both true and false, which will again mean it is not provable. Gödel effectively showed that G becomes both unprovable and true. This proof blows up Hilbert's second problem in the 23 problem list.
Gödel's Second Incompleteness Theorem: Consistency of a formal system that contains arithmetic can't be formally proved within that system.
This sounds like a corollary to the first one. Still it is important to note that he is not saying it can't be proven in any system but only within that system, as long as it is consistent. In effect, Gödel showed that within any mathematically consistent system, there will always be true theorem that will remain unprovable within the system! This simply destroys Hilbert's idea of getting rid of appeals to intuitions to prove mathematical theorems en-mass. Even after understanding and accepting the Incompleteness theorem, Hilbert kept working on his program, which apparently upset Gödel. In the discussions she touches upon Entscheidungsproblem, Diagonal_lemma and other ComSci grad school material that took me back to the 90's. :-)
While all this may sound like arcane Theory of Computation class material, the reach of Gödel's Incompleteness Theorem has been remarkable. It has been analyzed and understood from say religious point of view to discuss if the presence of God can be proven within the system in which we exist. In another very interesting take, it is used to argue that computers which are equivalent to consistent mathematical universes will always have blind spots that human minds won't (since human minds are not necessarily consistent) and so there are fundamental differences between human mind and computers that will always prevent computers from becoming an artificial equivalent of natural human mind! Gödel was very well known for extremely precise writing as well as verbal communication. For all the impact he had in the world, the total pages of his published material is less than 100 pages, that also includes seminal results related to Theory of Relativity that proved time travel is logically and physically possible! He apparently had a ton of material written down but held them back for one reason or another (such as work is not complete, it will not be received well, etc.).
As a personality he was extremely odd, germaphobe, hypochondriac who was a mere 65lbs when he died due to self inflicted starvation since he was worried about food poisoning. He was very close to Einstein during his decades in the Institute for Advanced Studies in Princeton, New Jersey. Einstein, who was much more gregarious in nature, was very caring and supportive of his younger colleague. One amusing note is related to the time when Gödel went to take his US citizenship test. He prepared very seriously for the test studying the US Constitution thoroughly and in the process found logical loopholes in the language used in the document! A gentleman who was Gödel's sponsor taking him to the test was quite worried that he will start pointing out all the flaws in the constitution to the US immigration officer administering the test and so asked Einstein to accompany Gödel to the test center distracting him on the way so that he doesn't get stuck on showing the holes in the constitution to the officer! Einstein obliged and kept talking about all kinds of issues on their way without letting Gödel delve into the consitution related discussion. When they reached the office, the immigration officer, who was apparently the same one that administered the US citizenship oath to Einstein, tried to engage in exchange of pleasantries. When he asked if Gödel is happy to be away from Hitler's Germany (Gödel was originally from Austria) to live in US that is devoid of such tyrents, Gödel promptly started explaining as to how US can land in a similar situation due to logical flaws in the US constitution! The worried officer stopped him saying it is ok not to delve into that much detail, gave him the test and passed him. Later Gödel wrote to his own mother in Europe saying the immigration office seemed to be a kind soul. :-)
Gödel was weirdly oblivious to most things going on in the world. Though he was Arian by descent, he looked like a Jew and worked with a lot of Jewish colleagues. But never said anything about Nazi atrocities and didn't even understand how some of his Jewish colleagues landed in USA to escape Nazi persecution! He was devastated when Einstein died as he didn't notice the deterioration in Einstein's health (who also tried to hide it from Gödel). He felt all alone in the world without any companion to talk to, was puzzled if anyone paid him a courtesy visit, insisted his own colleagues speak to him via telephone even if they are next door and avoided traveling anywhere and stayed within Princeton, NJ. Author keeps the focus on the Imcompleteness Theorem and proof while touching upon Gödel's family, Konisburg, family, Wiener Kreis (Vienna Circle, which is a prestigious association of Positivist philosophers, that Gödel attended as a student though he is an ardent Platonist), Bertrund Russell, Wittgenstein, von Neumann and other such personalities/items just enough to give the complete picture. Nostalgia inducing & Enjoyable.
If you don't think you will read this book, you can listen to this University of Sydney lecture which is less than an hour long and covers the wonders of Godel's work very well (i.e. better than Goldstein's lectures you may find online). In case if you weren't before, now you are prepped to enjoy joke number 13 in this list of "20 jokes for geeks". :-)
-sundar.
No comments:
Post a Comment