Robert R. Stoll - Set Theory and Logic

SET THEORY
AND LOGIC

SET THEORY
AND LOGIC

by
Robert R. Stoll

Cleveland State University

Dover Publications, Inc.
New York

Copyright

Copyright 1961, 1963 by Robert R. Stoll.

All rights reserved.

Bibliographical Note

This Dover edition, first published in 1979, is an unabridged and corrected republication of the work originally published in 1963 by W. H. Freeman and Company.

International Standard Book Number

ISBN-13: 978-0-486-63829-4
ISBN-10: 0-486-63829-4
Library of Congress Catalog Card Number: 79-87812

Manufactured in the United States by Courier Corporation
63829412
www.doverpublications.com

To Kurt, Nancy, and David

PREFACE

This book is an outgrowth of a course which I have developed at Oberlin College for advanced undergraduates. The purpose of the course is to introduce students to the foundations of mathematics, to give them initial training in the axiomatic method in mathematics, and to provide them with the necessary tools to cope successfully with graduate level courses having an abstract and axiomatic orientation. It may be inferred that as I use the term foundations of mathematics I understand it to mean an analysis of fundamental concepts of mathematics, intended to serve as a preparation for studying the superstructure from a general and unified perspective.

The book contains adequate material for any one of a variety of one- year upper undergraduate courses with a title resembling Introduction to Foundations of Mathematics. That is, there is sufficient material for a years course in which the instructor chooses to emphasize the construction of standard mathematical systems, or the role of logic in connection with axiomatic theories, or, simply, mathematical logic. Further, by focusing attention on certain chapters, it can serve as a text for one- semester courses in set theory (Chapters ).

The book has been organized so that not until the last chapter does symbolic logic play a significant role.

Most of the material presented might be described as the mathematics whose development was directly stimulated by investigations pertaining to the real number system. That is, the development and the study of the real number system serve as the underlying theme of the book. I will elaborate on this statement after outlining the contents.

is an introduction to so-called intuitive set theory. Along with the algebra of sets the theory is developed to the point where the notion of a relation can be defined. The remainder of the chapter is concerned with the special types of relations called equivalence relations, functions, and ordering relations. Sufficient examples and exercises are provided to enable the beginner to assimilate these concepts fully.

, the classical paradoxes (that is, bona fide contradictions) of intuitive set theory are described.

In the natural number sequence is extended to the real number system via the integers and the rational numbers, with Cauchy sequences being used in the extension of the rationals to the reals. Repetitious details have been cut to a minimum in the hope of relieving the boredom of this essential chapter.

is devoted to an intuitive exposition of symbolic logic. The simplest part of the classical variety of this subject, the statement calculus, is treated in some detail. Although the much more comprehensive system, the first-order predicate calculus, is barely more than outlined, by following the same pattern as that employed for the statement calculus, it is hoped that the exposition will be intelligible. Probably every serious student of mathematics should understand symbolic logic to the extent it is presented here, if only to be able to take advantage of its symbolism and know how to form the negation of the function / is continuous at x = a in a mechanical way.

.

contains the first full-blown development of an axiomatic theory. The theory that we have chosen for our prime example, that of Boolean algebras, is easily susceptible of investigation. Moreover, as we show in the latter part of the chapter, it has close connections with some of the logic discussed earlier.

the Zermelo-Fraenkel theory of sets is outlined. In the last section contact is made with another well-known axiomatization of classical set theorythat due to von Neumann. Zermelo-Fraenkel set theory was chosen for exposition because its development closely parallels that of intuitive set theory. However, for transfinite arithmetic the von Neumann theory of ordinal and cardinal numbers (which can be imbedded in every suitable axiomatization of set theory) was selected because of its elegance.

In several axiomatic theories which fall within the realm of modern algebra are introduced. The primary purpose is to enable us to give self-contained characterizations in turn of the system of integers, of rational numbers, and, finally, of real numbers. This is done in the last three sections of the chapter.

Finally, there is we round out our discussion of the axiomatic method with the presentation of three famous theorems about formal axiomatic mathematics. One of these, obtained by Alonzo Church in 1936, asserts that there is no automatic procedure for deciding whether an arbitrary formula of (an axiomatized version of) the predicate calculus of first order is a theorem. One of the other two theorems (both obtained by Kurt Godel in 1931) asserts that a sufficiently rich formal system of arithmetic, if consistent, contains a statement which is neither provable nor refutable. The last asserts that if such a system of arithmetic is consistent, then it is impossible to prove just that.

Our account of these theorems is neither self-contained nor rigorous, but, we believe, adequate for the reader to gain an understanding of their meaning and significance. In defense of such an approach we shall say only that we believe this coverage will meet the needs of most students. Those who desire a complete and rigorous account must be prepared to spend a considerable amount of time in mastering a variety of technical details.

We conclude our outline of the contents by substantiating an earlier , all of the material discussed is directly related to the real number system in the sense that it fits into the category of (a) a preliminary to the development of the system, or (b) developing some facet of either the system itself or an extension of it, or (c) developing tools to either characterize the system or study some property of it.

A Note to the Instructor

Since mathematical logic is often not an outstanding feature of a mathematicians repertoire, it may be helpful to clarify its role in this book. that logic (in the form of the first-order predicate calculus) enters explicitly into the mathematical development. But even here, for the instructor who has just a modest background in logic, with the standard texts by Church, Kleene, and Rosser at his side, all will go well.

Further, we call attention to the bibliographical notes which appear at the end of most chapters. These give references to original papers or to expositions which can serve as collateral reading material for students.

Numerous acknowledgments of assistance in this undertaking are in order. First there are those which appear in my book titled Sets, Logic, and Axiomatic Theories (which is made up of some of the more elementary portions of this book)to the National Science Foundation and Oberlin College, for making it possible for me to devote full time to writing for one year, and to Professor Angelo Margaris, for numerous helpful suggestions. In addition, I gratefully acknowledge the constructive criticism rendered in very precise form by Professor Anil Nerode, who read a near-final version of the manuscript at the request of the publisher. Professor Leon Henkin made numerous suggestions for the improvement of ; any shortcomings that remain are my sole responsibility. Finally, I am most grateful to my wifenot only for her typing of the manuscript again and again but also for managing to keep her family intact at the same time.