**UFBA**

# 1 Stoll Set Theory and Logic

(Parte **1** de 6)

Robert R. Stoll Cle;laixi State University

Dover Publications, Inc. NewYork

Copyright

Copyright (0 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

To Kurt, Nancy, and David To Kurt, Nancy, and David

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 year's 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 onesemester courses in set theory (Chapters 1, 2, 5, 7), in logic (Chapters 1, 4, 5, 6, 9), and in the development of the real number system (Chap- ters 1, 2, 3, 5, 8). 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.

Chapter 1is 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.

Chapter 2 begins with a discussion of a type of system (an "integral system") which incorporates several features of the natural number vii viii Preface sequence, as this notion is understood intuitively. Once it is proved that there is essentially only one integral system, we take as our definition of the natural number system some one integral system. After the arithmetic of this system is developed, careful consideration is given to both definition and proof by induction. There follows an account of Cantor's theory of cardinal and ordinal numbers. In Section 8 is introduced the remaining principle of intuitive set theory, the axiom of choice, along with several equivalent propositions. In Section 9, with the aid of the axiom of choice, the arithmetic of infinite cardinals is reduced to a triviality. Section 10 is devoted to propositions of a different kind which are equivalent to the axiom of choice. Finally, in Section 1, the classical paradoxes (that is, bona fide contradictions) of intuitive set theory are described. In Chapter 3 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 rationale to the reals. Repeti- tious details have been cut to a minimum in the hope of relieving the boredom of this essential chapter. Chapter 4 is devoted to an intuitive exposition of symbolic logic. The simplest [)art 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 f is con- tinuous at x = a" in a mechanical way. Chapter 5 consists of an exposition of the axiomatic method, the notion of an axiomatic theory, and related topics as they are encountered in everyday mathematics. It is only the italicized qualification that justifies the inclusion of this chapter. For in view of the tremendous accomplishments in the area of the foundations of mathematics in recent years, this chapter is antiquated. An introduction to modern investigations appears in Chapter 9. Chapter 6 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.

Preface ix

In Chapter 7 the Zerrnelo-Fracnkel theory of sets is outlined. In the last section contact is made with another well-known axiomatization of classical set theory-that due to von Neurnann. Zerinelo-Fraenkcl 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 inibedded in every suitable axiolnatization of set theory) was selected because of its elegance.

In Chapter 8 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 clone in the last three sections of the chapter.

Finally, there is Chapter 9, which is an introductory account of relatively recent investigations of the foundations of mathematics. A distinctive feature of the modern approach is the explicit incorporation of a theory of logic into an axiomatic theory. We restrict our attention to so-called first-order theories, that is, those axiomatic theories for which the predicate calculus of first order provides a logical base. Sections 4-7 give a rigorous account for first-order theories of the material discussed at the intuitive level in Chapter 5. Much of this has been available here- tofore only in more technically formidable accounts. In Sections 8-10 we round out our discussion of the. axiomatic method with the prescnta-, tion 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 axioinatizccl 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 stu- dents: 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 x Preface remark that the real number system serves as the underlying theme of the book. Indeed, apart from Chapter 6, 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 mathematician's repertoire, it may be helpful to clarify its role in this book. Chapter 4 should serve as an adequate introduction for a newcomer into this discipline and be more than adequate to cope with the references to logic which are made in Chapters 5 and 6. As has been stated in the above, itis only in Chapter 9 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. 't'hese give references to original papers or to expositions which can serve as collateral reacting 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 hook) -. to the National Science Foundation and Oberlin College, for making it possible for nrc: 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 Chapter 9; any shortcomings that remain are my sole responsibility. Finally, I am most grateful to my wife - not only for her typing of the manuscript again and again but also for managing to keep her family intact at the same tinge.

January 1963ROBERT R. STOLL

Chapter 1SETS AND RELATIONS

1. Cantor's Concept of a Set 2. The Basis of Intuitive Set Theory 3. Inclusion

4. Operations for Sets 5. The Algebra of Sets 6. Relations 7. Equivalence Relations 8. Functions 9. Composition and Inversion for Functions 10. Operations for Collections of Sets 1. Ordering Relations

Chapter 2 THE NATURAL NUMBER SEQUENCE AND ITS GENERALIZATIONS

1. The Natural Number Sequence 2. Proof and Definition by Induction

3. Cardinal Numbers 4. Countable Sets

5. Cardinal Arithmetic 6. Order 't'ypes 7. Well-ordered Sets and Ordinal Numbers

