Graduate Seminar Topic - Gödel's Theorems

I took this course because it was required and because I didn't like any of the other courses offered. The easiest way to describe the course is that it's an independent study but with a group of students. Everyone picks their own topic and is required to give four half-hour presentations and write four 10-page papers. The topic I picked was Gödel's incompleteness theorems. A topic from what some people call logic and others call metamathematics. It's a great subject that few math majors even know about. I knew about it from the classic book "Gödel, Escher, Bach : an Eternal Golden Braid" by Douglas Hofstadter which was given to me as a Christmas present when it was first published in 1979. Of course I didn't read it then. Heck I was single and who in their right mind reads a 700+ page technical book?

Now I must pick the main thrust of the rest of this posting. I could: 1) describe my presentations and try to teach you Gödel's results 2) give short reviews of the books that I read for the class 3) describe my experience of the class. The last choice might be amusing since the other students' topics ranged far and wide. Some topics were poorly chosen and equally poorly presented. A couple of the topics were very amusing like the construction of magic squares or the history of computational devices including finger counting to 100,000. I don't think that I can really explain the theorems before you get bored so I'll review my sources for the presentations and the papers.

"Gödel, Escher, Bach" or GEB is certainly a classic. Only a portion is about Gödel's theorems, of course. In general it's hard to say what this book is about because it's about so many different things. Many Escher drawings are reproduced and the text explains their significance in context of recursion, self-reference, and self-replication. Bach's fugues are analyzed in a similar way. And the book amusingly explains basic logic and Gödel's theorems. The author develops some fantastic analogies to give you different ways to understand what's going on. He compares the Gödel sentence to a vinyl record that's specifically designed to break the record player that will play it (nowadays, think of an mp3 file that's designed to break the player that will play it). And he invents amusing, yet deeply philosophical, dialogs between Achilles, the Tortoise, and the Crab. And let's not overlook the theme of Zen Buddhism that runs through the book.

My favorite takeaway from this book is a diagram that Hofstadter devised that explains Gödel's theorems visually. Here it is:

Gödel basically proved that a formal system designed to encompass arithmetic cannot prove all arithmetic truths. There are unreachable truths that are beyond the formal system. That's the left side of the picture. Since the book covers Eastern thought, or at least Zen thinking, he included the opposite of formal arithmetic on the right. In that system you start with negative axioms and prove the negation of theorems. But that side too is incomplete since it has unreachable falsehoods.

So now you do know Gödel's results. I bit the bullet and read the entire book (742 pages) and recommend it to anyone (who really, really likes math, logic, programming, or artificial intelligence).

My primary source was "A Profile of Mathematical Logic" by Harold DeLong. This book is a readable history of logic from the ancient Greeks up through the middle of the 20th century. DeLong gives a good treatment of Gödel's theorems adhering very closely to Gödel's research paper that was published in 1931. I "borrowed" the whole progression for my presentations/papers from this book. The scholarship behind this book is superb as the bibliography is 24 pages long. Highly recommended for the philosophy or math lover.

In 1958 a small paperback entitled "Gödel's Proof" was written by Nagel and Newman. This book is highly readable. If you had to read a book on Gödel this should be the one.

Next is a collection of scholarly papers on metamathematics titled "From Frege to Gödel: A Source Book of Mathematical Logic, 1879 – 1931." This collection includes two of Gödel's most famous papers translated into English. One proves that first order predicate calculus is complete. The other that formal arithmetic is incomplete.

My last source was a brand new book "An Introduction to Gödel's Theorems." This is a serious textbook designed for a one or two semester course leading up to the theorems. It is as much fun to read as a standard logic textbook. In fact I found a number of other books like this that were written for a course taught by the book's author.

About Kurt Gödel

To say that Gödel was a genius is an understatement. The originality of his first incompleteness proof is breathtaking. He has been called the greatest logician since Aristotle. Unfortunately he suffered from paranoia and hypochondria most of his adult life. In his 72nd year he literally starved himself to death fearing that his food was poisoned.

