Monday, January 14, 2008

Kurt Gödel: an anniversary

Background and countries

Kurt Gödel (4/28/1906) died in Princeton 30 years ago, on 1/14/1978. He was born in Brno, Moravia, Austria-Hungary to a family of a textile industry manager and automatically became a Czechoslovak citizen in 1918 when the monarchy split apart. At that time, Brno had a slight German-speaking majority - today the percentage is around 1% or so.

Talented in languages but speaking almost no Czech, he felt like an exiled Austrian in Czechoslovakia. Let's admit that various ethnic groups had worse feelings and not only feelings in Greater Germany in the course of the history. At the age of 23, he chose to become an Austrian citizen. Nine years later, when Hitler annexed Austria, he became a German citizen. After the war, as a founding member of the IAS, he became a U.S. citizen.

Schools and research of completeness

At the age of 18, he entered University of Vienna, intending to study theoretical physics. He also attended (and thought about) courses on mathematics and philosophy and a lecture by David Hilbert in Bologna transformed Gödel into a full-fledged logician. His PhD thesis defended in 1930 proved Gödel's completeness theorem i.e. the provability of all true assertions in first-order logic.

One year later, he proved his more famous theorem, namely Gödel's incompleteness theorem. Every consistent axiomatic system that is strong enough to include arithmetics of positive integers allows the existence of true statements that can't be proven (first theorem). And the consistency can't be proven either (second theorem).

The unprovable statement from the first theorem is a technically encoded statement saying that "I am unprovable within the system". It can't be false because if it were false, it would be provable (because it says it is unprovable). And provable assertions would have to be true. Being true and false at the same moment would cause inconsistency, in contradiction with the assumed consistency.

So the statement is true but unprovable within the axiomatic system. The only reason why I could have proved that the statement was true is that I used physicists' logic that is more powerful than any system of axioms of a narrow-minded mathematician. ;-)
See: Dangerous Knowledge (+), a 10-minute BBC document about Kurt Gödel. If you like it, try the whole 90-minute documentary including many more mathematicians.
I can also sketch the proof of the second theorem. Why cannot the consistency itself be proved in the system? Because it turns out that one can also translate the statement of the first theorem itself, "there exists an unprovable true assertion in the system", into the language of the given axiomatic system: one can formalize it. In this context, let us call the assertion of the first theorem "p". Above, I've explained that "p assuming the consistency" was not provable in the system, just by extended meta-tools. But the proof of "p" itself can be formalized, as a tedious analysis of the methods of the first theorem shows, and demonstrated as equivalent to "p is unprovable". In other words, "consistency implies that p is unprovable" is provable. But because "p is unprovable" is not provable, it follows that it must be the consistency that is unprovable. ;-)

Philosophical impact

This ended dreams that many of us have had at some point in our lives that one can design completely rigorous axioms for all of mathematics where all statements may be either proved or disproved. In the college, people would be telling us that these results have had far-reaching consequences for philosophy. Of course, I thought that theoretical physics has had much more dramatic consequences for philosophy than logic can ever dream of. But I must confess that as I studied these results due to Gödel in detail, I had to admit they were damn interesting and surprising.

Incidentally, I used to attend courses by Prof Petr Vopěnka (pic) in Prague (it was in this mathematicians' building on the Lesser Town Square, directly connected to the famous church). He was quite a character among the teachers. In the Czech context, he was a relatively achieved set theorist. He was also a former post-Velvet-Revolution minister of education - a source of many stories he told us - and probably the first Czech politician who advocated the dissolution of Czechoslovakia.

America and algorithms

In 1933, Gödel first visited the U.S. and met Albert Einstein who became his friend. Many decades before the official birth of the discipline, he studied algorithmic complexity and NP completeness, as his letters sent to John von Neumann recently emphasized.

He also worked out the consistency of the axiom of choice (it is possible to choose a set that contains exactly one element from each set from an infinite collection of non-empty sets) and the continuum hypothesis of Georg Cantor (there is no set with more elements than the integers and less elements than the continuum) and their unprovability within the conventional systems of set theory axioms.

Axiom of choice vs nice Lebesgue measures

Yes, they are actually unprovable from the other axioms. While most mathematicians prefer to believe that they are true, there also exist pretty good reasons to declare them false. For example, you can't prove that there exist sets without measure in measure theory without the axiom of choice.

I dare to say that I would find it "prettier" to have an axiom that every set of real numbers is measurable than to have the axiom of choice. Choosing representatives from an infinite collection of sets without any rule is unphysical and you can very well say that it is impossible because you won't ever need such an infinite election process in practice. On the other hand, it is physically attractive not to have pathological unmeasurable sets of real numbers.

The very notion that it is up to you whether these axioms are true or not is kind of revolutionary. Who would have thought that these seemingly objective questions about the Platonic world of mathematical structures - such as "Is the axiom of choice true?" - depend on your preferences!

In 1940, Gödel began to use the power of "models" - collections of easy-to-imagine, constructible sets where the validity or invalidity of various axioms may be seen - to further investigate the consistency and independency of various axioms.

Existence of God

In the 1970s, the last decade of his life, he proved the existence of God - He who has all positive properties - using the template of St Anselm and especially Gottfried von Leibniz. The proof is wrong because of the uncertainty principle, among other reasons. Gödel assumes that a union of positive properties is positive, too.

However, it's not the case. If God has a well-defined location, it's good because He is oh so sharp. If He has a sharp momentum, it's also good because He has oh so clear direction. But if He has both, then He is an idiot who misunderstands quantum mechanics which is bad. ;-)

Closed time-like curves

Gödel studied paradoxes outside mathematical logic, too. He learned general relativity and constructed solutions for rotating universes that would allow time travel, something that made Einstein doubt his own theory. Gödel's rotating universes embedded in string theory are T-dual and therefore equivalent to Penrose's pp-waves.

Kurt Gödel has suffered from poisonining paranoia throughout his life. He would only eat if his wife Adele tasted the food for him. Exactly 30 years ago, she was absent for a while and he starved to death. He was 30 kilograms when he died.

1 comment:

  1. A few points:

    1. Gödel only proved the consistency with ZF of the AC and the CH (in fact, the GCH). The independence was shown by Paul Cohen in the 60s.

    2. While the incompleteness theorem is more famous, the completeness theorem is by far the more important: paraphrased, it is the statement that insisting on proofs make sense. Formally, it says that if your axioms imply a conclusion (in the sense that whenever the axioms hood, so does the conclusion) then there is a finite proof of this fact. Without this, the insistence on proofs would not make sense, and we might as well be physicists.