Transcription

A Book ofSET THEORYCHARLES C. PINTEREmeritus ProfessorBucknell UniversityDOVER PUBLICATIONS, INC.Mineola, New York

CopyrightCopyright 1971, 2014 by Charles C. PinterAll rights reserved.Bibliographical NoteA Book of Set Theory, first published by Dover Publications, Inc., in 2014, is a revised and corrected republication of Set Theory,originally published in 1971 by Addison-Wesley Publishing Company, Reading, Massachusetts. This book has been reprinted with thecooperation of Kyung Moon Publishers, South Korea.Library of Congress Cataloging-in-Publication DataPinter, Charles C., 1932–author.A book of set theory / Charles C Pinter.p. cm.“A revised and corrected republication of Set Theory, originally published in 1971 by Addison-Wesley Publishing Company,Reading, Massachusetts.”Summary: “This accessible approach to set theory for upper-level undergraduates poses rigorous but simple arguments. Eachdefinition is accompanied by commentary that motivates and explains new concepts. A historical introduction is followed by discussionsof classes and sets, functions, natural and cardinal numbers, the arithmetic of ordinal numbers, and related topics. 1971 edition with newmaterial by the author”—Provided by publisher.Includes bibliographical references and index.eISBN-13: 978-0-486-79549-21. Set theory. I. Title.QA248.P55 2013511.3’.22—dc232013024319Manufactured in the United States by Courier Corporation49708901 2014www.doverpublications.com

To my students,from whom I have learned how to explain and how to teach

ContentsPrefaceChapter 0 Historical Introduction1 The background of set theory2 The paradoxes3 The axiomatic method4 Axiomatic set theory5 Objections to the axiomatic approach Other proposals6 Concluding remarksChapter 1 Classes and Sets1 Building sentences2 Building classes3 The algebra of classes4 Ordered pairs Cartesian products5 Graphs6 Generalized union and intersection7 SetsChapter 2 Functions1 Introduction2 Fundamental concepts and definitions3 Properties of composite functions and inverse functions4 Direct images and inverse images under functions5 Product of a family of classes6 The axiom of replacementChapter 3 Relations1 Introduction2 Fundamental concepts and definitions3 Equivalence relations and partitions4 Pre-image, restriction and quotient of equivalence relations5 Equivalence relations and functionsChapter 4 Partially Ordered Classes1 Fundamental concepts and definitions2 Order preserving functions and isomorphism3 Distinguished elements Duality

456LatticesFully ordered classes Well-ordered classesIsomorphism between well-ordered classesChapter 5 The Axiom of Choice and Related Principles1 Introduction2 The axiom of choice3 An application of the axiom of choice4 Maximal principles5 The well-ordering theorem6 ConclusionChapter 6 The Natural Numbers1 Introduction2 Elementary properties of the natural numbers3 Finite recursion4 Arithmetic of natural numbers5 Concluding remarksChapter 7 Finite and Infinite Sets1 Introduction2 Equipotence of sets3 Properties of infinite sets4 Properties of denumerable setsChapter 8 Arithmetic of Cardinal Numbers1 Introduction2 Operations on cardinal numbers3 Ordering of the cardinal numbers4 Special properties of infinite cardinal numbers5 Infinite sums and products of cardinal numbersChapter 9 Arithmetic of the Ordinal Numbers1 Introduction2 Operations on ordinal numbers3 Ordering of the ordinal numbers4 The alephs and the continuum hypothesis5 Construction of the ordinals and cardinalsChapter 10Transfinite Recursion Selected Topics in the Theory of Ordinals and Cardinals

12345Chapter 11123456Transfinite recursionProperties of ordinal exponentiationNormal formEpsilon numbersInaccessible ordinals and cardinalsConsistency and Independence in Set TheoryWhat is a set?ModelsIndependence results in set theoryThe question of models of set theoryProperties of the constructible universeThe Gödel TheoremsBibliographyIndex

