A Friendly Introduction to Mathematical Logic

Structures and Languages

Let us set the stage. In the middle of the nineteenth century, questions concerning the foundations of mathematics began to appear. Motivated by developments in geometry and in calculus, and pushed forward by results in set theory, mathematicians and logicians tried to create a system of axioms for mathematics, in particular, arithmetic. As systems were pro- posed, notably by the German mathematician Gottlob Frege, errors and paradoxes were discovered. So other systems were advanced.

At the International Congress of Mathematicians, a meeting held in Paris in 1900, David Hilbert proposed a list of 23 problems that the mathematical community should attempt to solve in the upcoming century. In stating the second of his problems, Hilbert said:

But above all I wish to designate the following as the most important among the numerous questions which can be asked with regard to the axioms [of arithmetic]: To prove that they are not contradictory, that is, that a finite number of logical steps based upon them can never lead to contradictory results. (Quoted in [Feferman 98])

In other words, Hilbert challenged mathematicians to come up with a set of axioms for arithmetic that were guaranteed to be consistent, guaranteed to be paradox-free.

In the first two decades of the twentieth century, three major schools of mathematical philosophy developed. The Platonists held that mathematical objects had an existence independent of human thought, and thus the job of mathematicians was to discover the truths about these mathematical objects. Intuitionists, led by the Dutch mathematician L. E. J. Brouwer, held that mathematics should be restricted to concrete operations performed on finite structures. Since vast areas of modern mathematics depended on using infinitary methods, Brouwer’s position implied that most of the mathematics of the previous 3000 years should be discarded until the results could be reproved using finitistic arguments. Hilbert was appalled at this suggestion and he became the leading exponent of the Formalist school, which held that mathematics was nothing more than the manipulation of meaningless symbols according to certain rules and that the consistency of such a system was nothing more than saying that the rules prohibited certain combinations of the symbols from occurring.

Hilbert developed a plan to refute the Intuitionist position that most of mathematics was suspect. He proposed to prove, using finite methods that the Intuitionists would accept, that all of classical mathematics was consistent. By using finite methods in his consistency proof, Hilbert was sure that his proof would be accepted by Brouwer and his followers, and then the mathematical community would be able to return to what Hilbert considered the more important work of advancing mathematical knowledge. In the 1920s many mathematicians became actively involved in Hilbert’s project, and there were several partial results that seemed to indicate that Hilbert’s plan could be accomplished. Then came the shock.

On Sunday, September 7, 1930, at the Conference on Epistemology of the Exact Sciences held in Königsberg, Germany, a 24-year-old Austrian mathematician named Kurt Gödel announced that he could show that there is a sentence such that the sentence is true but not provable in a formal system of classical mathematics. In 1931 Gödel published the proof of this claim along with the proof of his Second Incompleteness Theorem, which said that no consistent formal system of mathematics could prove its own consistency. Thus Hilbert’s program was impossible, and there would be no finitistic proof that the axioms of arithmetic were consistent.

Mathematics, which had reigned for centuries as the embodiment of certainty, had lost that role. Thus we find ourselves in a situation where we cannot prove that mathematics is consistent. Although we believe in our hearts that mathematics is consistent, we know in our brains that we will not be able to prove that fact, unless we are wrong. For if we are wrong, mathematics is inconsistent. And (as we will see) if mathematics is inconsistent, then it can prove anything, including the statement which says that mathematics is consistent.

So do we throw our hands in the air and give up the study of mathematics? Of course not! Mathematics is still useful, it is still beautiful, and it is still interesting. It is an intellectual challenge. It compels us to think about great ideas and difficult problems. It is a wonderful field of study, with rewards for us all. What we have learned from the developments of the nineteenth and twentieth centuries is that we must temper our hubris. Although we can still agree with Gauss, who said that, “Mathematics is the Queen of the Sciences. . . ” she no longer can claim to be a product of an immaculate conception.

Our study of mathematical logic will take us to a point where we can understand the statement and the proof of Gödel’s Incompleteness Theorems. On our way there, we will study formal languages, mathematical structures, and a certain deductive system. The type of thinking, the type of mathematics that we will do, may be unfamiliar to you, and it will probably be tough going at times. But the theorems that we will prove are among the most revolutionary mathematical results of the twentieth century. So your efforts will be well rewarded. Work hard. Have fun.