Friendly Introduction to Mathematical Logic (Leary & Kristiansen)

At the intersection of mathematics, computer science, and philosophy, mathematical logic examines the power and limitations of formal mathematical thinking. In this expansion of Leary’s user-friendly 1st edition, readers with no previous study in the field are introduced to the basics of model theory, proof theory, and computability theory. The text is designed to be used either in an upper division undergraduate classroom, or for self study. Updating the 1st Edition’s treatment of languages, structures, and deductions, leading to rigorous proofs of Gödel’s First and Second Incompleteness Theorems, the expanded 2nd Edition includes a new introduction to incompleteness through computability as well as solutions to selected exercises.

Summing Up, Looking Ahead

What we have tried to do in this first chapter is to introduce the concepts of formal languages and formal structures. We hope that you will agree that you have seen many mathematical structures in the past, even though you may not have called them structures at the time. By formalizing what we mean when we say that a formula is true in a structure, we will be able to tie together truth and provability in the next couple of chapters.

You might be at a point where you are about to throw your hands up in disgust and say, “Why does any of this matter? I’ve been doing mathematics for over ten years without worrying about structures or assignment functions, and I have been able to solve problems and succeed as a mathematician so far.” Allow us to assure you that the effort and the almost unreasonable precision that we are imposing on our exposition will have a payoff in later chapters. The major theorems that we wish to prove are theorems about the existence or nonexistence of certain objects. To prove that you cannot express a certain idea in a certain language, we have to know, with an amazing amount of exactitude, what a language is and what structures are. Our goals are some theorems that are easy to state incorrectly, so by being precise about what we are saying, we will be able to make (and prove) claims that are truly revolutionary.

Since we will be talking about the existence and nonexistence of proofs, we now must turn our attention to defining (yes, precisely) what sorts of things qualify as proofs. That is the topic of the next chapter.

Languages

We will be constructing a very restricted formal language, and our goal in constructing that language will be to be able to form certain statements about certain kinds of mathematical structures. For our work, it will be necessary to be able to talk about constants, functions, and relations, and so we will need symbols to represent them.