PrefaceOver many years of selecting instructional materials for my courses, I came to understand thattextbooks that are congenial to students obey a law of reciprocity that I wish to propose as an axiom:Axiom The more effort an author puts into writing a text, the less effort is required of the reader tounderstand it.I adopted this guiding principle as a categorical imperative during the writing of this book. Even afterall the mathematics was in place, I reread and rewrote many times and tested explanatory strategies withmy students. I have dedicated this book to them because they have been my most patient and honestcritics. The book owes its present form largely to them and to their (sometimes naïve, often brilliant)suggestions.Mathematics has a superbly efficient language by means of which vast amounts of information can beelegantly expressed in a few formal definitions and theorems. It is remarkable that the life work ofconsecutive generations of great thinkers can often be summed up in a set of equations. The economy ofthe language masks the richness and complexity of the thoughts that lie behind the symbols. Everymathematics student has to master the conventions for using its language effectively. However, what isfar more important is that the student be initiated into the inner life of mathematics—the images, theintuitions, the metaphors that, once grasped, make us say, “Aha! Now I understand! Now I see it!” Thisinner seeing is what makes mathematics vital and exciting.What is most unique about set theory is that it is the perfect amalgam of the visual and the abstract.The notions of set theory, and the ideas behind many of the proofs, present themselves to the inner eyein vivid detail. These pictures are not as overtly visual as those of geometry or calculus. You don’t seethem in the same way that you see a circle or a tangent line. But these images are the way intoabstraction. For the maturing student, the journey deeper into abstraction is a rite of passage into theheart of mathematics.Set theory is also the most “philosophical” of all disciplines in mathematics. Questions are bound tocome up in any set theory course that cannot be answered “mathematically”, for example with a formalproof. The big questions cannot be dodged, and students will not brook a flippant or easy answer. Is thecontinuum hypothesis a fact of the world? Is the axiom of choice a truth? If we cannot answer with adefinite yes or no, in what manner are they justified? (That one requires a long answer). What is themeaning of the Jacob’s ladder of successive infinities so high that the very thought of it leads to a kindof intellectual vertigo? To what extent does mathematics dwell in a Platonic realm—and if it does, thenin the words of Eugene Wigner, “how do you explain the unreasonable effectiveness of mathematics inthe natural world?” Or as Descartes wondered, where do you find the nexus between the material worldand the products of thought?In this book I have tried, insofar as possible, not to evade these questions nor to dwell on themexcessively. Students should perceive that mathematics opens doors to far-reaching and fascinatingquestions, but on the other hand they must remain anchored in mathematics and not get lost in thenarcotic haze of speculative thought. I have tried to provide the necessary background for understandingaxiomatics and the purpose and meaning of each of the axioms needed to found set theory. I have triedto give a fair account of the philosophical problems that lie at the center of the formal treatment ofinfinities and other abstractions. Above all, of course, I have endeavored to present the standard topicsof set theory with uncompromising rigor and precision, and made it clear that the formalism on the onehand, and the intuitive explanations on the other hand, belong in two separate domains, one useful forunderstanding, the other essential for doing mathematics.

This book is a revised and re-written version of an earlier edition, published in 1972 by AddisonWesley. I have retained most of the formal definitions, theorems and proofs, with nothing more than afew corrections where needed. I have also retained the initial chapter that narrates the origins and earlyhistory of set theory, because history (in general) does not change. I have added commentary, introducedsome new discussions, and reorganized a few proofs in order to make them cleaner and clearer. Finally,I have added a new chapter on models of set theory and the independence results of Gödel and Cohen. Ihave set the discussion of these topics at a level that is accessible to undergraduates while notconcealing the difficulties of the subject.

