About this title A Mathematical Introduction to Logic, Second Edition, offers increased flexibility with topic coverage, allowing for choice in how to utilize the textbook in a course. It is intended for the reader who has not studied logic previously, but who has some experience in mathematical reasoning. Material is presented on computer science issues such as computational complexity and database queries, with additional coverage of introductory material such as sets. From the Back Cover: About this book An accessible, flexible introduction to the subject of mathematical logic, the second edition of this popular and widely-adopted text has been revised to be appropriate for courses enrolling either advanced undergraduates or graduate students. Like the First Edition, this book is an introduction to the concepts of proof, truth, and computability.
|Published (Last):||28 August 2017|
|PDF File Size:||12.38 Mb|
|ePub File Size:||1.97 Mb|
|Price:||Free* [*Free Regsitration Required]|
As before, the presentation is directed toward the reader with some mathematical background and interests. In the main development, I have tried not to take for granted information or insights that might be unavailable to a junior-level mathematics student. Footnotes at the beginning of many of the sections indicate optional paths the instructor — or the independent reader — might choose to take. Issues of computability are taken more seriously.
The book is intended to serve as a textbook for an introductory mathematics course in logic at the junior-senior level. As a text, the book can be used in courses anywhere from a quarter to a year in length. The extra time afforded by a semester would permit some glimpse of undecidability, as in Section 3. In a second ix x Preface term, the material of Chapter 3 on undecidability can be more adequately covered.
The book is intended for the reader who has not studied logic previously, but who has some experience in mathematical reasoning. There is the inevitable use of basic set theory. Chapter 0 gives a concise summary of the set theory used. One should not begin the book by studying this chapter; it is instead intended for reference if and when the need arises. The instructor can adjust the amount of set theory employed; for example it is possible to avoid cardinal numbers completely at the cost of losing some theorems.
The book contains some examples drawn from abstract algebra. But they are just examples, and are not essential to the exposition. The later chapters Chapter 3 and 4 tend to be more demanding of the reader than are the earlier chapters. Induction and recursion are given a more extensive discussion in Section 1.
I prefer to give an informal account of these subjects in lectures and have a precise version in the book rather than to have the situation reversed. Exercises are given at the end of nearly all the sections. If the exercise bears a boldface numeral, then the results of that exercise are used in the exposition in the text. Unusually challenging exercises are marked with an asterisk. I cheerfully acknowledge my debt to my teachers, a category in which I include also those who have been my colleagues or students.
I would be pleased to receive comments and corrections from the users of this book. Introduction S ymbolic logic is a mathematical model of deductive thought. Or at least that was true originally; as with other branches of mathematics it has grown beyond the circumstances of its birth. Symbolic logic is a model in much the same way that modern probability theory is a model for situations involving chance and uncertainty.
How are models constructed? You begin with a real-life object, for example an airplane. Then you select some features of this original object to be represented in the model, for example its shape, and others to be ignored, for example its size.
And then you build an object that is like the original in some ways which you call essential and unlike it in others which you call irrelevant. Whether or not the resulting model meets its intended purpose will depend largely on the selection of the properties of the original object to be represented in the model. Logic is more abstract than airplanes. For example, All men are mortal. Socrates is a man. Therefore, Socrates is mortal.
Borogoves are mimsy whenever it is brillig. It is now brillig, and this thing is a borogove. Hence this thing is mimsy. Logically correct deductions are of more interest than the above frivolous examples might suggest.
In fact, axiomatic mathematics consists of many such deductions laid end to end. These deductions made by the working mathematician constitute real-life originals whose features are to be mirrored in our model. The logical correctness of these deductions is due to their form but is independent of their content. This criterion is vague, but it is just this sort of vagueness that prompts us to turn to mathematical models.
A major goal will be to give, within a model, a precise version of this criterion. The questions about our model we will initially be most concerned with are these: 1. If a sentence does follow logically from certain others, what methods of proof might be necessary to establish this fact?
Is there a gap between what we can prove in an axiomatic system say for the natural numbers and what is true about the natural numbers? What is the connection between logic and computability? Actually we will present two models. Its inadequacy stems from the fact that it preserves only some crude properties of real-life deductions. When a working mathematician asserts that a particular sentence follows from the axioms of set theory, he or she means that this deduction can be translated to one in our model.
This emphasis on mathematics has guided the choice of topics to include. This book does not venture into many-valued logic, modal logic, or intuitionistic logic, which represent different selections of properties of real-life deductions. As brief hints, we now give some examples of the expressiveness of its formal language.
We have given some hints as to what we intend to do in this book. We should also correct some possible misimpressions by saying what we are not going to do. This book does not propose to teach the reader how to think. The reader already knows how to think. Here are some intriguing concepts to think about. Chapter Useful Facts about Sets W e assume that the reader already has some familiarity with normal everyday set-theoretic apparatus.
Nonetheless, we give here a brief summary of facts from set theory we will need; this will at least serve to establish the notation. It is suggested that the reader, instead of poring over this chapter at the outset, simply refer to it if and when issues of a set-theoretic nature arise in later chapters. First a word about jargon. Throughout the book we will utilize an assortment of standard mathematical abbreviations. For example, in Section 1. Now then, a set is a collection of things, called its members or elements.
This holds simply because A and B are the same thing. A useful operation is that of adjoining one extra object to a set. For a set A, let A; t be the set whose members are i the members of A, plus ii the possibly new member t.
Any other set is said to be nonempty. We have only used different expressions to denote the set. If order matters, we can use ordered pairs discussed later. We will take considerable liberty with this notation. Sets A and B are disjoint iff their intersection is empty i. A collection of sets is pairwise disjoint iff any two members of the collection are disjoint.
More generally, consider a set A whose members are themselves sets. If x1 ,. The proof uses induction on n and the basic property of ordered pairs. But if x1 ,. After all, every ordered triple is also an ordered pair. We use induction on m. For the inductive step, assume that x1 ,. Now apply the inductive hypothesis. Then if x1 ,. An is the set of all n-tuples of members of A. A relation R is a set of ordered pairs. But a 1-ary unary relation on A is simply a subset of A.
As usual, this unique y is said to be the value F x that F assumes at x. This notation goes back to Euler. This notation is extended to n-tuples; F x1 ,. An n-ary operation on A is a function mapping An into A.
If f is an n-ary operation on A, then the restriction of f to a subset B of A is the function g with domain B n which agrees with f at each point of B n. This g will be an n-ary operation on B iff B is closed under f , in the sense that f b1 ,.
For example, the addition operation on N, which contains such triples as 3, 2 , 5 , is the restriction to N of the addition operation on R, which contains many more triples. The equivalence classes then partition A. That is, the equivalence classes are subsets of A such that each member of A belongs to exactly one equivalence class.
A set A is countable iff there is some function mapping A one-to-one into N. The basic idea is to map S one-to-one into N by assigning to a0 , a1 ,.
For conceivably there could be a0 , a1 ,.
A Mathematical Introduction to Logic, 2nd Edition
As before, the presentation is directed toward the reader with some mathematical background and interests. In the main development, I have tried not to take for granted information or insights that might be unavailable to a junior-level mathematics student. Footnotes at the beginning of many of the sections indicate optional paths the instructor — or the independent reader — might choose to take. Issues of computability are taken more seriously. The book is intended to serve as a textbook for an introductory mathematics course in logic at the junior-senior level. As a text, the book can be used in courses anywhere from a quarter to a year in length. The extra time afforded by a semester would permit some glimpse of undecidability, as in Section 3.
ISBN 13: 9780122384523