8. The Axiom of Choice, the Well-ordering Theorem, and Zorn's lemma

9. Further Properties of Cardinal Numbers

10. Some Theorems Equivalent to the Axiom of Choice

1. The Paradoxes of Intuitive Set Theory

126 xi xii Contents

Chapter,; THE EXTENSION OF THE NATURAL NUMBERS TO THE REAL NUMBERS130

1. The System of Natural Numbers130 2. Differences132 3. Integers134 4. Rational Numbers137 5. Cauchy Sequences of Rational Numbers142 6. Real Numbers149 7. Further Properties of the Real Number System154

Chapter 4 LOGIC160

1. The Statement Calculus. Sentential Connectives160 2. The Statement Calculus. 'truth Tables164 3. '1 he Statement Calculus. Validity169 4. The Statement Calculus. Consequence179

5. The Statement Calculus. Applications187

6. The Predicate Calculuis. Symbolizing Everyday Language 192

7. The Predicate Calculus. A Formulation200 8. The Predicate Calculus. Validity205 9. The Predicate Calculus. Consequence215

Chapter 5 INFORMAL AXIOMATIC MATHEMATICS221

1. The Concept of an Axiomatic Theory221 2. Informal Theories227

3. Definitions of Axiomatic Theories by Set-theoretical Predicates 233

4. Further Features of Informal 'T'heories236

Chapter 6 BOOLEAN ALGEBRAS248

1. A Definition of a Boolean Algebra248 2. Some Basic Properties of a Boolean Algebra250

Contents xiii

3. Another Formulation of the Theory254 4. Congruence Relations for a Boolean Algebra259

5. Representations of Boolean Algebras267 6. Statement Calculi as Boolcan Algebras273 7. Free Boolcan Algebras274

8. Applications of the Theory of Boolean Algebras to Statement Calculi278

9. Further Interconnections between Boolean Algebras and Statement Calculi282

Chapter 7 INFORMAL AXIOMATIC SET THEORY289

1. The Axioms of Extension and Set Formation289 2. The Axiom of Pairing292 3. The Axioms of Union and Power Set294 4. The Axiom of Infinity297

5. The Axiom of Choice302

6. The Axiom Schemas of Replacement and Restriction302

7. Ordinal Numbers306 8. Ordinal Arithmetic312

9. Cardinal Numbers and Their Arithmetic316

10. The von Neumann-Bcrnays-Godel Theory of Sets318

Chapter 8 SEVERAL ALGEBRAIC THEORIES321

1. Features of Algebraic 'Theories322 2. Definition of a Scmigroup324 3. Definition of a Group329 4. Subgroups333

5. Coset Decompositions and Congruence Relations for Groups339

6. Rings, Integral Domains, and Fields346 7. Subrings and Difference Rings351 xiv Contents

8. A Characterization of the System of Integers357

9. A Characterization of the System of Rational Numbers361

10. A Characterization of the Real Number System367

Chapter g FIRST-ORDER THEORIES 1. Formal Axiomatic Theories

2. The Statement Calculus as a Formal Axiomatic Theory

3. Predicate Calculi of First Order as Formal Axiomatic Theories

4. First-order Axiomatic Theories

5. Metarnathernatics

6. Consistency and Satisfiability of Sets of Formulas

7. Consistency, Completeness, and Categoricity of First-order Theories

8. 'l'uring Machines and Recursive Functions

9. Some Undecidable and Some Decidable 'T'heories

10. 06del's Theorems 1. Some Further Remarks about Set Theory

References Symbols and Notation

Author Index Subject Index

CHAPTER 1Sets and Relations

THETHEORY OF SETS as a mathematical discipline originated with the German mathematician G. Cantor (1845-1918). A complete account of its birth and childhood is out of the question here, since a considerable knowledge of mathematics is a prerequisite for its compre- hension. Instead, we adopt the uneasy compromise of a brief sketch of these matters. If this proves too difficult for the reader, nothing is lost ; on the other hand, if it is at least partially understood, something may be gained. Cantor's investigation of questions pertaining to trigonometric series and series of real numbers led him to recognize the need for a means of comparing the magnitude of infinite sets of numbers. To cope with this problem, he introduced the notion of the power (or size) of a set by defining two sets as having the same power if the members of one can be paired with those of the other. Since two finite sets can be paired if and only if they have the same number of members, the power of a finite set may be identified with a counting number. Thus the notion of power for infinite sets provides a generalization of everyday counting numbers.

(Parte **1** de 6)