Stephen Cole Kleene - Mathematical Logic

Mathematical
Logic

Stephen Cole Kleene

DOVER PUBLICATIONS, INC.
Mineola, New York

Mathematical
Logic

Copyright

Copyright 1967 by Stephen Cole Kleene

All rights reserved.

Bibliographical Note

This Dover edition, first published in 2002, is an unabridged republication of the work originally published in 1967 by John Wiley & Sons, Inc., New York.

Library of Congress Cataloging-in-Publication Data

Kleene, Stephen Cole, 1909

Mathematical logic / Stephen Cole Kleene.

p. cm.

Originally published: New York : Wiley, 1967.

Includes bibliographical references and index.

ISBN 0-486-42533-9 (pbk.)

1. MathematicsPhilosophy. 2. Logic, Symbolic and mathematical.

I. Title.

QA9.A1 K54 2002

511.3dc21

2002034823

Manufactured in the United States of America

Dover Publications, Inc., 31 East 2nd Street, Mineola, NY. 11501

To Nancy

PREFACE

After the appearance in 1952 of my Introduction to Metamathematics, written for students at the first-year graduate level, I had no expectation of writing another text. But various occasions arose which required me to think about how to present parts of the same material more briefly, to a more general audience, or to students at an earlier educational level. These newer expositions were received well enough that I was persuaded to prepare the present book for undergraduate students in the Junior year.

In Introduction to Metamathematics, the study of mathematical logic begins properly only in ). Graduate students in mathematics can cover rapidly the introductory material which precedes it there. But for less advanced students or in shorter courses, too much time would be used by such a thorough introduction. I am now convinced that it is also sound pedagogically and scientifically to start doing logic (correctly) right from the beginning, even if not all the reasons for doing it nor all the criteria governing how it is done have been enumerated in advance. The rest of the "introduction" can come later.

On this basis, , a Gentzen-type sequent system will be introduced, as a fourth formulation of logic.)

.

Specifically, surveys the famous incompleteness and undecidability results of Godel, Church and others, using the Turing machine concept, without always giving detailed proofs. (Thus an overview is provided of some of the principal results of IM 42 and Part III, without the detailed theory developed there.) These two chapters concern the foundations of mathematics more than pure logic.

In the emphasis reverts to logic. GodePs completeness theorem and Gentzen's theorem (besides theorems of Lowenheim, Skolem, Herbrand, Henkin, Beth, Craig and A. Robinson) are obtained, using an approach which has been in the literature only since 1955. There are more compact treatments of Godel's completeness theorem. The one used here is thought to have the merit, for an introduction to the subject, that almost from the very beginning it should both be clear in what direction one is going and plausible that with patience in managing details one can thus reach the goal. Besides, this approach gives Gentzen's theorem quickly, though nonconstructively. (This chapter corresponds to Part IV of IM, but there are considerable differences in the approach and selection of topics.)

will have to be omitted.)

A fair number of exercises is supplied; but especially in they do not illustrate all the topics. A course taught from this book is not intended to be primarily a problem course. The student should be disabused of the idea Freshman calculus students often have that the text is of no importance except as it helps him to do the exercises. Mastering definitions is especially important to a proper understanding of the enterprise.

I am grateful to H. William Oliver and Edward Pols for taking the notes on my lectures at NSF Summer Institutes at Williams in 1956 and Bowdoin in 1961, respectively. The 1956 lectures and notes were reworked

PREFACE ix in 1961, and the latter have been reworked and very much expanded in this book. Among the added subjects are ones suggested by H. Jerome Keisler, Georg Kreisel and Julius R. Weinberg. Keisler also suggested improvements, and supplied some eight exercises, after teaching from a draft of the book. Weinberg, William W. Boone, Burton Dreben and Jean van Heijenoort helped with some references. Particularly, the last two persons are my source for a more accurate assessment of the contributions of Lowenheim, Skolem and Herbrand than has hitherto prevailed in the literature. Finally, I thank William E. Ritter for reading the printer's proof independently of myself, and for suggesting improvements made in proof.

S. C. Kleene

Madison, Wisconsin

October, 1966

Cf. the last five items under my name in the bibliography (pp. 378-379).

CONTENTS

PART II. MATHEMATICAL LOGIC
AND THE FOUNDATIONS OF MATHEMATICS

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 Euclids 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 observers language. Or we may speak of the object logic and the observers 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 observers 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 through declarative sentences which express them is some language (the object language); the propositions are the meanings of the sentences. Declarative sentences express propositions (while interrogatory sentences ask questions and imperative sentences express commands). The same proposition may be expressed by different (declarative) sentences. Thus John loves Jane and Jane is loved by John express the same proposition, but John loves Mary expresses a different proposition. Under the usual definition of > from <, the two sentences 5 < 3 and 3 > 5 express the same proposition (which happens to be false), namely that increasing 5 by a suitable positive quantity will give 3; but 52 42 = 10 expresses a different proposition (also false). Each of 5 < 3, 3 > 5 and 52 42 = 10 asserts something about the outcome of a mathematical process, which is the same process in the first two cases, but a different one in the third. 3 2 = 1 and (481 581) + 101 = 1 express two different propositions (both true).