Graduate Course in Number Theory

I just completed my second graduate math course. The subject was number theory which is known as the "queen of mathematics." Before I describe the course I want to briefly mention that last summer I toured the old growth redwood forests in California. When I walked through the redwoods I felt like I was in an enchanted forest. I marveled at the towering sequoias which ranged in age from 1,500 to 300 years old. Each tree is a monument to nature herself and the forest has an eternal quality to it.

I found my number theory course was similar to visiting the ancient forest. We learned theorems from Euclid (e.g. the infinitude of prime numbers) and Diophantus that date back over 2,000 years. We learned venerable theorems from Fermat, Euler, and Gauss that date back over 300 years. Each theorem stands as a pillar of mathematical truth for all eternity.

I have to admit, though, that I was lost in the forest of number theory at times. At certain points I could understand individual theorems and their proofs, but for long stretches I stumbled along. The journey began with chapters on divisibility and congruences. These are straightforward topics that can be taught to bright high school students or the brightest middle school students. Fermat’s Little Theorem and Euler’s generalization were covered. Of course, the totient function f(n) was defined (the count of numbers relatively prime to n) and in a later chapter the remarkable formula was proven. Translated into English this states that the sum of the totient function ranging over all of the divisors of n is equal to n itself (futher translation not available).

Okay they were the easy chapters. Now we move onto quadratic reciprocity and quadratic forms. Our textbook An Introduction to the Theory of Numbers by Niven, Zuckerman, and Montgomery mentions that "Gauss discovered the quadratic reciprocity law just before his 18^th birthday. After a year of strenuous effort he found the first proof, in 1795, at the age of nineteen." I find this fact comforting. The world’s greatest mathematician had to struggle for a year to find a proof for a fact that he knew to be true. So it’s okay to struggle with math homework – that’s its purpose in life.

Binary quadratic forms have the form f(x,y) = ax²+bxy + cy². Mathematicians have studied BQFs intensely and have a complete understanding of them. I can’t say that I have a complete understanding but I did learn a technique based on BQFs that can be used for the following arithmetic parlor trick. Given the prime number 398417 find two numbers whose squares sum to 398417 (answer: 631² + 16²).

For some reason our teacher decided to skip Chapter 4 which has marvelous results like the Moebius inversion formula (don’t ask). So we continue with the chapter on Diophantine equations, the most famous of which is Fermat’s Last Theorem (there are no integer solutions for xⁿ+ yⁿ = zⁿ where n > 2). This leads to an area of mathematics I had never learned before called elliptic curves (these are not elliptical curves). The geometric analysis of these curves (chord and tangent method) yields additional solutions to the Diophantine equation on which they are based. In our class we visit the foothills of the mountains that Andrew Wiles conquered in his 1993 proof of Fermat’s Last Theorem.

We skip chapter 6 to get to the chapter on Continued Fractions. I’m in the embarrassing situation of having to tell people that I’m studying fractions in graduate mathematics, but it’s worth it. These fractions are small wonders and the basis for new insights into irrational numbers. I also learned of Pell’s equation and was able to fully understand an anecdote relating to the Indian mathematician Ramanujan. One of his friend’s gave him a puzzle to determine a house number that met certain conditions. Ramanujan was cooking at the time, but he was able to instantly state the result in general terms using a continued fraction based on Pell’s equation.

For the last two classes our teacher covered eclectic topics in multiplicative number theory. At the very least I learned what Dirichlet’s series are and the Reimann zeta function in particular. Oh to solve the Riemann hypothesis relating to the roots of the zeta function!

Note on textbook: It seems that the textbook by Niven, Zuckerman andMontgomery is widely used as a graduate text. It has survived the test of time having endured five editions since 1961. My belief is that it was a fit text in its early editions, but by the fifth edition it has grown flaccid and overweight. The authors give the most succinct proofs and even skip steps at times.

If I felt stultified by the topics at hand, the authors helped me achieve that state.