PHI 220: Logic and the Undecidable

Another name for the logic in this course is ``metamathematics,'' or the mathematics of mathematics. Logic attempts to study mathematics itself.

It begins by examining the language of mathematics: $\vee$ (``or''), $\Rightarrow$ (``implies''), $\exists$ (``there exists''), $\forall$ (``for all''), and so on. It is not at first clear what good this will do. If we are interested in the theorems and results of mathematics, then it seems a little foolish to look at the symbols we use to express those facts. Isn't that like analyzing the paper on which the theorems are written?

In fact, this approach, which starts so humbly, leads to what is probably the most profound theorem of the century. This is the ``Incompleteness Theorem'' of Kurt Gödel, which he proved in 1931. The theorem has excited and challenged philosophy. It has inspired art. It thrills and haunts mathematics.

To understand this theorem, think for a moment about what we mathematicians do. If we are given a problem, we try to solve it. The problem may be of the form: is such and such true? If we think that it is true, we try to prove it. If we do not succeed, then we try to disprove it. If we do not succeed at this either, then we say it must be a hard problem, and we hope that someone else will solve it while we are still alive to enjoy its solution.

Gödel's theorem has changed this. The incompleteness theorem says that there are mathematical statements that can neither be proved nor disproved. There are such statements about subjects as simple as arithmetic. There are such statements that we know (in some sense) are true--yet which cannot be proved!

What does this say about truth? What does this say about mathematics? What does this say about the power and the limitations of the human mind?