0Historical Introduction1 THE BACKGROUND OF SET THEORYAlthough set theory is recognized to be the cornerstone of the “new” mathematics, there is nothingessentially new in the intuitive idea of a set. From the earliest times, mathematicians have been led toconsider sets of objects of one kind or another, and the elementary notions of modern set theory areimplicit in a great many classical arguments. However, it was not until the latter part of the nineteenthcentury, in the work of Georg Cantor (1845–1918), that sets came into their own as the principal objectof a mathematical theory.Strangely, it was his work in the highly technical field of trigonometric series which first led Cantorto study the properties of sets. At first, he confined himself to certain particular sets of real numberswhich occurred in connection with the convergence of series. But Cantor was quick to understand thathis discoveries applied to sets quite generally; in a series of remarkable papers, published between 1873and 1897, he moved progressively further from the concrete problems which had initiated his thinkingon sets, and toward the powerful general concepts which underlie set theory today.The boldest step which Cantor had taken—in the eyes of his contemporaries–was his use of infinitesets, which he considered as no less natural than using finite sets. The question of “infinity” had longbeen one of the most sensitive problems of mathematics. The reader is undoubtedly acquainted withZeno’s famous “paradox”, in which a unit line segment is divided into subintervals by the points 1/2,1/4, 1/8, 1/16, etc. Each subinterval—no matter how small—has a definite, nonzero length, and thereare infinitely many subintervals; hence, the seemingly paradoxical conclusion that infinitely manynonzero lengths can be added together to produce a finite length. In order to avoid such traps, classicalmathematicians made a distinction between the “actual” infinite—in which infinitely many objects areconceived of as existing simultaneously—and the “virtual” infinite, which is simply the potential toexceed any given finite quantity. The “virtual” infinite was regarded as safe, hence admissible, whereasthe “actual” infinite was taboo.It is not surprising then, that Cantor’s theory—with its uninhibited use of infinite sets (the notion ofinfinite was obviously understood here in the “actual” sense)—was not immediately accepted by hiscontemporaries. It was received at first with skepticism, sometimes even with open hostility. However,by the 1890’s the more “palatable” parts of Cantor’s theory were widely used, for they provided anelegant framework for a wide variety of mathematical theories. And before the turn of the century, eventhe most revolutionary aspects of set theory had been accepted by a great many mathematicians—chiefly because they turned out to be invaluable tools, particularly in analysis.Meanwhile, the work of several outstanding mathematicians, in particular Dedekind, was taking aturn which would cast set theory in its most promising role—as the fundamental, “unifying” branch ofmathematics. From the earliest times, mathematicians have given thought to the possibility of unifyingthe entire discipline under a small number of basic principles. Many of the ancient schools, from Euclidthrough the Middle Ages, contended that the various branches of mathematics could be subsumed undergeometry (numbers might be conceived as geometric proportions); a far more successful attempt atunification came in the nineteenth century, when the work of Weierstrass, Dedekind, and otherssuggested that all of classical mathematics could be derived from the arithmetic of the natural numbers

(positive integers). It was shown that every real number can be regarded as a sequence (called a“Cauchy sequence”) of rational numbers; hence the study of the real numbers is reduced to that of therational numbers. But the rational numbers can easily be regarded as pairs of integers, so finally themathematics of the real numbers—which includes the calculus and (via analytic geometry) all ofgeometry—can be based on the natural numbers.It was at this crucial point in the evolution of ideas on the foundations of mathematics that Dedekind,in his little book Was sind und was sollen die Zahlen (1888), revealed that the concept of naturalnumbers can be derived from the basic principles of set theory. A modern way to show this is thefollowing: we let “0” be the empty set (that is, the set with no elements, denoted by the symbol Ø); “1”is defined to be the set {Ø}, that is, the set (of sets) containing the one element Ø. Then, “2” is definedto be the set {0, 1}, “3” is defined to be {0, 1, 2}, and so on. All the properties of the natural numberscan be proven using these definitions and elementary set theory.By the turn of the century, then, set theory had not only been accepted as an indispensable tool by alarge segment of the mathematical community, but, moreover, it was a serious contender for the positionof primacy among the mathematical sciences.Ironically, at the very time when Cantor’s ideas seemed finally to have gained acceptance, the first ofcertain “paradoxes” were announced, which eventually cast serious doubts as to the basic soundness ofset theory in its “Cantorian” form. These paradoxes had such wide re

These pictures are not as overtly visual as those of geometry or calculus. You don’t see them in the same way that you see a circle or a tangent line. But these images are the way into abstraction. For the maturing student, the journey deeper into abstraction is a rite of passage into the heart of mathematics. Set theory is also the most “philosophical” of all disciplines in mathematics .