Mathematical Logic

Stephen Cole Kleene

• Publisher: Dover Publications
• Year: 2013
• ISBN:
  9780486317076
• Topic: Mathematics
• Subtopic: Logic in Mathematics
• Index: Mathematics

Undergraduate students with no prior classroom instruction in mathematical logic will benefit from this evenhanded multipart text. It begins with an elementary but thorough overview of mathematical logic of first order. The treatment extends beyond a single method of formulating logic to offer instruction in a variety of techniques: model theory (truth tables), Hilbert-type proof theory, and proof theory handled through derived rules.
The second part supplements the previously discussed material and introduces some of the newer ideas and the more profound results of twentieth-century logical research. Subsequent chapters explore the study of formal number theory, with surveys of the famous incompleteness and undecidability results of Godel, Church, Turing, and others. The emphasis in the final chapter reverts to logic, with examinations of Godel's completeness theorem, Gentzen's theorem, Skolem's paradox and nonstandard models of arithmetic, and other theorems. The author, Stephen Cole Kleene, was Cyrus C. MacDuffee Professor of Mathematics at the University of Wisconsin, Madison. Preface. Bibliography. Theorem and Lemma Numbers: Pages. List of Postulates. Symbols and Notations. Index.

Mathematical
Logic

PART I
ELEMENTARY MATHEMATICAL LOGIC

CHAPTER I

THE PROPOSITIONAL CALCULUS

§ 1. Linguistic considerations: formulas. Mathematical logic (also called symbolic logic) is logic treated by mathematical methods. But our title has a double meaning, since we shall be studying the logic that is used in mathematics.

Logic has the important function of saying what follows from what. Every development of mathematics makes use of logic. A familiar example is the presentation of geometry in Euclid’s “Elements” (c. 330-320 B.C.), in which theorems are deduced by logic from axioms (or postulates). But any orderly arrangement of the content of mathematics would exhibit logical connections. Similarly, logic is used in organizing scientific knowledge, and as a tool of reasoning and argumentation in daily life.

Now we are proposing to study logic, and indeed by mathematical methods. Here we are confronted by a bit of a paradox. For, how can we treat logic mathematically (or in any systematic way) without using logic in the treatment?

The solution of this paradox is simple, though it will take some time before we can appreciate fully how it works. We simply put the logic that we are studying into one compartment, and the logic that we are using to study it in another. Instead of “compartments”, we can speak of “languages”. When we are studying logic, the logic we are studying will pertain to one language, which we call the object language, because this language (including its logic) is an object of our study. Our study of this language and its logic, including our use of logic in carrying out the study, we regard as taking place in another language, which we call the observer’s language.¹ Or we may speak of the object logic and the observer’s logic.

It will be very important as we proceed to keep in mind this distinction between the logic we are studying (the object logic) and our use of logic in studying it (the observer’s logic). To any student who is not ready to do so, we suggest that he close the book now, and pick some other subject instead, such as acrostics or beekeeping.

All of logic, like all of physics or all of history, constitutes a very rich and varied discipline. We follow the usual strategy for approaching such disciplines, by picking a small and manageable portion to treat first, after which we can extend our treatment to include some more.

The portion of logic we study first deals with connections between propositions which depend only on how some propositions are constructed out of other propositions that are employed intact, as building blocks, in the construction. This part of logic is called propositional logic or the propositional calculus.

We deal with propositions ...