Main
Set Theory
Set Theory
Thomas Jech
0 /
0
How much do you like this book?
What’s the quality of the file?
Download the book for quality assessment
What’s the quality of the downloaded files?
Set Theory has experienced a rapid development in recent years, with major advances in forcing, inner models, large cardinals and descriptive set theory. The present book covers each of these areas, giving the reader an understanding of the ideas involved. It can be used for introductory students and is broad and deep enough to bring the reader near the boundaries of current research. Students and researchers in the field will find the book invaluable both as a study material and as a desktop reference.
Categories:
Year:
2006
Edition:
3rd
Publisher:
Springer
Language:
english
Pages:
787
ISBN 10:
3540440852
ISBN 13:
9783540440857
Series:
Springer Monographs in Mathematics
File:
PDF, 4.09 MB
Your tags:
Download (pdf, 4.09 MB)
 Open in Browser
 Checking other formats...
 Convert to EPUB
 Convert to FB2
 Convert to MOBI
 Convert to TXT
 Convert to RTF
 Converted file can differ from the original. If possible, download the file in its original format.
 Please login to your account first

Need help? Please read our short guide how to send a book to Kindle
The file will be sent to your email address. It may take up to 15 minutes before you receive it.
The file will be sent to your Kindle account. It may takes up to 15 minutes before you received it.
Please note: you need to verify every book you want to send to your Kindle. Check your mailbox for the verification email from Amazon Kindle.
Please note: you need to verify every book you want to send to your Kindle. Check your mailbox for the verification email from Amazon Kindle.
You may be interested in Powered by Rec2Me
Most frequently terms
theorem^{1381}
cardinal^{1321}
lemma^{1131}
generic^{676}
countable^{619}
stationary^{613}
cardinals^{606}
ordinal^{560}
subset^{521}
sequence^{502}
measurable^{472}
boolean^{406}
algebra^{389}
elementary^{375}
axiom^{373}
dense^{360}
closed unbounded^{347}
transitive^{325}
uncountable^{325}
math^{295}
subsets^{291}
dom^{285}
embedding^{274}
induction^{262}
founded^{260}
disjoint^{257}
ordinals^{247}
reals^{233}
formula^{232}
boolean algebra^{229}
saturated^{218}
implies^{209}
inaccessible^{202}
measurable cardinal^{201}
construct^{198}
elementary embedding^{187}
borel^{187}
limit ordinal^{186}
corollary^{185}
iteration^{174}
constructible^{171}
canonical^{169}
ult^{169}
pcf^{167}
zfc^{161}
partition^{159}
suslin^{152}
baire^{151}
woodin^{149}
ord^{144}
generic ﬁlter^{138}
large cardinals^{138}
skolem^{138}
proof of theorem^{135}
nonempty^{134}
ultrapower^{133}
seq^{132}
generic extension^{129}
axiom of choice^{128}
unbounded set^{128}
Related Booklists
0 comments
You can write a book review and share your experiences. Other readers will always be interested in your opinion of the books you've read. Whether you've loved the book or not, if you give your honest and detailed thoughts then people will find new books that are right for them.
1

2

Springer Monographs in Mathematics This page intentionally left blank Thomas Jech Set Theory The Third Millennium Edition, revised and expanded 123 Thomas Jech email: jech@math.cas.cz The original edition was published in 1978 by Academic Press, Inc. in the series Pure and Applied Mathematics, vol. 79, with the ISBN 0123819504 The second edition was published in 1997 by SpringerVerlag under the same title in the series Perspectives in Mathematical Logic CataloginPublication Data applied for Die Deutsche Bibliothek  CIPEinheitsaufnahme Jech, Thomas J.: Set theory / Thomas Jech.  3rd Millennium ed, rev. and expanded.  Berlin ; Heidelberg ; New York ; Hong Kong ; London ; Milan ; Paris ; Tokyo : Springer, 2002 (Springer monographs in mathematics) ISBN 3540440852 Mathematics Subject Classification (2000): 03Exx ISSN 14397382 Corrected 4th printing 2006 ISBN10 3540440852 SpringerVerlag Berlin Heidelberg New York ISBN13 9783540440857 SpringerVerlag Berlin Heidelberg New York ISBN 3540630481 2nd ed. SpringerVerlag Berlin Heidelberg New York This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable for prosecution under the German Copyright Law. Springer is a part of Springer Science+Business Media springer.com © SpringerVerlag Berlin Heidelberg 1997, 2003 Printed in Germany The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations ; and therefore free for general use. Typesetting by the author using a Springer TEX macro package Production: LETEX Jelonek, Schmidt & Vöckler GbR, Leipzig Cover design: Erich Kirchner, Heidelberg Printed on acidfree paper 46/3100YL  5 4 3 2 1 0 For Paula, Pavel, and Susanna This page intentionally left blank Preface When I wrote the ﬁrst edition in the 1970s my goal was to present the state of the art of a century old discipline that had recently undergone a revolutionary transformation. After the book was reprinted in 1997 I started contemplating a revised edition. It has soon become clear to me that in order to describe the present day set theory I would have to write a more or less new book. As a result this edition diﬀers substantially from the 1978 book. The major diﬀerence is that the three major areas (forcing, large cardinals and descriptive set theory) are no longer treated as separate subjects. The progress in past quarter century has blurred the distinction between these areas: forcing has become an indispensable tool of every set theorist, while descriptive set theory has practically evolved into the study of L(R) under large cardinal assumptions. Moreover, the theory of inner models has emerged as a major part of the large cardinal theory. The book has three parts. The ﬁrst part contains material that every student of set theory should learn and all results contain a detailed proof. In the second part I present the topics and techniques that I believe every set theorist should master; most proofs are included, even if some are sketchy. For the third part I selected various results that in my opinion reﬂect the state of the art of set theory at the turn of the millennium. I wish to express my gratitude to the following institutions that made their facilities available to me while I was writing the book: Mathematical Institute of the Czech Academy of Sciences, The Center for Theoretical Study in Prague, CRM in Barcelona, and the Rockefeller Foundation’s Bellagio Center. I am also grateful to numerous set theorists who I consulted on various subjects, and particularly to those who made invaluable comments on preliminary versions of the manuscript. My special thanks are to Miroslav Repický who converted the handwritten manuscript to LATEX. He also compiled the three indexes that the reader will ﬁnd extremely helpful. Finally, and above all, I would like to thank my wife for her patience and encouragement during the writing of this book. Prague, May 2002 Thomas Jech This page intentionally left blank Table of Contents Part I. Basic Set Theory 1. Axioms of Set Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Axioms of ZermeloFraenkel. Why Axiomatic Set Theory? Language of Set Theory, Formulas. Classes. Extensionality. Pairing. Separation Schema. Union. Power Set. Inﬁnity. Replacement Schema. Exercises. Historical Notes. 2. Ordinal Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 Linear and Partial Ordering. WellOrdering. Ordinal Numbers. Induction and Recursion. Ordinal Arithmetic. WellFounded Relations. Exercises. Historical Notes. 3. Cardinal Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 Cardinality. Alephs. The Canonical WellOrdering of α × α. Coﬁnality. Exercises. Historical Notes. 4. Real Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 The Cardinality of the Continuum. The Ordering of R. Suslin’s Problem. The Topology of the Real Line. Borel Sets. Lebesgue Measure. The Baire Space. Polish Spaces. Exercises. Historical Notes. 5. The Axiom of Choice and Cardinal Arithmetic . . . . . . . . . . . . . 47 The Axiom of Choice. Using the Axiom of Choice in Mathematics. The Countable Axiom of Choice. Cardinal Arithmetic. Inﬁnite Sums and Products. The Continuum Function. Cardinal Exponentiation. The Singular Cardinal Hypothesis. Exercises. Historical Notes. 6. The Axiom of Regularity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 The Cumulative Hierarchy of Sets. ∈Induction. WellFounded Relations. The BernaysGödel Axiomatic Set Theory. Exercises. Historical Notes. 7. Filters, Ultraﬁlters and Boolean Algebras . . . . . . . . . . . . . . . . . . 73 Filters and Ultraﬁlters. Ultraﬁlters on ω. κComplete Filters and Ideals. Boolean Algebras. Ideals and Filters on Boolean Algebras. Complete Boolean Algebras. Complete and Regular Subalgebras. Saturation. Distributivity of Complete Boolean Algebras. Exercises. Historical Notes. X Table of Contents 8. Stationary Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 Closed Unbounded Sets. Mahlo Cardinals. Normal Filters. Silver’s Theorem. A Hierarchy of Stationary Sets. The Closed Unbounded Filter on Pκ (λ). Exercises. Historical Notes. 9. Combinatorial Set Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 Partition Properties. Weakly Compact Cardinals. Trees. Almost Disjoint Sets and Functions. The Tree Property and Weakly Compact Cardinals. Ramsey Cardinals. Exercises. Historical Notes. 10. Measurable Cardinals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 The Measure Problem. Measurable and RealValued Measurable Cardinals. Measurable Cardinals. Normal Measures. Strongly Compact and Supercompact Cardinals. Exercises. Historical Notes. 11. Borel and Analytic Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 Borel Sets. Analytic Sets. The Suslin Operation A. The Hierarchy of Projective Sets. Lebesgue Measure. The Property of Baire. Analytic Sets: Measure, Category, and the Perfect Set Property. Exercises. Historical Notes. 12. Models of Set Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 Review of Model Theory. Gödel’s Theorems. Direct Limits of Models. Reduced Products and Ultraproducts. Models of Set Theory and Relativization. Relative Consistency. Transitive Models and ∆0 Formulas. Consistency of the Axiom of Regularity. Inaccessibility of Inaccessible Cardinals. Reﬂection Principle. Exercises. Historical Notes. Part II. Advanced Set Theory 13. Constructible Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 The Hierarchy of Constructible Sets. Gödel Operations. Inner Models of ZF. The Lévy Hierarchy. Absoluteness of Constructibility. Consistency of the Axiom of Choice. Consistency of the Generalized Continuum Hypothesis. Relative Constructibility. OrdinalDeﬁnable Sets. More on Inner Models. Exercises. Historical Notes. 14. Forcing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 Forcing Conditions and Generic Sets. Separative Quotients and Complete Boolean Algebras. BooleanValued Models. The BooleanValued Model V B . The Forcing Relation. The Forcing Theorem and the Generic Model Theorem. Consistency Proofs. Independence of the Continuum Hypothesis. Independence of the Axiom of Choice. Exercises. Historical Notes. 15. Applications of Forcing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 Cohen Reals. Adding Subsets of Regular Cardinals. The κChain Condition. Distributivity. Product Forcing. Easton’s Theorem. Forcing with a Class of Conditions. The Lévy Collapse. Suslin Trees. Random Reals. Forcing with Perfect Trees. More on Generic Extensions. Symmetric Submodels of Generic Models. Exercises. Historical Notes. Table of Contents XI 16. Iterated Forcing and Martin’s Axiom . . . . . . . . . . . . . . . . . . . . . 267 TwoStep Iteration. Iteration with Finite Support. Martin’s Axiom. Independence of Suslin’s Hypothesis. More Applications of Martin’s Axiom. Iterated Forcing. Exercises. Historical Notes. 17. Large Cardinals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285 Ultrapowers and Elementary Embeddings. Weak Compactness. Indescribability. Partitions and Models. Exercises. Historical Notes. 18. Large Cardinals and L . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311 Silver Indiscernibles. Models with Indiscernibles. Proof of Silver’s Theorem and 0 . Elementary Embeddings of L. Jensen’s Covering Theorem. Exercises. Historical Notes. 19. Iterated Ultrapowers and L[U ] . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339 The Model L[U ]. Iterated Ultrapowers. Representation of Iterated Ultrapowers. Uniqueness of the Model L[D]. Indiscernibles for L[D]. General Iterations. The Mitchell Order. The Models L[U]. Exercises. Historical Notes. 20. Very Large Cardinals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365 Strongly Compact Cardinals. Supercompact Cardinals. Beyond Supercompactness. Extenders and Strong Cardinals. Exercises. Historical Notes. 21. Large Cardinals and Forcing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389 Mild Extensions. KunenParis Forcing. Silver’s Forcing. Prikry Forcing. Measurability of ℵ1 in ZF. Exercises. Historical Notes. 22. Saturated Ideals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409 RealValued Measurable Cardinals. Generic Ultrapowers. Precipitous Ideals. Saturated Ideals. Consistency Strength of Precipitousness. Exercises. Historical Notes. 23. The Nonstationary Ideal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 441 Some Combinatorial Principles. Stationary Sets in Generic Extensions. Precipitousness of the Nonstationary Ideal. Saturation of the Nonstationary Ideal. Reﬂection. Exercises. Historical Notes. 24. The Singular Cardinal Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 457 The GalvinHajnal Theorem. Ordinal Functions and Scales. The pcf Theory. The Structure of pcf. Transitive Generators and Localization. Shelah’s Bound on 2ℵω . Exercises. Historical Notes. 25. Descriptive Set Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 479 The Hierarchy of Projective Sets. Π11 Sets. Trees, WellFounded Relations and κSuslin Sets. Σ12 Sets. Projective Sets and Constructibility. Scales and Uniformization. Σ12 WellOrderings and Σ12 WellFounded Relations. Borel Codes. Exercises. Historical Notes. XII Table of Contents 26. The Real Line . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 511 Random and Cohen reals. Solovay Sets of Reals. The Lévy Collapse. Solovay’s Theorem. Lebesgue Measurability of Σ12 Sets. Ramsey Sets of Reals and Mathias Forcing. Measure and Category. Exercises. Historical Notes. Part III. Selected Topics 27. Combinatorial Principles in L . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545 The Fine Structure Theory. The Principle κ . The Jensen Hierarchy. Projecta, Standard Codes and Standard Parameters. Diamond Principles. Trees in L. Canonical Functions on ω1 . Exercises. Historical Notes. 28. More Applications of Forcing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 557 A Nonconstructible ∆13 Real. Namba Forcing. A Cohen Real Adds a Suslin Tree. Consistency of Borel’s Conjecture. κ+ Aronszajn Trees. Exercises. Historical Notes. 29. More Combinatorial Set Theory . . . . . . . . . . . . . . . . . . . . . . . . . . 573 Ramsey Theory. Gaps in ω ω . The Open Coloring Axiom. Almost Disjoint Subsets of ω1 . Functions from ω1 into ω. Exercises. Historical Notes. 30. Complete Boolean Algebras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 585 Measure Algebras. Cohen Algebras. Suslin Algebras. Simple Algebras. Inﬁnite Games on Boolean Algebras. Exercises. Historical Notes. 31. Proper Forcing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 601 Deﬁnition and Examples. Iteration of Proper Forcing. The Proper Forcing Axiom. Applications of PFA. Exercises. Historical Notes. 32. More Descriptive Set Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 615 Π11 Equivalence Relations. Σ11 Equivalence Relations. Constructible Reals and Perfect Sets. Projective Sets and Large Cardinals. Universally Baire sets. Exercises. Historical Notes. 33. Determinacy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 627 Determinacy and Choice. Some Consequences of AD. AD and Large Cardinals. Projective Determinacy. Consistency of AD. Exercises. Historical Notes. 34. Supercompact Cardinals and the Real Line . . . . . . . . . . . . . . . 647 Woodin Cardinals. Semiproper Forcing. The Model L(R). Stationary Tower Forcing. Weakly Homogeneous Trees. Exercises. Historical Notes. 35. Inner Models for Large Cardinals . . . . . . . . . . . . . . . . . . . . . . . . . 659 The Core Model. The Covering Theorem for K. The Covering Theorem for L[U ]. The Core Model for Sequences of Measures. Up to a Strong Cardinal. Inner Models for Woodin Cardinals. Exercises. Historical Notes. Table of Contents XIII 36. Forcing and Large Cardinals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 669 Violating GCH at a Measurable Cardinal. The Singular Cardinal Problem. Violating SCH at ℵω . Radin Forcing. Stationary Tower Forcing. Exercises. Historical Notes. 37. Martin’s Maximum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 681 RCS iteration of semiproper forcing. Consistency of MM. Applications of MM. Reﬂection Principles. Forcing Axioms. Exercises. Historical Notes. 38. More on Stationary Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 695 The Nonstationary Ideal on ℵ1 . Saturation and Precipitousness. Reﬂection. Stationary Sets in Pκ (λ). Mutually Stationary Sets. Weak Squares. Exercises. Historical Notes. Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 707 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 733 Name Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 743 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 749 This page intentionally left blank Part I Basic Set Theory This page intentionally left blank 1. Axioms of Set Theory Axioms of ZermeloFraenkel 1.1. Axiom of Extensionality. If X and Y have the same elements, then X =Y. 1.2. Axiom of Pairing. For any a and b there exists a set {a, b} that contains exactly a and b. 1.3. Axiom Schema of Separation. If P is a property (with parameter p), then for any X and p there exists a set Y = {u ∈ X : P (u, p)} that contains all those u ∈ X that have property P . 1.4. Axiom of Union. For any X there exists a set Y = X, the union of all elements of X. 1.5. Axiom of Power Set. For any X there exists a set Y = P (X), the set of all subsets of X. 1.6. Axiom of Inﬁnity. There exists an inﬁnite set. 1.7. Axiom Schema of Replacement. If a class F is a function, then for any X there exists a set Y = F (X) = {F (x) : x ∈ X}. 1.8. Axiom of Regularity. Every nonempty set has an ∈minimal element. 1.9. Axiom of Choice. Every family of nonempty sets has a choice function. The theory with axioms 1.1–1.8 is the ZermeloFraenkel axiomatic set theory ZF; ZFC denotes the theory ZF with the Axiom of Choice. Why Axiomatic Set Theory? Intuitively, a set is a collection of all elements that satisfy a certain given property. In other words, we might be tempted to postulate the following rule of formation for sets. 4 Part I. Basic Set Theory 1.10. Axiom Schema of Comprehension (false). If P is a property, then there exists a set Y = {x : P (x)}. This principle, however, is false: 1.11. Russell’s Paradox. Consider the set S whose elements are all those (and only those) sets that are not members of themselves: S = {X : X ∈ / X}. Question: Does S belong to S? If S belongs to S, then S is not a member of itself, and so S ∈ / S. On the other hand, if S ∈ / S, then S belongs to S. In either case, we have a contradiction. Thus we must conclude that {X : X ∈ / X} is not a set, and we must revise the intuitive notion of a set. The safe way to eliminate paradoxes of this type is to abandon the Schema of Comprehension and keep its weak version, the Schema of Separation: If P is a property, then for any X there exists a set Y = {x ∈ X : P (x)}. Once we give up the full Comprehension Schema, Russell’s Paradox is no longer a threat; moreover, it provides this useful information: The set of all sets does not exist. (Otherwise, apply the Separation Schema to the property x∈ / x.) In other words, it is the concept of the set of all sets that is paradoxical, not the idea of comprehension itself. Replacing full Comprehension by Separation presents us with a new problem. The Separation Axioms are too weak to develop set theory with its usual operations and constructions. Notably, these axioms are not suﬃcient to prove that, e.g., the union X ∪ Y of two sets exists, or to deﬁne the notion of a real number. Thus we have to add further construction principles that postulate the existence of sets obtained from other sets by means of certain operations. The axioms of ZFC are generally accepted as a correct formalization of those principles that mathematicians apply when dealing with sets. Language of Set Theory, Formulas The Axiom Schema of Separation as formulated above uses the vague notion of a property. To give the axioms a precise form, we develop axiomatic set theory in the framework of the ﬁrst order predicate calculus. Apart from the equality predicate =, the language of set theory consists of the binary predicate ∈, the membership relation. 1. Axioms of Set Theory 5 The formulas of set theory are built up from the atomic formulas x ∈ y, x=y by means of connectives ϕ ∧ ψ, ϕ ∨ ψ, ¬ϕ, ϕ → ψ, ϕ↔ψ (conjunction, disjunction, negation, implication, equivalence), and quantiﬁers ∀x ϕ, ∃x ϕ. In practice, we shall use in formulas other symbols, namely deﬁned predicates, operations, and constants, and even use formulas informally; but it will be tacitly understood that each such formula can be written in a form that only involves ∈ and = as nonlogical symbols. Concerning formulas with free variables, we adopt the notational convention that all free variables of a formula ϕ(u1 , . . . , un ) are among u1 , . . . , un (possibly some ui are not free, or even do not occur, in ϕ). A formula without free variables is called a sentence. Classes Although we work in ZFC which, unlike alternative axiomatic set theories, has only one type of object, namely sets, we introduce the informal notion of a class. We do this for practical reasons: It is easier to manipulate classes than formulas. If ϕ(x, p1 , . . . , pn ) is a formula, we call C = {x : ϕ(x, p1 , . . . , pn )} a class. Members of the class C are all those sets x that satisfy ϕ(x, p1 , . . . , pn ): x∈C if and only if ϕ(x, p1 , . . . , pn ). We say that C is deﬁnable from p1 , . . . , pn ; if ϕ(x) has no parameters pi then the class C is deﬁnable. Two classes are considered equal if they have the same elements: If C = {x : ϕ(x, p1 , . . . , pn )}, D = {x : ψ(x, q1 , . . . , qm )}, then C = D if and only if for all x ϕ(x, p1 , . . . , pn ) ↔ ψ(x, q1 , . . . , qm ). 6 Part I. Basic Set Theory The universal class, or universe, is the class of all sets: V = {x : x = x}. We deﬁne inclusion of classes (C is a subclass of D) C ⊂ D if and only if for all x, x ∈ C implies x ∈ D, and the following operations on classes: C ∩ D = {x : x ∈ C and x ∈ D}, C ∪ D = {x : x ∈ C or x ∈ D}, C − D = {x : x ∈ C and x ∈ / D}, C = {x : x ∈ S for some S ∈ C} = {S : S ∈ C}. Every set can be considered a class. If S is a set, consider the formula x ∈ S and the class {x : x ∈ S}. That the set S is uniquely determined by its elements follows from the Axiom of Extensionality. A class that is not a set is a proper class. Extensionality If X and Y have the same elements, then X = Y : ∀u (u ∈ X ↔ u ∈ Y ) → X = Y. The converse, namely, if X = Y then u ∈ X ↔ u ∈ Y , is an axiom of predicate calculus. Thus we have X=Y if and only if ∀u (u ∈ X ↔ u ∈ Y ). The axiom expresses the basic idea of a set: A set is determined by its elements. Pairing For any a and b there exists a set {a, b} that contains exactly a and b: ∀a ∀b ∃c ∀x (x ∈ c ↔ x = a ∨ x = b). 1. Axioms of Set Theory 7 By Extensionality, the set c is unique, and we can deﬁne the pair {a, b} = the unique c such that ∀x (x ∈ c ↔ x = a ∨ x = b). The singleton {a} is the set {a} = {a, a}. Since {a, b} = {b, a}, we further deﬁne an ordered pair (a, b) so as to satisfy the following condition: (1.1) (a, b) = (c, d) if and only if a = c and b = d. For the formal deﬁnition of an ordered pair, we take (a, b) = {{a}, {a, b}}. We leave the veriﬁcation of (1.1) to the reader (Exercise 1.1). We further deﬁne ordered triples, quadruples, etc., as follows: (a, b, c) = ((a, b), c), (a, b, c, d) = ((a, b, c), d), .. . (a1 , . . . , an+1 ) = ((a1 , . . . , an ), an+1 ). It follows that two ordered ntuples (a1 , . . . , an ) and (b1 , . . . , bn ) are equal if and only if a1 = b1 , . . . , an = bn . Separation Schema Let ϕ(u, p) be a formula. For any X and p, there exists a set Y = {u ∈ X : ϕ(u, p)}: (1.2) ∀X ∀p ∃Y ∀u (u ∈ Y ↔ u ∈ X ∧ ϕ(u, p)). For each formula ϕ(u, p), the formula (1.2) is an Axiom (of Separation). The set Y in (1.2) is unique by Extensionality. Note that a more general version of Separation Axioms can be proved using ordered ntuples: Let ψ(u, p1 , . . . , pn ) be a formula. Then (1.3) ∀X ∀p1 . . . ∀pn ∃Y ∀u (u ∈ Y ↔ u ∈ X ∧ ψ(u, p1 , . . . , pn )). 8 Part I. Basic Set Theory Simply let ϕ(u, p) be the formula ∃p1 , . . . ∃pn (p = (p1 , . . . , pn ) and ψ(u, p1 , . . . , pn )) and then, given X and p1 , . . . , pn , let Y = {u ∈ X : ϕ(u, (p1 , . . . , pn ))}. We can give the Separation Axioms the following form: Consider the class C = {u : ϕ(u, p1 , . . . , pn )}; then by (1.3) ∀X ∃Y (C ∩ X = Y ). Thus the intersection of a class C with any set is a set; or, we can say even more informally a subclass of a set is a set. One consequence of the Separation Axioms is that the intersection and the diﬀerence of two sets is a set, and so we can deﬁne the operations X ∩ Y = {u ∈ X : u ∈ Y } and X − Y = {u ∈ X : u ∈ / Y }. Similarly, it follows that the empty class ∅ = {u : u = u} is a set—the empty set ; this, of course, only under the assumption that at least one set X exists (because ∅ ⊂ X): ∃X (X = X). (1.4) We have not included (1.4) among the axioms, because it follows from the Axiom of Inﬁnity. Two sets X, Y are called disjoint if X ∩ Y = ∅. If C is a nonempty class of sets, we let C= {X : X ∈ C} = {u : u ∈ X for every X ∈ C}. Note that C is a set (it is a subset of any X ∈ C). Also, X ∩ Y = {X, Y }. Another consequence of the Separation Axioms is that the universal class V is a proper class; otherwise, S = {x ∈ V : x ∈ / x} would be a set. 1. Axioms of Set Theory Union For any X there exists a set Y = (1.5) X: ∀X ∃Y ∀u (u ∈ Y ↔ ∃z (z ∈ X ∧ u ∈ z)). Let us introduce the abbreviations (∃z ∈ X) ϕ for ∃z (z ∈ X ∧ ϕ), (∀z ∈ X) ϕ for ∀z (z ∈ X → ϕ). and By (1.5), for every X there is a unique set Y = {u : (∃z ∈ X) u ∈ z} = {z : z ∈ X} = X, the union of X. Now we can deﬁne X ∪ Y = {X, Y }, X ∪ Y ∪ Z = (X ∪ Y ) ∪ Z, and also {a, b, c} = {a, b} ∪ {c}, and in general {a1 , . . . , an } = {a1 } ∪ . . . ∪ {an }. We also let X Y = (X − Y ) ∪ (Y − X), the symmetric diﬀerence of X and Y . Power Set For any X there exists a set Y = P (X): ∀X ∃Y ∀u (u ∈ Y ↔ u ⊂ X). A set U is a subset of X, U ⊂ X, if ∀z (z ∈ U → z ∈ X). If U ⊂ X and U = X, then U is a proper subset of X. The set of all subsets of X, P (X) = {u : u ⊂ X}, is called the power set of X. etc., 9 10 Part I. Basic Set Theory Using the Power Set Axiom we can deﬁne other basic notions of set theory. The product of X and Y is the set of all pairs (x, y) such that x ∈ X and y ∈ Y: X × Y = {(x, y) : x ∈ X and y ∈ Y }. (1.6) The notation {(x, y) : . . . } in (1.6) is justiﬁed because {(x, y) : ϕ(x, y)} = {u : ∃x ∃y (u = (x, y) and ϕ(x, y))}. The product X × Y is a set because X × Y ⊂ P P (X ∪ Y ). Further, we deﬁne X × Y × Z = (X × Y ) × Z, and in general X1 × . . . × Xn+1 = (X1 × . . . × Xn ) × Xn+1 . Thus X1 × . . . × Xn = {(x1 , . . . , xn ) : x1 ∈ X1 ∧ . . . ∧ xn ∈ Xn }. We also let Xn = X × . . . × X . n times An nary relation R is a set of ntuples. R is a relation on X if R ⊂ X n . It is customary to write R(x1 , . . . , xn ) instead of (x1 , . . . , xn ) ∈ R, and in case that R is binary, then we also use xRy for (x, y) ∈ R. If R is a binary relation, then the domain of R is the set dom(R) = {u : ∃v (u, v) ∈ R}, and the range of R is the set ran(R) = {v : ∃u (u, v) ∈ R}. Note that dom(R) and ran(R) are sets because dom(R) ⊂ R, ran(R) ⊂ R. The ﬁeld of a relation R is the set ﬁeld(R) = dom(R) ∪ ran(R). 1. Axioms of Set Theory 11 In general, we call a class R an nary relation if all its elements are ntuples; in other words, if R ⊂ V n = the class of all ntuples, where C n (and C × D) is deﬁned in the obvious way. A binary relation f is a function if (x, y) ∈ f and (x, z) ∈ f implies y = z. The unique y such that (x, y) ∈ f is the value of f at x; we use the standard notation y = f (x) or its variations f : x → y, y = fx , etc. for (x, y) ∈ f . f is a function on X if X = dom(f ). If dom(f ) = X n , then f is an nary function on X. f is a function from X to Y , f : X → Y, if dom(f ) = X and ran(f ) ⊂ Y . The set of all functions from X to Y is denoted by Y X . Note that Y X is a set: Y X ⊂ P (X × Y ). If Y = ran(f ), then f is a function onto Y . A function f is onetoone if f (x) = f (y) implies x = y. An nary operation on X is a function f : X n → X. The restriction of a function f to a set X (usually a subset of dom(f )) is the function f X = {(x, y) ∈ f : x ∈ X}. A function g is an extension of a function f if g ⊃ f , i.e., dom(f ) ⊂ dom(g) and g(x) = f (x) for all x ∈ dom(f ). If f and g are functions such that ran(g) ⊂ dom(f ), then the composition of f and g is the function f ◦ g with domain dom(f ◦ g) = dom(g) such that (f ◦ g)(x) = f (g(x)) for all x ∈ dom(g). We denote the image of X by f either f “X or f (X): f “X = f (X) = {y : (∃x ∈ X) y = f (x)}, and the inverse image by f−1 (X) = {x : f (x) ∈ X}. If f is onetoone, then f −1 denotes the inverse of f : f −1 (x) = y if and only if x = f (y). The previous deﬁnitions can also be applied to classes instead of sets. A class F is a function if it is a relation such that (x, y) ∈ F and (x, z) ∈ F 12 Part I. Basic Set Theory implies y = z. For example, F “C or F (C) denotes the image of the class C by the function F . It should be noted that a function is often called a mapping or a correspondence (and similarly, a set is called a family or a collection). An equivalence relation on a set X is a binary relation ≡ which is reﬂexive, symmetric, and transitive: For all x, y, z ∈ X, x ≡ x, x ≡ y implies y ≡ x, if x ≡ y and y ≡ z then x ≡ z. A family of sets is disjoint if any two of its members are disjoint. A partition of a set X is a disjoint family P of nonempty sets such that X = {Y : Y ∈ P }. Let ≡ be an equivalence relation on X. For every x ∈ X, let [x] = {y ∈ X : y ≡ x} (the equivalence class of x). The set X/≡ = {[x] : x ∈ X} is a partition of X (the quotient of X by ≡). Conversely, each partition P of X deﬁnes an equivalence relation on X: x≡y if and only if (∃Y ∈ P )(x ∈ Y and y ∈ Y ). If an equivalence relation is a class, then its equivalence classes may be proper classes. In Chapter 6 we shall introduce a trick that enables us to handle equivalence classes as if they were sets. Inﬁnity There exists an inﬁnite set. To give a precise formulation of the Axiom of Inﬁnity, we have to deﬁne ﬁrst the notion of ﬁniteness. The most obvious deﬁnition of ﬁniteness uses the notion of a natural number, which is as yet undeﬁned. We shall deﬁne natural numbers (as ﬁnite ordinals) in Chapter 2 and give only a quick treatment of natural numbers and ﬁniteness in the exercises below. In principle, it is possible to give a deﬁnition of ﬁniteness that does not mention numbers, but such deﬁnitions necessarily look artiﬁcial. We therefore formulate the Axiom of Inﬁnity diﬀerently: ∃S (∅ ∈ S ∧ (∀x ∈ S)x ∪ {x} ∈ S). We call a set S with the above property inductive. Thus we have: 1. Axioms of Set Theory 13 Axiom of Inﬁnity. There exists an inductive set. The axiom provides for the existence of inﬁnite sets. In Chapter 2 we show that an inductive set is inﬁnite (and that an inductive set exists if there exists an inﬁnite set). We shall introduce natural numbers and ﬁnite sets in Chapter 2, as a part of the introduction of ordinal numbers. In Exercises 1.3–1.9 we show an alternative approach. Replacement Schema If a class F is a function, then for every set X, F (X) is a set. For each formula ϕ(x, y, p), the formula (1.7) is an Axiom (of Replacement): (1.7) ∀x ∀y ∀z (ϕ(x, y, p) ∧ ϕ(x, z, p) → y = z) → ∀X ∃Y ∀y (y ∈ Y ↔ (∃x ∈ X) ϕ(x, y, p)). As in the case of Separation Axioms, we can prove the version of Replacement Axioms with several parameters: Replace p by p1 , . . . , pn . If F = {(x, y) : ϕ(x, y, p)}, then the premise of (1.7) says that F is a function, and we get the formulation above. We can also formulate the axioms in the following ways: If a class F is a function and dom(F ) is a set, then ran(F ) is a set. If a class F is a function, then ∀X ∃f (F X = f ). The remaining two axioms, Choice and Regularity, will by introduced in Chapters 5 and 6. Exercises 1.1. Verify (1.1). 1.2. There is no set X such that P (X) ⊂ X. Let N = T {X : X is inductive}. N is the smallest inductive set. Let us use the following notation: 0 = ∅, 1 = {0}, 2 = {0, 1}, 3 = {0, 1, 2}, .... If n ∈ N , let n + 1 = n ∪ {n}. Let us deﬁne < (on N ) by n < m if and only if n ∈ m. A set T is transitive if x ∈ T implies x ⊂ T . 14 Part I. Basic Set Theory 1.3. If X is inductive, then the set {x ∈ X : x ⊂ X} is inductive. Hence N is transitive, and for each n, n = {m ∈ N : m < n}. 1.4. If X is inductive, then the set {x ∈ X : x is transitive} is inductive. Hence every n ∈ N is transitive. 1.5. If X is inductive, then the set {x ∈ X : x is transitive and x ∈ / x} is inductive. Hence n ∈ / n and n = n + 1 for each n ∈ N . 1.6. If X is inductive, then {x ∈ X : x is transitive and every nonempty z ⊂ x has an ∈minimal element} is inductive (t is ∈minimal in z if there is no s ∈ z such that s ∈ t). 1.7. Every nonempty X ⊂ N has an ∈minimal element. [Pick n ∈ X and look at X ∩ n.] 1.8. If X is inductive then so is {x ∈ X : x = ∅ or x = y ∪ {y} for some y}. Hence each n = 0 is m + 1 for some m. 1.9 (Induction). Let A be a subset of N such that 0 ∈ A, and if n ∈ A then n + 1 ∈ A. Then A = N . A set X has n elements (where n ∈ N ) if there is a onetoone mapping of n onto X. A set is ﬁnite if it has n elements for some n ∈ N , and inﬁnite if it is not ﬁnite. A set S is Tﬁnite if every nonempty X ⊂ P (S) has a ⊂maximal element, i.e., u ∈ X such that there is no v ∈ X with u ⊂ v and u = v. S is Tinﬁnite if it is not Tﬁnite. (T is for Tarski.) 1.10. Each n ∈ N is Tﬁnite. 1.11. N is Tinﬁnite; the set N ⊂ P (N ) has no ⊂maximal element. 1.12. Every ﬁnite set is Tﬁnite. 1.13. Every inﬁnite set is Tinﬁnite. [If S is inﬁnite, consider X = {u ⊂ S : u is ﬁnite}.] 1.14. The Separation Axioms follow from the Replacement Schema. [Given ϕ, let F = {(x, x) : ϕ(x)}. Then {x ∈ X : ϕ(x)} = F (X), for every X.] 1.15. Instead of Union, Power Set, and Replacement Axioms consider the following weaker versions: S (1.8) ∀X ∃Y X ⊂Y, i.e., ∀X ∃Y (∀x ∈ X)(∀u ∈ x) u ∈ Y , (1.9) ∀X ∃Y P (X) ⊂ Y , i.e., ∀X ∃Y ∀u (u ⊂ X → u ∈ Y ), (1.10) If a class F is a function, then ∀X ∃Y F (X) ⊂ Y . Then axioms 1.4, 1.5, and 1.7 can be proved from (1.8), (1.9), and (1.10), using the Separation Schema (1.3). 1. Axioms of Set Theory 15 Historical Notes Set theory was invented by Georg Cantor. The ﬁrst attempt to consider inﬁnite sets is attributed to Bolzano (who introduced the term Menge). It was however Cantor who realized the signiﬁcance of onetoone functions between sets and introduced the notion of cardinality of a set. Cantor originated the theory of cardinal and ordinal numbers as well as the investigations of the topology of the real line. Much of the development in the ﬁrst four chapters follows Cantor’s work. The main reference to Cantor’s work is his collected works, Cantor [1932]. Another source of references to the early research in set theory is Hausdorﬀ’s book [1914]. Cantor started his investigations in [1874], where he proved that the set of all real numbers is uncountable, while the set of all algebraic reals is countable. In [1878] he gave the ﬁrst formulation of the celebrated Continuum Hypothesis. The axioms for set theory (except Replacement and Regularity) are due to Zermelo [1908]. The Replacement Schema is due to Fraenkel [1922a] and Skolem (see [1970], pp. 137–152). Exercises 1.12 and 1.13: Tarski [1925a]. This page intentionally left blank 2. Ordinal Numbers In this chapter we introduce ordinal numbers and prove the Transﬁnite Recursion Theorem. Linear and Partial Ordering Deﬁnition 2.1. A binary relation < on a set P is a partial ordering of P if: (i) p < p for any p ∈ P ; (ii) if p < q and q < r, then p < r. (P, <) is called a partially ordered set. A partial ordering < of P is a linear ordering if moreover (iii) p < q or p = q or q < p for all p, q ∈ P . If < is a partial (linear) ordering, then the relation ≤ (where p ≤ q if either p < q or p = q) is also called a partial (linear) ordering (and < is sometimes called a strict ordering). Deﬁnition 2.2. If (P, <) is a partially ordered set, X is a nonempty subset of P , and a ∈ P , then: a a a a a a a a is is is is is is is is a maximal element of X if a ∈ X and (∀x ∈ X) a < x; a minimal element of X if a ∈ X and (∀x ∈ X) x < a; the greatest element of X if a ∈ X and (∀x ∈ X) x ≤ a; the least element of X if a ∈ X and (∀x ∈ X) a ≤ x; an upper bound of X if (∀x ∈ X) x ≤ a; a lower bound of X if (∀x ∈ X) a ≤ x; the supremum of X if a is the least upper bound of X; the inﬁmum of X if a is the greatest lower bound of X. The supremum (inﬁmum) of X (if it exists) is denoted sup X (inf X). Note that if X is linearly ordered by <, then a maximal element of X is its greatest element (similarly for a minimal element). If (P, <) and (Q, <) are partially ordered sets and f : P → Q, then f is orderpreserving if x < y implies f (x) < f (y). If P and Q are linearly ordered, then an orderpreserving function is also called increasing. 18 Part I. Basic Set Theory A onetoone function of P onto Q is an isomorphism of P and Q if both f and f −1 are orderpreserving; (P, <) is then isomorphic to (Q, <). An isomorphism of P onto itself is an automorphism of (P, <). WellOrdering Deﬁnition 2.3. A linear ordering < of a set P is a wellordering if every nonempty subset of P has a least element. The concept of wellordering is of fundamental importance. It is shown below that wellordered sets can be compared by their lengths; ordinal numbers will be introduced as ordertypes of wellordered sets. Lemma 2.4. If (W, <) is a wellordered set and f : W → W is an increasing function, then f (x) ≥ x for each x ∈ W . Proof. Assume that the set X = {x ∈ W : f (x) < x} is nonempty and let z be the least element of X. If w = f (z), then f (w) < w, a contradiction. Corollary 2.5. The only automorphism of a wellordered set is the identity. Proof. By Lemma 2.4, f (x) ≥ x for all x, and f −1 (x) ≥ x for all x. Corollary 2.6. If two wellordered sets W1 , W2 are isomorphic, then the isomorphism of W1 onto W2 is unique. If W is a wellordered set and u ∈ W , then {x ∈ W : x < u} is an initial segment of W (given by u). Lemma 2.7. No wellordered set is isomorphic to an initial segment of itself. Proof. If ran(f ) = {x : x < u}, then f (u) < u, contrary to Lemma 2.4. Theorem 2.8. If W1 and W2 are wellordered sets, then exactly one of the following three cases holds: (i) W1 is isomorphic to W2 ; (ii) W1 is isomorphic to an initial segment of W2 ; (iii) W2 is isomorphic to an initial segment of W1 . Proof. For u ∈ Wi , (i = 1, 2), let Wi (u) denote the initial segment of Wi given by u. Let f = {(x, y) ∈ W1 × W2 : W1 (x) is isomorphic to W2 (y)}. Using Lemma 2.7, it is easy to see that f is a onetoone function. If h is an isomorphism between W1 (x) and W2 (y), and x < x, then W1 (x ) and W2 (h(x )) are isomorphic. It follows that f is orderpreserving. 2. Ordinal Numbers 19 If dom(f ) = W1 and ran(f ) = W2 , then case (i) holds. If y1 < y2 and y2 ∈ ran(f ), then y1 ∈ ran(f ). Thus if ran(f ) = W2 and y0 is the least element of W2 − ran(f ), we have ran(f ) = W2 (y0 ). Necessarily, dom(f ) = W1 , for otherwise we would have (x0 , y0 ) ∈ f , where x0 = the least element of W1 − dom(f ). Thus case (ii) holds. Similarly, if dom(f ) = W1 , then case (iii) holds. In view of Lemma 2.7, the three cases are mutually exclusive. If W1 and W2 are isomorphic, we say that they have the same ordertype. Informally, an ordinal number is the ordertype of a wellordered set. We shall now give a formal deﬁnition of ordinal numbers. Ordinal Numbers The idea is to deﬁne ordinal numbers so that α<β if and only if α ∈ β, and α = {β : β < α}. Deﬁnition 2.9. A set T is transitive if every element of T is a subset of T . (Equivalently, T ⊂ T , or T ⊂ P (T ).) Deﬁnition 2.10. A set is an ordinal number (an ordinal ) if it is transitive and wellordered by ∈. We shall denote ordinals by lowercase Greek letters α, β, γ, . . . . The class of all ordinals is denoted by Ord. We deﬁne α < β if and only if α ∈ β. Lemma 2.11. (i) (ii) (iii) (iv) 0 = ∅ is an ordinal. If α is an ordinal and β ∈ α, then β is an ordinal. If α = β are ordinals and α ⊂ β, then α ∈ β. If α, β are ordinals, then either α ⊂ β or β ⊂ α. Proof. (i), (ii) by deﬁnition. (iii) If α ⊂ β, let γ be the least element of the set β − α. Since α is transitive, it follows that α is the initial segment of β given by γ. Thus α = {ξ ∈ β : ξ < γ} = γ, and so α ∈ β. (iv) Clearly, α ∩ β is an ordinal, α ∩ β = γ. We have γ = α or γ = β, for otherwise γ ∈ α, and γ ∈ β, by (iii). Then γ ∈ γ, which contradicts the deﬁnition of an ordinal (namely that ∈ is a strict ordering of α). 20 Part I. Basic Set Theory Using Lemma 2.11 one gets the following facts about ordinal numbers (the proofs are routine): (2.1) < is a linear ordering of the class Ord. (2.2) For each α, α = {β : β < α}. (2.3) If C is a nonempty class of ordinals, then C is an ordinal, C ∈ C and C = inf C. (2.4) If X is a nonempty set of ordinals, then X is an ordinal, and X = sup X. (2.5) For every α, α ∪ {α} is an ordinal and α ∪ {α} = inf{β : β > α}. We thus deﬁne α + 1 = α ∪ {α} (the successor of α). In view of (2.4), the class Ord is a proper class; otherwise, consider sup Ord + 1. We can now prove that the above deﬁnition of ordinals provides us with ordertypes of wellordered sets. Theorem 2.12. Every wellordered set is isomorphic to a unique ordinal number. Proof. The uniqueness follows from Lemma 2.7. Given a wellordered set W , we ﬁnd an isomorphic ordinal as follows: Deﬁne F (x) = α if α is isomorphic to the initial segment of W given by x. If such an α exists, then it is unique. By the Replacement Axioms, F (W ) is a set. For each x ∈ W , such an α exists (otherwise consider the least x for which such an α does not exist). If γ is the least γ ∈ / F (W ), then F (W ) = γ and we have an isomorphism of W onto γ. If α = β + 1, then α is a successor ordinal. If α is not a successor ordinal, then α = sup{β : β < α} = α; α is called a limit ordinal. We also consider 0 a limit ordinal and deﬁne sup ∅ = 0. The existence of limit ordinals other than 0 follows from the Axiom of Inﬁnity; see Exercise 2.3. Deﬁnition 2.13 (Natural Numbers). We denote the least nonzero limit ordinal ω (or N ). The ordinals less than ω (elements of N ) are called ﬁnite ordinals, or natural numbers. Speciﬁcally, 0 = ∅, 1 = 0 + 1, 2 = 1 + 1, 3 = 2 + 1, etc. A set X is ﬁnite if there is a onetoone mapping of X onto some n ∈ N . X is inﬁnite if it is not ﬁnite. We use letters n, m, l, k, j, i (most of the time) to denote natural numbers. 2. Ordinal Numbers 21 Induction and Recursion Theorem 2.14 (Transﬁnite Induction). Let C be a class of ordinals and assume that : (i) 0 ∈ C; (ii) if α ∈ C, then α + 1 ∈ C; (iii) if α is a nonzero limit ordinal and β ∈ C for all β < α, then α ∈ C. Then C is the class of all ordinals. Proof. Otherwise, let α be the least ordinal α ∈ / C and apply (i), (ii), or (iii). A function whose domain is the set N is called an (inﬁnite) sequence (A sequence in X is a function f : N → X.) The standard notation for a sequence is an : n < ω or variants thereof. A ﬁnite sequence is a function s such dom(s) = {i : i < n} for some n ∈ N ; then s is a sequence of length n. A transﬁnite sequence is a function whose domain is an ordinal: aξ : ξ < α. It is also called an αsequence or a sequence of length α. We also say that a sequence aξ : ξ < α is an enumeration of its range {aξ : ξ < α}. If s is a sequence of length α, then s x or simply sx denotes the sequence of length α + 1 that extends s and whose αth term is x: s x = sx = s ∪ {(α, x)}. Sometimes we shall call a “sequence” aα : α ∈ Ord a function (a proper class) on Ord . “Deﬁnition by transﬁnite recursion” usually takes the following form: Given a function G (on the class of transﬁnite sequences), then for every θ there exists a unique θsequence aα : α < θ such that aα = G(aξ : ξ < α) for every α < θ. We shall give a general version of this theorem, so that we can also construct sequences aα : α ∈ Ord . 22 Part I. Basic Set Theory Theorem 2.15 (Transﬁnite Recursion). Let G be a function (on V ), then (2.6) below deﬁnes a unique function F on Ord such that F (α) = G(F α) for each α. In other words, if we let aα = F (α), then for each α, aα = G(aξ : ξ < α). (Note that we tacitly use Replacement: F α is a set for each α.) Corollary 2.16. Let X be a set and θ an ordinal number. For every function G on the set of all transﬁnite sequences in X of length < θ such that ran(G) ⊂ X there exists a unique θsequence aα : α < θ in X such that aα = G(aξ : ξ < α) for every α < θ. Proof. Let (2.6) F (α) = x ↔ there is a sequence aξ : ξ < α such that: (i) (∀ξ < α) aξ = G(aη : η < ξ); (ii) x = G(aξ : ξ < α). For every α, if there is an αsequence that satisﬁes (i), then such a sequence is unique: If aξ : ξ < α and bξ : ξ < α are two αsequences satisfying (i), one shows aξ = bξ by induction on ξ. Thus F (α) is determined uniquely by (ii), and therefore F is a function. It follows, again by induction, that for each α there is an αsequence that satisﬁes (i) (at limit steps, we use Replacement to get the αsequence as the union of all the ξsequences, ξ < α). Thus F is deﬁned for all α ∈ Ord. It obviously satisﬁes F (α) = G(F α). If F is any function on Ord that satisﬁes F (α) = G(F α) then it follows by induction that F (α) = F (α) for all α. Deﬁnition 2.17. Let α > 0 be a limit ordinal and let γξ : ξ < α be a nondecreasing sequence of ordinals (i.e., ξ < η implies γξ ≤ γη ). We deﬁne the limit of the sequence by limξ→α γξ = sup{γξ : ξ < α}. A sequence of ordinals γα : α ∈ Ord is normal if it is increasing and continuous, i.e., for every limit α, γα = limξ→α γξ . 2. Ordinal Numbers 23 Ordinal Arithmetic We shall now deﬁne addition, multiplication and exponentiation of ordinal numbers, using Transﬁnite Recursion. Deﬁnition 2.18 (Addition). For all ordinal numbers α (i) α + 0 = α, (ii) α + (β + 1) = (α + β) + 1, for all β, (iii) α + β = limξ→β (α + ξ) for all limit β > 0. Deﬁnition 2.19 (Multiplication). For all ordinal numbers α (i) α · 0 = 0, (ii) α · (β + 1) = α · β + α for all β, (iii) α · β = limξ→β α · ξ for all limit β > 0. Deﬁnition 2.20 (Exponentiation). For all ordinal numbers α (i) α0 = 1, (ii) αβ+1 = αβ · α for all β, (iii) αβ = limξ→β αξ for all limit β > 0. As deﬁned, the operations α + β, α · β and αβ are normal functions in the second variable β. Their properties can be proved by transﬁnite induction. For instance, + and · are associative: Lemma 2.21. For all ordinals α, β and γ, (i) α + (β + γ) = (α + β) + γ, (ii) α · (β · γ) = (α · β) · γ. Proof. By induction on γ. Neither + nor · are commutative: 1 + ω = ω = ω + 1, 2 · ω = ω = ω · 2 = ω + ω. Ordinal sums and products can be also deﬁned geometrically, as can sums and products of arbitrary linear orders: Deﬁnition 2.22. Let (A, <A ) and (B, <B ) be disjoint linearly ordered sets. The sum of these linear orders is the set A ∪ B with the ordering deﬁned as follows: x < y if and only if (i) x, y ∈ A and x <A y, or (ii) x, y ∈ B and x <B y, or (iii) x ∈ A and y ∈ B. 24 Part I. Basic Set Theory Deﬁnition 2.23. Let (A, <) and (B, <) be linearly ordered sets. The product of these linear orders is the set A × B with the ordering deﬁned by (a1 , b1 ) < (a2 , b2 ) if and only if either b1 < b2 or (b1 = b2 and a1 < a2 ). Lemma 2.24. For all ordinals α and β, α + β and α · β are, respectively, isomorphic to the sum and to the product of α and β. Proof. By induction on β. Ordinal sums and products have some properties of ordinary addition and multiplication of integers. For instance: Lemma 2.25. (i) (ii) (iii) (iv) If β < γ then α + β < α + γ. If α < β then there exists a unique δ such that α + δ = β. If β < γ and α > 0, then α · β < α · γ. If α > 0 and γ is arbitrary, then there exist a unique β and a unique ρ < α such that γ = α · β + ρ. (v) If β < γ and α > 1, then αβ < αγ . Proof. (i), (iii) and (v) are proved by induction on γ. (ii) Let δ be the ordertype of the set {ξ : α ≤ ξ < β}; δ is unique by (i). (iv) Let β be the greatest ordinal such that α · β ≤ γ. For more, see Exercises 2.10 and 2.11. Theorem 2.26 (Cantor’s Normal Form Theorem). Every ordinal α > 0 can be represented uniquely in the form α = ω β1 · k1 + . . . + ω βn · kn , where n ≥ 1, α ≥ β1 > . . . > βn , and k1 , . . . , kn are nonzero natural numbers. Proof. By induction on α. For α = 1 we have 1 = ω 0 · 1; for arbitrary α > 0 let β be the greatest ordinal such that ω β ≤ α. By Lemma 2.25(iv) there exists a unique δ and a unique ρ < ω β such that α = ω β · δ + ρ; this δ must necessarily be ﬁnite. The uniqueness of the normal form is proved by induction. In the normal form it is possible to have α = ωα ; see Exercise 2.12. The least ordinal with this property is called ε0 . 2. Ordinal Numbers 25 WellFounded Relations Now we shall deﬁne an important generalization of wellordered sets. A binary relation E on a set P is wellfounded if every nonempty X ⊂ P has an Eminimal element, that is a ∈ X such that there is no x ∈ X with x E a. Clearly, a wellordering of P is a wellfounded relation. Given a wellfounded relation E on a set P , we can deﬁne the height of E, and assign to each x ∈ P an ordinal number, the rank of x in E. Theorem 2.27. If E is a wellfounded relation on P , then there exists a unique function ρ from P into the ordinals such that for all x ∈ P , (2.7) ρ(x) = sup{ρ(y) + 1 : y E x}. The range of ρ is an initial segment of the ordinals, thus an ordinal number. This ordinal is called the height of E. Proof. We shall deﬁne a function ρ satisfying (2.7) and then prove its uniqueness. By induction, let P0 = ∅, Pα+1 = {x ∈ P : ∀y (y E x → y ∈ Pα )}, Pα = Pξ if α is a limit ordinal. ξ<α Let θ be the least ordinal such that Pθ+1 = Pθ (such θ exists by Replacement). First, it should be easy to see that Pα ⊂ Pα+1 for each α (by induction). Thus P0 ⊂ P1 ⊂ . . . ⊂ Pθ . We claim that Pθ = P . Otherwise, let a be an Eminimal element of P − Pθ . It follows that each x E a is in Pθ , and so a ∈ Pθ+1 , a contradiction. Now we deﬁne ρ(x) as the least α such that x ∈ Pα+1 . It is obvious that if x E y, then ρ(x) < ρ(y), and (2.7) is easily veriﬁed. The ordinal θ is the height of E. The uniqueness of ρ is established as follows: Let ρ be another function satisfying (2.7) and consider an Eminimal element of the set {x ∈ P : ρ(x) = ρ (x)}. Exercises 2.1. The relation “(P, <) is isomorphic to (Q, <)” is an equivalence relation (on the class of all partially ordered sets). 2.2. α is a limit ordinal if and only if β < α implies β + 1 < α, for every β. T 2.3. If a set X is inductive, then X ∩ Ord is inductive. The set N = {X : X is inductive} is the least limit ordinal = 0. 26 Part I. Basic Set Theory 2.4. (Without the Axiom of Inﬁnity). Let ω = least limit α = 0 if it exists, ω = Ord otherwise. Prove that the following statements are equivalent: (i) There exists an inductive set. (ii) There exists an inﬁnite set. (iii) ω is a set. [For (ii) → (iii), apply Replacement to the set of all ﬁnite subsets of X.] 2.5. If W is a wellordered set, then there exists no sequence an : n ∈ N in W such that a0 > a1 > a2 > . . .. 2.6. There are arbitrarily large limit ordinals; i.e., ∀α ∃β > α (β is a limit). [Consider limn→ω αn , where αn+1 = αn + 1.] 2.7. Every normal sequence γα : α ∈ Ord has arbitrarily large ﬁxed points, i.e., α such that γα = α. [Let αn+1 = γαn , and α = limn→ω αn .] 2.8. For all α, β and γ, (i) α · (β + γ) = α · β + α · γ, (ii) αβ+γ = αβ · αγ , (iii) (αβ )γ = αβ·γ . 2.9. (i) Show that (ω + 1) · 2 = ω · 2 + 1 · 2. (ii) Show that (ω · 2)2 = ω 2 · 22 . 2.10. If α < β then α + γ ≤ β + γ, α · γ ≤ β · γ, and αγ ≤ β γ , 2.11. Find α, β, γ such that (i) α < β and α + γ = β + γ, (ii) α < β and α · γ = β · γ, (iii) α < β and αγ = β γ . 2.12. Let ε0 = limn→ω αn where α0 = ω and αn+1 = ω αn for all n. Show that ε0 is the least ordinal ε such that ω ε = ε. A limit ordinal γ > 0 is called indecomposable if there exist no α < γ and β < γ such that α + β = γ. 2.13. A limit ordinal γ > 0 is indecomposable if and only if α + γ = γ for all α < γ if and only if γ = ω α for some α. 2.14. If E is a wellfounded relation on P , then there is no sequence an : n ∈ N in P such that a1 E a0 , a2 E a1 , a3 E a2 , . . . . 2.15 (WellFounded Recursion). Let E be a wellfounded relation on a set P , and let G be a function. Then there exists a function F such that for all x ∈ P , F (x) = G(x, F {y ∈ P : y E x}). Historical Notes The theory of wellordered sets was developed by Cantor, who also introduced transﬁnite induction. The idea of identifying an ordinal number with the set of smaller ordinals is due to Zermelo and von Neumann. 3. Cardinal Numbers Cardinality Two sets X, Y have the same cardinality (cardinal number, cardinal), (3.1) X = Y , if there exists a onetoone mapping of X onto Y . The relation (3.1) is an equivalence relation. We assume that we can assign to each set X its cardinal number X so that two sets are assigned the same cardinal just in case they satisfy condition (3.1). Cardinal numbers can be deﬁned either using the Axiom of Regularity (via equivalence classes of (3.1)), or using the Axiom of Choice. In this chapter we deﬁne cardinal numbers of wellorderable sets; as it follows from the Axiom of Choice that every set can be wellordered, this deﬁnes cardinals in ZFC. We recall that a set X is ﬁnite if X = n for some n ∈ N ; then X is said to have n elements. Clearly, n = m if and only if n = m, and so we deﬁne ﬁnite cardinals as natural numbers, i.e., n = n for all n ∈ N . The ordering of cardinal numbers is deﬁned as follows: (3.2) X ≤ Y  if there exists a onetoone mapping of X into Y . We also deﬁne the strict ordering X < Y  to mean that X ≤ Y  while X = Y . The relation ≤ in (3.2) is clearly transitive. Theorem 3.2 below shows that it is indeed a partial ordering, and it follows from the Axiom of Choice that the ordering is linear—any two sets are comparable in this ordering. The concept of cardinality is central to the study of inﬁnite sets. The following theorem tells us that this concept is not trivial: Theorem 3.1 (Cantor). For every set X, X < P (X). Proof. Let f be a function from X into P (X). The set Y = {x ∈ X : x ∈ / f (x)} is not in the range of f : If z ∈ X were such that f (z) = Y , then z ∈ Y if and only if z ∈ / Y , a contradiction. Thus f is not a function of X onto P (X). Hence P (X) = X. 28 Part I. Basic Set Theory The function f (x) = {x} is a onetoone function of X into P (X) and so X ≤ P (X). It follows that X < P (X). In view of the following theorem, < is a partial ordering of cardinal numbers. Theorem 3.2 (CantorBernstein). If A ≤ B and B ≤ A, then A = B. Proof. If f1 : A → B and f2 : B → A are onetoone, then if we let B = f2 (B) and A1 = f2 (f1 (A)), we have A1 ⊂ B ⊂ A and A1  = A. Thus we may assume that A1 ⊂ B ⊂ A and that f is a onetoone function of A onto A1 ; we will show that A = B. We deﬁne (by induction) for all n ∈ N : A0 = A, An+1 = f (An ), B0 = B, Bn+1 = f (Bn ). Let g be the function on A deﬁned as follows: g(x) = f (x) x if x ∈ An − Bn for some n, otherwise. Then g is a onetoone mapping of A onto B, as the reader will easily verify. Thus A = B. The arithmetic operations on cardinals are deﬁned as follows: (3.3) κ + λ = A ∪ B where A = κ, B = λ, and A, B are disjoint, κ · λ = A × B where A = κ, B = λ, κ = A  where A = κ, B = λ. λ B Naturally, the deﬁnitions in (3.3) are meaningful only if they are independent of the choice of A and B. Thus one has to check that, e.g., if A = A  and B = B , then A × B = A × B . Lemma 3.3. If A = κ, then P (A) = 2κ . Proof. For every X ⊂ A, let χX be the function χX (x) = 1 0 if x ∈ X, if x ∈ A − X. The mapping f : X → χX is a onetoone correspondence between P (A) and {0, 1}A. 3. Cardinal Numbers 29 Thus Cantor’s Theorem 3.1 can be formulated as follows: κ < 2κ for every cardinal κ. A few simple facts about cardinal arithmetic: (3.4) + and · are associative, commutative and distributive. (3.5) (κ · λ)µ = κµ · λµ . (3.6) κλ+µ = κλ · κµ . (3.7) (κλ )µ = κλ·µ . (3.8) If κ ≤ λ, then κµ ≤ λµ . (3.9) If 0 < λ ≤ µ, then κλ ≤ κµ . (3.10) κ0 = 1; 1κ = 1; 0κ = 0 if κ > 0. To prove (3.4)–(3.10), one has only to ﬁnd the appropriate onetoone functions. Alephs An ordinal α is called a cardinal number (a cardinal) if α = β for all β < α. We shall use κ, λ, µ, . . . to denote cardinal numbers. If W is a wellordered set, then there exists an ordinal α such that W  = α. Thus we let W  = the least ordinal such that W  = α. Clearly, W  is a cardinal number. Every natural number is a cardinal (a ﬁnite cardinal ); and if S is a ﬁnite set, then S = n for some n. The ordinal ω is the least inﬁnite cardinal. Note that all inﬁnite cardinals are limit ordinals. The inﬁnite ordinal numbers that are cardinals are called alephs. Lemma 3.4. (i) For every α there is a cardinal number greater than α. (ii) If X is a set of cardinals, then sup X is a cardinal. For every α, let α+ be the least cardinal number greater than α, the cardinal successor of α. Proof. (i) For any set X, let (3.11) h(X) = the least α such that there is no onetoone function of α into X. There is only a set of possible wellorderings of subsets of X. Hence there is only a set of ordinals for which a onetoone function of α into X exists. Thus h(X) exists. 30 Part I. Basic Set Theory If α is an ordinal, then α < h(α) by (3.11). That proves (i). (ii) Let α = sup X. If f is a onetoone mapping of α onto some β < α, let κ ∈ X be such that β < κ ≤ α. Then κ = {f (ξ) : ξ < κ} ≤ β, a contradiction. Thus α is a cardinal. Using Lemma 3.4, we deﬁne the increasing enumeration of all alephs. We usually use ℵα when referring to the cardinal number, and ωα to denote the ordertype: ℵ0 = ω0 = ω, ℵα+1 = ωα+1 = ℵ+ α, ℵα = ωα = sup{ωβ : β < α} if α is a limit ordinal. Sets whose cardinality is ℵ0 are called countable; a set is at most countable if it is either ﬁnite or countable. Inﬁnite sets that are not countable are uncountable. A cardinal ℵα+1 is a successor cardinal. A cardinal ℵα whose index is a limit ordinal is a limit cardinal. Addition and multiplication of alephs is a trivial matter, due to the following fact: Theorem 3.5. ℵα · ℵα = ℵα . To prove Theorem 3.5 we use a pairing function for ordinal numbers: The Canonical WellOrdering of α × α We deﬁne a wellordering of the class Ord × Ord of ordinal pairs. Under this wellordering, each α × α is an initial segment of Ord 2 ; the induced wellordering of α2 is called the canonical wellordering of α2 . Moreover, the wellordered class Ord 2 is isomorphic to the class Ord, and we have a onetoone function Γ of Ord 2 onto Ord. For many α’s the ordertype of α × α is α; in particular for those α that are alephs. We deﬁne: (3.12) (α, β) < (γ, δ) ↔ either max{α, β} < max{γ, δ}, or max{α, β} = max{γ, δ} and α < γ, or max{α, β} = max{γ, δ}, α = γ and β < δ. The relation < deﬁned in (3.12) is a linear ordering of the class Ord × Ord. Moreover, if X ⊂ Ord × Ord is nonempty, then X has a least element. Also, for each α, α × α is the initial segment given by (0, α). If we let Γ(α, β) = the ordertype of the set {(ξ, η) : (ξ, η) < (α, β)}, 3. Cardinal Numbers 31 then Γ is a onetoone mapping of Ord 2 onto Ord, and (3.13) (α, β) < (γ, δ) if and only if Γ(α, β) < Γ(γ, δ). Note that Γ(ω×ω) = ω and since γ(α) = Γ(α×α) is an increasing function of α, we have γ(α) ≥ α for every α. However, γ(α) is also continuous, and so Γ(α × α) = α for arbitrarily large α. Proof of Theorem 3.5. Consider the canonical onetoone mapping Γ of Ord × Ord onto Ord. We shall show that Γ(ωα × ωα ) = ωα . This is true for α = 0. Thus let α be the least ordinal such that Γ(ωα × ωα ) = ωα . Let β, γ < ωα be such that Γ(β, γ) = ωα . Pick δ < ωα such that δ > β and δ > γ. Since δ × δ is an initial segment of Ord × Ord in the canonical wellordering and contains (β, γ), we have Γ(δ × δ) ⊃ ωα , and so δ × δ ≥ ℵα . However, δ × δ = δ · δ, and by the minimality of α, δ · δ = δ < ℵα . A contradiction. As a corollary we have (3.14) ℵα + ℵβ = ℵα · ℵβ = max{ℵα , ℵβ }. Exponentiation of cardinals will be dealt with in Chapter 5. Without the Axiom of Choice, one cannot prove that 2ℵα is an aleph (or that P (ωα ) can ℵ be wellordered), and there is very little one can prove about 2ℵα or ℵαβ . Coﬁnality Let α > 0 be a limit ordinal. We say that an increasing βsequence αξ : ξ < β, β a limit ordinal, is coﬁnal in α if limξ→β αξ = α. Similarly, A ⊂ α is coﬁnal in α if sup A = α. If α is an inﬁnite limit ordinal, the coﬁnality of α is cf α = the least limit ordinal β such that there is an increasing βsequence αξ : ξ < β with limξ→β αξ = α. Obviously, cf α is a limit ordinal, and cf α ≤ α. Examples: cf(ω + ω) = cf ℵω = ω. Lemma 3.6. cf(cf α) = cf α. Proof. If αξ : ξ < β is coﬁnal in α and ξ(ν) : ν < γ is coﬁnal in β, then αξ(ν) : ν < γ is coﬁnal in α. Two useful facts about coﬁnality: Lemma 3.7. Let α > 0 be a limit ordinal. (i) If A ⊂ α and sup A = α, then the ordertype of A is at least cf α. 32 Part I. Basic Set Theory (ii) If β0 ≤ β1 ≤ . . . ≤ βξ ≤ . . ., ξ < γ, is a nondecreasing γsequence of ordinals in α and limξ→γ βξ = α, then cf γ = cf α. Proof. (i) The ordertype of A is the length of the increasing enumeration of A which is an increasing sequence with limit α. (ii) If γ = limν→cf γ ξ(ν), then α = limν→cf γ βξ(ν) , and the nondecreasing sequence βξ(ν) : ν < cf γ has an increasing subsequence of length ≤ cf γ, with the same limit. Thus cf α ≤ cf γ. To show that cf γ ≤ cf α, let α = limν→cf α αν . For each ν < cf α, let ξ(ν) be the least ξ greater than all ξ(ι), ι < ν, such that βξ > αν . Since limν→cf α βξ(ν) = α, it follows that limν→cf α ξ(ν) = γ, and so cf γ ≤ cf α. An inﬁnite cardinal ℵα is regular if cf ωα = ωα . It is singular if cf ωα < ωα . Lemma 3.8. For every limit ordinal α, cf α is a regular cardinal. Proof. It is easy to see that if α is not a cardinal, then using a mapping of α onto α, one can construct a coﬁnal sequence in α of length ≤ α, and therefore cf α < α. Since cf(cf α) = cf α, it follows that cf α is a cardinal and is regular. Let κ be a limit ordinal. A subset X ⊂ κ is bounded if sup X < κ, and unbounded if sup X = κ. Lemma 3.9. Let κ be an aleph. (i) If X ⊂ κ and X < cf κ then X is bounded. (ii) If λ < cf κ and f : λ → κ then the range of f is bounded. It follows from (i) that every unbounded subset of a regular cardinal has cardinality κ. Proof. (i) Lemma 3.7(i). (ii) If X = ran(f ) then X ≤ λ, and use (i). There are arbitrarily large singular cardinals. For each α, ℵα+ω is a singular cardinal of coﬁnality ω. Using the Axiom of Choice, we shall show in Chapter 5 that every ℵα+1 is regular. (The Axiom of Choice is necessary.) Lemma 3.10. An inﬁnite cardinal κ is singular if and only if there exists a cardinal λ < κ and a family {Sξ : ξ < λ} of subsets of κ such that Sξ  < κ for each ξ < λ, and κ = ξ<λ Sξ . The least cardinal λ that satisﬁes the condition is cf κ. Proof. If κ is singular, then there is an increasing sequence αξ : ξ < cf κ with limξ αξ = κ. Let λ = cf κ, and Sξ = αξ for all ξ < λ. If the condition holds, let λ < κbe the least cardinal for which there is a family {Sξ : ξ < λ} such that κ = ξ<λ Sξ and Sξ  < κ for each ξ < λ. For 3. Cardinal Numbers 33 every ξ < λ, let βξ be the ordertype of ν<ξ Sν . The sequence βξ : ξ < λ is nondecreasing, and by the minimality of λ, βξ < κ for all ξ < λ. We shall show that limξ βξ = κ, thus proving that cf κ ≤ λ. Let β = limξ→λ βξ . There is a onetoone mapping f of κ = ξ<λ Sξ into λ × β: If α ∈ κ, let f (α) = (ξ, γ), where ξ is the least ξ such that α ∈ Sξ and γ is the ordertype of Sξ ∩ α. Since λ < κ and λ × β = λ · β, it follows that β = κ. One cannot prove without the Axiom of Choice that ω1 is not a countable union of countable sets. Compare this with Exercise 3.13 The only cardinal inequality we have proved so far is Cantor’s Theorem κ < 2κ . It follows that κ < λκ for every λ > 1, and in particular κ < κκ (for κ = 1). The following theorem gives a better inequality. This and other cardinal inequalities will also follow from König’s Theorem 5.10, to be proved in Chapter 5. Theorem 3.11. If κ is an inﬁnite cardinal, then κ < κcf κ . Proof. Let F be a collection of κ functions from cf κ to κ: F = {fα : α < κ}. It is enough to ﬁnd f : cf κ → κ that is diﬀerent from all the fα . Let κ = limξ→cf κ αξ . For ξ < cf κ, let f (ξ) = least γ such that γ = fα (ξ) for all α < αξ . Such γ exists since {fα (ξ) : α < αξ } ≤ αξ  < κ. Obviously, f = fα for all α < κ. Consequently, κλ > κ whenever λ ≥ cf κ. An uncountable cardinal κ is weakly inaccessible if it is a limit cardinal and is regular. There will be more about inaccessible cardinals later, but let me mention at this point that existence of (weakly) inaccessible cardinals is not provable in ZFC. To get an idea of the size of an inaccessible cardinal, note that if ℵα > ℵ0 is limit and regular, then ℵα = cf ℵα = cf α ≤ α, and so ℵα = α. Since the sequence of alephs is a normal sequence, it has arbitrarily large ﬁxed points; the problem is whether some of them are regular cardinals. For instance, the least ﬁxed point ℵα = α has coﬁnality ω: κ = limω, ωω , ωωω , . . . = limn→ω κn where κ0 = ω, κn+1 = ωκn . 34 Part I. Basic Set Theory Exercises 3.1. (i) A subset of a ﬁnite set is ﬁnite. (ii) The union of a ﬁnite set of ﬁnite sets is ﬁnite. (iii) The power set of a ﬁnite set is ﬁnite. (iv) The image of a ﬁnite set (under a mapping) is ﬁnite. 3.2. (i) A subset of a countable set is at most countable. (ii) The union of a ﬁnite set of countable sets is countable. (iii) The image of a countable set (under a mapping) is at most countable. 3.3. N × N is countable. [f (m, n) = 2m (2n + 1) − 1.] 3.4. (i) The set of all ﬁnite sequences in N is countable. (ii) The set of all ﬁnite subsets of a countable set is countable. 3.5. Show that Γ(α × α) ≤ ω α . 3.6. There is a wellordering of the class of all ﬁnite sequences of ordinals such that for each α, the set of all ﬁnite sequences in ωα is an initial segment and its ordertype is ωα . We say that a set B is a projection of a set A if there is a mapping of A onto B. Note that B is a projection of A if and only if there is a partition P of A such that P  = B. If A ≥ B > 0, then B is a projection of A. Conversely, using the Axiom of Choice, one shows that if B is a projection of A, then A ≥ B. This, however, cannot be proved without the Axiom of Choice. 3.7. If B is a projection of ωα , then B ≤ ℵα . 3.8. The set of all ﬁnite subsets of ωα has cardinality ℵα . [The set is a projection of the set of ﬁnite sequences.] 3.9. If B is a projection of A, then P (B) ≤ P (A). [Consider g(X) = f−1 (X), where f maps A onto B.] 3.10. ωα+1 is a projection of P (ωα ). [Use ωα × ωα  = ωα and project P (ωα × ωα ): If R ⊂ ωα × ωα is a wellordering, let f (R) be its ordertype.] ℵα 3.11. ℵα+1 < 22 . [Use Exercises 3.10 and 3.9.] 3.12. If ℵα is an uncountable limit cardinal, then cf ωα = cf α; ωα is the limit of a coﬁnal sequence ωξ : ξ < cf α of cardinals. 3.13 (ZF). Show that ω S2 is not a countable union of countable sets. [Assume that ω2 = n<ω Sn with Sn countable and let αn be the ordertype of Sn . Then α = supn αn ≤ ω1 and there is a mapping of ω × α onto ω2 .] A set S is Dedekindﬁnite (Dﬁnite) if there is no onetoone mapping of S onto a proper subset of S. Every ﬁnite set is Dﬁnite. Using the Axiom of Choice, one proves that every inﬁnite set is Dinﬁnite, and so Dﬁniteness is the same as ﬁniteness. Without the Axiom of Choice, however, one cannot prove that every Dﬁnite set is ﬁnite. The set N of all natural numbers is Dinﬁnite and hence every S such that S ≥ ℵ0 , is Dinﬁnite. 3. Cardinal Numbers 35 3.14. S is Dinﬁnite if and only if S has a countable subset. [If S is Dinﬁnite, let f : S → X ⊂ S be onetoone. Let x0 ∈ S − X and xn+1 = f (xn ). Then S ⊃ {xn : n < ω}.] 3.15. (i) If A and B are Dﬁnite, then A ∪ B and A × B are Dﬁnite. (ii) The set of all ﬁnite onetoone sequences in a Dﬁnite set is Dﬁnite. (iii) The union of a disjoint Dﬁnite family of Dﬁnite sets is Dﬁnite. On the other hand, one cannot prove without the Axiom of Choice that a projection, power set, or the set of all ﬁnite subsets of a Dﬁnite set is Dﬁnite, or that the union of a Dﬁnite family of Dﬁnite sets is Dﬁnite. 3.16. If A is an inﬁnite set, then P P (A) is Dinﬁnite. [Consider the set {{X ⊂ A : X = n} : n < ω}.] Historical Notes Cardinal numbers and alephs were introduced by Cantor. The proof of the CantorBernstein Theorem is Bernstein’s; see Borel [1898], p. 103. (There is an earlier proof by Dedekind.) The ﬁrst proof of ℵα ·ℵα = ℵα appeared in Hessenberg [1906], p. 593. Regularity of cardinals was investigated by Hausdorﬀ, who also raised the question of existence of regular limit cardinals. Dﬁniteness was formulated by Dedekind. This page intentionally left blank 4. Real Numbers The set of all real numbers R (the real line or the continuum) is the unique ordered ﬁeld in which every nonempty bounded set has a least upper bound. The proof of the following theorem marks the beginning of Cantor’s theory of sets. Theorem 4.1 (Cantor). The set of all real numbers is uncountable. Proof. Let us assume that the set R of all reals is countable, and let c0 , c1 , . . . , cn , . . . , n ∈ N , be an enumeration of R. We shall ﬁnd a real number diﬀerent from each cn . Let a0 = c0 and b0 = ck0 where k0 is the least k such that a0 < ck . For each n, let an+1 = cin where in is the least i such that an < ci < bn , and bn+1 = ckn where kn is the least k such that an+1 < ck < bn . If we let a = sup{an : n ∈ N }, then a = ck for all k. The Cardinality of the Continuum Let c denote the cardinality of R. As the set Q of all rational numbers is dense in R, every real number r is equal to sup{q ∈ Q : q < r} and because Q is countable, it follows that c ≤ P (Q) = 2ℵ0 . ∞ Let C (the Cantor set ) be the set of all reals of the form n=1 an /3n , where each an = 0 or 2. C is obtained by removing from the closed interval [0, 1], the open intervals ( 13 , 23 ), ( 19 , 29 ), ( 79 , 89 ), etc. (the middlethird intervals). C is in a onetoone correspondence with the set of all ωsequences of 0’s and 2’s and so C = 2ℵ0 . Therefore c ≥ 2ℵ0 , and so by the CantorBernstein Theorem we have (4.1) c = 2ℵ0 . By Cantor’s Theorem 4.1 (or by Theorem 3.1), c > ℵ0 . Cantor conjectured that every set of reals is either at most countable or has cardinality of the continuum. In ZFC, every inﬁnite cardinal is an aleph, and so 2ℵ0 ≥ ℵ1 . Cantor’s conjecture then becomes the statement 2ℵ0 = ℵ1 known as the Continuum Hypothesis (CH). 38 Part I. Basic Set Theory Among sets of cardinality c are the set of all sequences of natural numbers, the set of all sequences of real numbers, the set of all complex numbers. This is because ℵℵ0 0 = (2ℵ0 )ℵ0 = 2ℵ0 , 2ℵ0 · 2ℵ0 = 2ℵ0 . Cantor’s proof of Theorem 4.1 yielded more than uncountability of R; it showed that the set of all transcendental numbers has cardinality c (cf. Exercise 4.5). The Ordering of R A linear ordering (P, <) is complete if every nonempty bounded subset of P has a least upper bound. We stated above that R is the unique complete ordered ﬁeld. We shall generally disregard the ﬁeld properties of R and will concern ourselves more with the order properties. One consequence of being a complete ordered ﬁeld is that R contains the set Q of all rational numbers as a dense subset. The set Q is countable and its ordering is dense. Deﬁnition 4.2. A linear ordering (P, <) is dense if for all a < b there exists a c such that a < c < b. A set D ⊂ P is a dense subset if for all a < b in P there exists a d ∈ D such that a < d < b. The following theorem proves the uniqueness of the ordered set (R, <). We say that an ordered set is unbounded if it has neither a least nor a greatest element. Theorem 4.3 (Cantor). (i) Any two countable unbounded dense linearly ordered sets are isomorphic. (ii) (R, <) is the unique complete linear ordering that has a countable dense subset isomorphic to (Q, <). Proof. (i) Let P1 = {an : n ∈ N } and let P2 = {bn : n ∈ N } be two such linearly ordered sets. We construct an isomorphism f : P1 → P2 in the following way: We ﬁrst deﬁne f (a0 ), then f −1 (b0 ), then f (a1 ), then f −1 (b1 ), etc., so as to keep f orderpreserving. For example, to deﬁne f (an ), if it is not yet deﬁned, we let f (an ) = bk where k is the least index such that f remains orderpreserving (such a k always exists because f has been deﬁned for only ﬁnitely many a ∈ P1 , and because P2 is dense and unbounded). (ii) To prove the uniqueness of R, let C and C be two complete dense unbounded linearly ordered sets, let P and P be dense in C and C , respectively, and let f be an isomorphism of P onto P . Then f can be extended (uniquely) to an isomorphism f ∗ of C and C : For x ∈ C, let f ∗ (x) = sup{f (p) : p ∈ P and p ≤ x}. 4. Real Numbers 39 The existence of (R, <) is proved by means of Dedekind cuts in (Q, <). The following theorem is a general version of this construction: Theorem 4.4. Let (P, <) be a dense unbounded linearly ordered set. Then there is a complete unbounded linearly ordered set (C, ≺) such that : (i) P ⊂ C, and < and ≺ agree on P ; (ii) P is dense in C. Proof. A Dedekind cut in P is a pair (A, B) of disjoint nonempty subsets of P such that (i) A ∪ B = P ; (ii) a < b for any a ∈ A and b ∈ B; (iii) A does not have a greatest element. Let C be the set of all Dedekind cuts in P and let (A1 , B1 ) (A2 , B2 ) if A1 ⊂ A2 (and B1 ⊃ B2 ). The set C is complete: If {(Ai , Bi ) : i ∈ I} is a nonempty bounded subset of C, then ( i∈I Ai , i∈I Bi ) is its supremum. For p ∈ P , let Ap = {x ∈ P : x < p}, Bp = {x ∈ P : x ≥ p}. Then P = {(Ap , Bp ) : p ∈ P } is isomorphic to P and is dense in C. Suslin’s Problem The real line is, up to isomorphism, the unique linearly ordered set that is dense, unbounded, complete and contains a countable dense subset. Since Q is dense in R, every nonempty open interval of R contains a rational number. Hence if S is a disjoint collection of open intervals, S is at most countable. (Let rn : n ∈ N be an enumeration of the rationals. To each J ∈ S assign rn ∈ J with the least possible index n.) Let P be a dense linearly ordered set. If every disjoint collection of open intervals in P is at most countable, then we say that P satisﬁes the countable chain condition. Suslin’s Problem. Let P be a complete dense unbounded linearly ordered set that satisﬁes the countable chain condition. Is P isomorphic to the real line? This question cannot be decided in ZFC; we shall return to the problem in Chapter 9. 40 Part I. Basic Set Theory The Topology of the Real Line The real line is a metric space with the metric d(a, b) = a − b. Its metric topology coincides with the order topology of (R, <). Since Q is a dense set in R and since every Cauchy sequence of real numbers converges, R is a separable complete metric space. (A metric space is separable if it has a countable dense set; it is complete if every Cauchy sequence converges.) Open sets are unions of open intervals, and in fact, every open set is the union of open intervals with rational endpoints. This implies that the number of all open sets in R is the continuum and so is the number of all closed sets in R (Exercise 4.6). Every open interval has cardinality c, therefore every nonempty open set has cardinality c. We show below that every uncountable closed set has cardinality c. Proving this was Cantor’s ﬁrst step in the search for the proof of the Continuum Hypothesis. In Chapter 11 we show that CH holds for Borel and analytic sets as well. A nonempty closed set is perfect if it has no isolated points. Theorems 4.5 and 4.6 below show that every uncountable closed set contains a perfect set. Theorem 4.5. Every perfect set has cardinality c. Proof. Given a perfect set P , we want to ﬁnd a onetoone function F from {0, 1}ω into P . Let S be the set of all ﬁnite sequences of 0’s and 1’s. By induction on the length of s ∈ S one can ﬁnd closed intervals Is such that for each n and all s ∈ S of length n, (i) Is ∩ P is perfect, (ii) the diameter of Is is ≤ 1/n, (iii) Is 0 ⊂ Is , Is 1 ⊂ Is and Is 0 ∩ Is 1 = ∅. For each f ∈ {0, 1}ω , the set P ∩ ∞ n=0 If n has exactly one element, and we let F (f ) to be this element of P . The same proof gives a more general result: Every perfect set in a separable complete metric space contains a closed copy of the Cantor set (Exercise 4.19). Theorem 4.6 (CantorBendixson). If F is an uncountable closed set, then F = P ∪ S, where P is perfect and S is at most countable. Corollary 4.7. If F is a closed set, then either F  ≤ ℵ0 or F  = 2ℵ0 . Proof. For every A ⊂ R, let A = the set of all limit points of A It is easy to see that A is closed, and if A is closed then A ⊂ A. Thus we let F0 = F, Fα+1 = Fα , Fγ if α > 0 is a limit ordinal. Fα = γ<α 4. Real Numbers 41 Since F0 ⊃ F1 ⊃ . . . ⊃ Fα ⊃ . . ., there exists an ordinal θ such that Fα = Fθ for all α ≥ θ. (In fact, the least θ with this property must be countable, by the argument below.) We let P = Fθ . If P is nonempty, then P = P and so it is perfect. Thus the proof is completed by showing that F − P is at most countable. Let Jk : k ∈ N be an enumeration of rational intervals. We have F −P = α<θ (Fα − Fα ); hence if a ∈ F − P , then there is a unique α such that a is an isolated point of Fα . We let k(a) be the least k such that a is the only point of Fα in the interval Jk . Note that if α ≤ β, b = a and b ∈ Fβ − Fβ , then b ∈ / Jk(a) , and hence k(b) = k(a). Thus the correspondence a → k(a) is onetoone, and it follows that F − P is at most countable. A set of reals is called nowhere dense if its closure has empty interior. The following theorem shows that R is not the union of countably many nowhere dense sets (R is not of the ﬁrst category). Theorem 4.8 (The Baire Category Theorem). If D0 , D1 , . .. , Dn , . . . , ∞ n ∈ N , are dense open sets of reals, then the intersection D = n=0 Dn is dense in R. Proof. We show that D intersects every nonempty open interval I. First note that for each n, D0 ∩ . . . ∩ Dn is dense and open. Let Jk : k ∈ N be an enumeration of rational intervals. Let I0 = I, and let, for each n, In+1 = Jk = (qk , rk ), where k is the least k such that the closed interval [qk , rk ] is included in In ∩ Dn . Then a ∈ D ∩ I, where a = limk→∞ qk . Borel Sets Deﬁnition 4.9. An algebra of sets is a collection S of subsets of a given set S such that (4.2) (i) S ∈ S, (ii) if X ∈ S and Y ∈ S then X ∪ Y ∈ S, (iii) if X ∈ S then S − X ∈ S. (Note that S is also closed under intersections.) A σalgebra is additionally closed under countable unions (and intersections): (iv) If Xn ∈ S for all n, then ∞ n=0 Xn ∈ S. For any collection X of subsets of S there is a smallest algebra (σalgebra) S such that S ⊃ X ; namely the intersection of all algebras (σalgebras) S of subsets of S for which X ⊂ S. Deﬁnition 4.10. A set of reals B is Borel if it belongs to the smallest σalgebra B of sets of reals that contains all open sets. 42 Part I. Basic Set Theory In Chapter 11 we investigate Borel sets in more detail. In particular, we shall classify Borel sets by deﬁning a hierarchy of ω1 levels. For that we need however a weak version of the Axiom of Choice that is not provable in ZF alone. At this point we mention the lowest level of the hierarchy (beyond open sets and closed sets): The intersections of countably many open sets are called Gδ sets, and the unions of countably many closed sets are called Fσ sets. Lebesgue Measure We assume that the reader is familiar with the basic theory of Lebesgue measure. As we shall return to the subject in Chapter 11 we do not deﬁne the concept of measure at this point. We also caution the reader that some of the basic theorems on Lebesgue measure require the Countable Axiom of Choice (to be discussed in Chapter 5). Lebesgue measurable sets form a σalgebra and contain all open intervals (the measure of an interval is its length). Thus all Borel sets are Lebesgue measurable. The Baire Space The Baire space is the space N = ω ω of all inﬁnite sequences of natural numbers, an : n ∈ N , with the following topology: For every ﬁnite sequence s = ak : k < n, let (4.3) O(s) = {f ∈ N : s ⊂ f } = {ck : k ∈ N : (∀k < n) ck = ak }. The sets (4.3) form a basis for the topology of N . Note that each O(s) is also closed. The Baire space is separable and is metrizable: consider the metric d(f, g) = 1/2n+1 where n is the least number such that f (n) = g(n). The countable set of all eventually constant sequences is dense in N . This separable metric space is complete, as every Cauchy sequence converges. Every inﬁnite sequence an : n ∈ N of positive integers deﬁnes a continued fraction 1/(a0 + 1/(a1 + 1/(a2 + . . .))), an irrational number between 0 and 1. Conversely, every irrational number in the interval (0, 1) can be so represented, and the onetoone correspondence is a homeomorphism. It follows that the Baire space is homeomorphic to the space of all irrational numbers. For various reasons, modern descriptive set theory uses the Baire space rather than the real line. Often the functions in ω ω are called reals. Clearly, the space N satisﬁes the Baire Category Theorem; the proof is similar to the proof of Theorem 4.8 above. The CantorBendixson Theorem holds as well. For completeness we give a description of perfect sets in N . 4. Real Numbers 43 Let Seq denote the set of all ﬁnite sequences of natural numbers. A (sequential ) tree is a set T ⊂ Seq that satisﬁes (4.4) if t ∈ T and s = tn for some n, then s ∈ T . If T ⊂ Seq is a tree, let [T ] be the set of all inﬁnite paths through T : (4.5) [T ] = {f ∈ N : f n ∈ T for all n ∈ N }. The set [T ] is a closed set in the Baire space: Let f ∈ N be such that f ∈ / [T ]. Then there is n ∈ N such that f n = s is not in T . In other words, the open set O(s) = {g ∈ N : g ⊃ s}, a neighborhood of f , is disjoint from [T ]. Hence [T ] is closed. Conversely, if F is a closed set in N , then the set (4.6) TF = {s ∈ Seq : s ⊂ f for some f ∈ F } is a tree, and it is easy to verify that [TF ] = F : If f ∈ N is such that f n ∈ T for all n ∈ N , then for each n there is some g ∈ F such that gn = f n; and since F is closed, it follows that f ∈ F . If f is an isolated point of a closed set F in N , then there is n ∈ N such that there is no g ∈ F , g = f , such that gn = f n. Thus the following deﬁnition: A nonempty sequential tree T is perfect if for every t ∈ T there exist s1 ⊃ t and s2 ⊃ t, both in T , that are incomparable, i.e., neither s1 ⊃ s2 nor s 2 ⊃ s1 . Lemma 4.11. A closed set F ⊂ N is perfect if and only if the tree TF is a perfect tree. The CantorBendixson analysis for closed sets in the Baire space is carried out as follows: For each tree T ⊂ Seq, we let (4.7) T = {t ∈ T : there exist incomparable s1 ⊃ t and s2 ⊃ t in T }. (Thus T is perfect if and only if ∅ = T = T .) The set [T ]−[T ] is at most countable: For each f ∈ [T ] such that f ∈ / [T ], let sf = f n where n is the least number such that f n ∈ / T . If f, g ∈ [T ] − [T ], then sf = sg , by (4.7). Hence the mapping f → sf is onetoone and [T ] − [T ] is at most countable. Now we let (4.8) T0 = T, Tα+1 = Tα , Tβ if α > 0 is a limit ordinal. Tα = β<α Since T0 ⊃ T1 ⊃ . . . ⊃ Tα ⊃ . . ., and T0 is at most countable, there is an ordinal θ < ω1 such that Tθ+1 = Tθ . If Tθ = ∅, then it is perfect. 44 Part I. Basic Set Theory Tβ = β<α [Tβ ], and so ([Tα ] − [Tα ]); [T ] − [Tθ ] = Now it is easy to see that (4.9) β<α α<θ hence (4.9) is at most countable. Thus if [T ] is an uncountable closed set in N , the sets [Tθ ] and [T ] − [Tθ ] constitute the decomposition of [T ] into a perfect and an at most countable set. In modern descriptive set theory one often speaks about the Lebesgue measure on N . This measure is the extension of the product measure m on Borel sets in the Baire space induced by the probability measure on N that gives the singleton {n} measure 1/2n+1 . Thus for every sequence s ∈ Seq of length n ≥ 1 we have n−1 (4.10) m(O(s)) = 1/2s(k)+1 . k=0 Polish Spaces Deﬁnition 4.12. A Polish space is a topological space that is homeomorphic to a separable complete metric space. Examples of Polish spaces include R, N , the Cantor space, the unit interval [0, 1], the unit circle T , the Hilbert cube [0, 1]ω , etc. Every Polish space is a continuous image of the Baire space. In Chapter 11 we prove a somewhat more general statement. Exercises 4.1. The set of all continuous functions f : R → R has cardinality c (while the set of all functions has cardinality 2c ). [A continuous function on R is determined by its values at rational points.] 4.2. There are at least c countable ordertypes of linearly ordered sets. [For every sequence a = an : n ∈ N of natural numbers consider the ordertype τa = a0 + ξ + a1 + ξ + a2 + . . . where ξ is the ordertype of the integers. Show that if a = b, then τa = τb .] A real number is algebraic if it is a root of a polynomial whose coeﬃcients are integers. Otherwise, it is transcendental. 4.3. The set of all algebraic reals is countable. 4.4. If S is a countable set of reals, then R − S = c. [Use R × R rather than R (because R × R = 2ℵ0 ).] 4. Real Numbers 45 4.5. (i) The set of all irrational numbers has cardinality c. (ii) The set of all transcendental numbers has cardinality c. 4.6. The set of all open sets of reals has cardinality c. 4.7. The Cantor set is perfect. 4.8. If P is a perfect set and (a, b) is an open interval such that P ∩ (a, b) = ∅, then P ∩ (a, b) = c. 4.9. If P2 ⊂ P1 are perfect sets, then P2 − P1  = c. [Use Exercise 4.8.] If A is a set of reals, a real number a is called a condensation point of A if every neighborhood of a contains uncountably many elements of A. Let A∗ denote the set of all condensation points of A. 4.10. If P is perfect then P ∗ = P . [Use Exercise 4.8.] 4.11. If F is closed and P ⊂ F is perfect, then P ⊂ F ∗ . [P = P ∗ ⊂ F ∗ .] 4.12. If F is an uncountable closed set and P is the perfect set constructed in Theorem 4.6, then F ∗ ⊂ P ; thus F ∗ = P . [Every a ∈ F ∗ is a limit point of P since F − P  ≤ ℵ0 .] 4.13. If F is an uncountable closed set, then F = F ∗ ∪ (F − F ∗ ) is the unique partition of F into a perfect set and an at most countable set. [Use Exercise 4.9.] 4.14. Q is not the intersection of a countable collection of open sets. [Use the Baire Category Theorem.] 4.15. If B is Borel and f is a continuous function then f−1 (B) is Borel. 4.16. Let f : R → R. Show that the set of all x at which f is continuous is a Gδ set. 4.17. (i) N × N is homeomorphic to N . (ii) N ω is homeomorphic to N . 4.18. The tree TF in (4.6) has no maximal node, i.e., s ∈ T such that there is no t ∈ T with s ⊂ t. The map F → TF is a onetoone correspondence between closed sets in N and sequential trees without maximal nodes. 4.19. Every perfect Polish space has a closed subset homeomorphic to the Cantor space. 4.20. Every Polish space is homeomorphic to a Gδ subspace of the Hilbert cube. [Let {xn : n ∈ N } be a dense set, and deﬁne f (x) = d(x, xn ) : n ∈ N .] Historical Notes Theorems 4.1, 4.3 and 4.5 are due to Cantor. The construction of real numbers by completion of the rationals is due to Dedekind [1872]. Suslin’s Problem: Suslin [1920]. Theorem 4.6: Cantor, Bendixson [1883]. Theorem 4.8: Baire [1899]. Exercise 4.5: Cantor. This page intentionally left blank 5. The Axiom of Choice and Cardinal Arithmetic The Axiom of Choice Axiom of Choice (AC). Every family of nonempty sets has a choice function. If S is a family of sets and ∅ ∈ / S, then a choice function for S is a function f on S such that (5.1) f (X) ∈ X for every X ∈ S. The Axiom of Choice postulates that for every S such that ∅ ∈ / S there exists a function f on S that satisﬁes (5.1). The Axiom of Choice diﬀers from other axioms of ZF by postulating the existence of a set (i.e., a choice function) without deﬁning it (unlike, for instance, the Axiom of Pairing or the Axiom of Power Set). Thus it is often interesting to know whether a mathematical statement can be proved without using the Axiom of Choice. It turns out that the Axiom of Choice is independent of the other axioms of set theory and that many mathematical theorems are unprovable in ZF without AC. In some trivial cases, the existence of a choice function can be proved outright in ZF: (i) when every X ∈ S is a singleton X = {x}; (ii) when S is ﬁnite; the existence of a choice function for S is proved by induction on the size of S; (iii) when every X ∈ S is a ﬁnite set of real numbers; let f (X) = the least element of X. On the other hand, one cannot prove existence of a choice function (in ZF) just from the assumption that the sets in S are ﬁnite; even when every X ∈ S has just two elements (e.g., sets of reals), we cannot necessarily prove that S has a choice function. Using the Axiom of Choice, one proves that every set can be wellordered, and therefore every inﬁnite set has cardinality equal to some ℵα . In particular, 48 Part I. Basic Set Theory any two sets have comparable cardinals, and the ordering X ≤ Y  is a wellordering of the class of all cardinals. Theorem 5.1 (Zermelo’s WellOrdering Theorem). Every set can be wellordered. Proof. Let A be a set. To wellorder A, it suﬃces to construct a transﬁnite onetoone sequence aα : α < θ that enumerates A. That we can do by induction, using a choice function f for the family S of all nonempty subsets of A. We let for every α aα = f (A − {aξ : ξ < α}) if A − {aξ : ξ < α} is nonempty. Let θ be the least ordinal such that A = {aξ : ξ < θ}. Clearly, aα : α < θ enumerates A. In fact, Zermelo’s Theorem 5.1 is equivalent to the Axiom of Choice: If every set can be wellordered, then every family S of nonempty sets has a choice function. To see this, wellorder S and let f (X) be the least element of X for every X ∈ S. Of particular importance is the fact that the set of all real numbers can be wellordered. It follows that 2ℵ0 is an aleph and so 2ℵ0 ≥ ℵ1 . The existence of a wellordering of R yields some interesting counterexamples. Well known is Vitali’s construction of a nonmeasurable set (Exercise 10.1); another example is an uncountable set of reals without a perfect subset (Exercise 5.1). If every set can be wellordered, then every inﬁnite set has a countable subset: Wellorder the set and take the ﬁrst ω elements. Thus every inﬁnite set is Dedekindinﬁnite, and so ﬁniteness and Dedekind ﬁniteness coincide. Dealing with cardinalities of sets is much easier when we have the Axiom of Choice. In the ﬁrst place, any two sets have comparable cardinals. Another consequence is: (5.2) if f maps A onto B then B ≤ A. To show (5.2), we have to ﬁnd a onetoone function from B to A. This is done by choosing one element from f−1 ({b}) for each b ∈ B. Another consequence of the Axiom of Choice is: (5.3) The union of a countable family of countable sets is countable. (By the way, this often used fact cannot be proved in ZF alone.) To prove (5.3) let An be a countable set for each n ∈ N . For each n, let us choose an 5. The Axiom of Choice and Cardinal Arithmetic 49 enumeration an,k : k ∈ N of An . That gives us a projection of N × N onto ∞ n=0 An : (n, k) → an,k . ∞ Thus n=0 An is countable. In a similar fashion, one can prove a more general statement. Lemma 5.2.  S ≤ S · sup{X : X ∈ S}. Proof. Let κ = S and λ = sup{X : X ∈ S}. We have S = {Xα : α < κ} and for each α < κ, we choose an enumeration Xα = {aα,β : β < λα }, where λα ≤ λ. Again we have a projection (α, β) → aα,β of κ × λ onto S, and so  S ≤ κ · λ. In particular, the union of ℵα sets, each of cardinality ℵα , has cardinality ℵα . Corollary 5.3. Every ℵα+1 is a regular cardinal. Proof. This is because otherwise ωα+1 would be the union of at most ℵα sets of cardinality at most ℵα . Using the Axiom of Choice in Mathematics In algebra and point set topology, one often uses the following version of the Axiom of Choice. We recall that if (P, <) is a partially ordered set, then a ∈ P is called maximal in P if there is no x ∈ P such that a < x. If X is a nonempty subset of P , then c ∈ P is an upper bound of X if x ≤ c for every x ∈ X. We say that a nonempty C ⊂ P is a chain in P if C is linearly ordered by <. Theorem 5.4 (Zorn’s Lemma). If (P, <) is a nonempty partially ordered set such that every chain in P has an upper bound, then P has a maximal element. Proof. We construct (using a choice function for nonempty subsets of P ), a chain in P that leads to a maximal element of P . We let, by induction, aα = an element of P such that aα > aξ for every ξ < α if there is one. Clearly, if α > 0 is a limit ordinal, then Cα = {aξ : ξ < α} is a chain in P and aα exists by the assumption. Eventually, there is θ such that there is no aθ+1 ∈ P , aθ+1 > aθ . Thus aθ is a maximal element of P . 50 Part I. Basic Set Theory Like Zermelo’s Theorem 5.1, Zorn’s Lemma 5.4 is equivalent to the Axiom of Choice (in ZF); see Exercise 5.5. There are numerous examples of proofs using Zorn’s Lemma. To mention only of few: Every vector space has a basis. Every ﬁeld has a unique algebraic closure. The HahnBanach Extension Theorem. Tikhonov’s Product Theorem for compact spaces. The Countable Axiom of Choice Many important consequences of the Axiom of Choice, particularly many concerning the real numbers, can be proved from a weaker version of the Axiom of Choice. The Countable Axiom of Choice. Every countable family of nonempty sets has a choice function. For instance, the countable AC implies that the union of countably many countable sets is countable. In particular, the real line is not a countable union of countable sets. Similarly, it follows that ℵ1 is a regular cardinal. On the other hand, the countable AC does not imply that the set of all reals can be wellordered. Several basic theorems about Borel sets and Lebesgue measure use the countable AC; for instance, one needs it to show that the union of countably many Fσ sets is Fσ . In modern descriptive set theory one often works without the Axiom of Choice and uses the countable AC instead. In some instances, descriptive set theorists use a somewhat stronger principle (that follows from AC): The Principle of Dependent Choices (DC). If E is a binary relation on a nonempty set A, and if for every a ∈ A there exists b ∈ A such that b E a, then there is a sequence a0 , a1 , . . . , an , . . . in A such that an+1 E an (5.4) for all n ∈ N . The Principle of Dependent Choices is stronger than the Countable Axiom of Choice; see Exercise 5.7. As an application of DC we have the following characterization of wellfounded relations and wellorderings: Lemma 5.5. (i) A linear ordering < of a set P is a wellordering of P if and only if there is no inﬁnite descending sequence a0 > a1 > . . . > an > . . . in A. 5. The Axiom of Choice and Cardinal Arithmetic 51 (ii) A relation E on P is wellfounded if and only if there is no inﬁnite sequence an : n ∈ N in P such that (5.5) an+1 E an for all n ∈ N . Proof. Note that (i) is a special case of (ii) since a wellordering is a wellfounded linear ordering. If a0 , a1 , . . . , an , . . . is a sequence that satisﬁes (5.5), then the set {an : n ∈ N } has no Eminimal element and hence E is not wellfounded. Conversely, if E is not wellfounded, then there is a nonempty set A ⊂ P with no Eminimal element. Using the Principle of Dependent Choices we construct a sequence a0 , a1 , . . . , an , . . . that satisﬁes (5.5). Cardinal Arithmetic In the presence of the Axiom of Choice, every set can be wellordered and so every inﬁnite set has the cardinality of some ℵα . Thus addition and multiplication of inﬁnite cardinal numbers is simple: If κ and λ are inﬁnite cardinals then κ + λ = κ · λ = max{κ, λ}. The exponentiation of cardinals is more interesting. The rest of Chapter 5 is devoted to the operations 2κ and κλ , for inﬁnite cardinals κ and λ. Lemma 5.6. If 2 ≤ κ ≤ λ and λ is inﬁnite, then κλ = 2λ . Proof. (5.6) 2λ ≤ κλ ≤ (2κ )λ = 2κ·λ = 2λ . If κ and λ are inﬁnite cardinals and λ < κ then the evaluation of κλ is more complicated. First, if 2λ ≥ κ then we have κλ = 2λ (because κλ ≤ (2λ )λ = 2λ ), but if 2λ < κ then (because κλ ≤ κκ = 2κ ) we can only conclude (5.7) κ ≤ κλ ≤ 2 κ . Not much more can be claimed at this point, except that by Theorem 3.11 in Chapter 3 (κcf κ > κ) we have (5.8) κ < κλ if λ ≥ cf κ. If λ is a cardinal and A ≥ λ, let (5.9) [A]λ = {X ⊂ A : X = λ}. Lemma 5.7. If A = κ ≥ λ, then the set [A]λ has cardinality κλ . 52 Part I. Basic Set Theory Proof. On the one hand, every f : λ → A is a subset of λ × A, and f  = λ. Thus κλ ≤ [λ × A]λ = [A]λ . On the other hand, we construct a onetoone function F : [A]λ → Aλ as follows: If X ⊂ A and X = λ, let F (X) be some function f on λ whose range is X. Clearly, F is onetoone. If λ is a limit cardinal, let (5.10) κ<λ = sup{κµ : µ is a cardinal and µ < λ}. + For the sake of completeness, we also deﬁne κ<λ = κλ for inﬁnite successor cardinals λ+ . If κ is an inﬁnite cardinal and A ≥ κ, let (5.11) [A]<κ = Pκ (A) = {X ⊂ A : X < κ}. It follows from Lemma 5.7 and Lemma 5.8 below that the cardinality of Pκ (A) is A<κ . Inﬁnite Sums and Products Let {κi : i ∈ I} be an indexed set of cardinal numbers. We deﬁne (5.12) κi = i∈I Xi , i∈I where {Xi : i ∈ I} is a disjoint family of sets such that Xi  = κi for each i ∈ I. This deﬁnition does not depend on the choice of {Xi }i ; this follows from the Axiom of Choice (see Exercise 5.9). Note that if κ and λ are cardinals and κi = κ for each i < λ, then κi = λ · κ. i<λ In general, we have the following Lemma 5.8. If λ is an inﬁnite cardinal and κi > 0 for each i < λ, then (5.13) κi = λ · supi<λ κi . i<λ Proof. Let κ = sup i<λ κi and σ = i<λ κi . On the one hand, since κi ≤ κ for all i, we have i<λ κ ≤ λ · κ. On the other hand, since κi ≥ 1 for all i, we have λ = i<λ 1 ≤ σ, and since σ ≥ κi for all i, we have σ ≥ supi<λ κi = κ. Therefore σ ≥ λ · κ. 5. The Axiom of Choice and Cardinal Arithmetic 53 In particular, if λ ≤ supi<λ κi , we have κi = supi<λ κi . i<λ Thus we can characterize singular cardinals as follows: An inﬁnite cardinal κ is singular just in case κi κ= i<λ where λ < κ and for each i, κi < κ. An inﬁnite product of cardinals is deﬁned using inﬁnite products of sets. If {Xi : i ∈ I} is a family of sets, then the product is deﬁned as follows: Xi = {f : f is a function on I and f (i) ∈ Xi for each i ∈ I}. (5.14) i∈I Note that if some Xi is empty, then the product is empty. If all the Xi are nonempty, then AC implies that the product is nonempty. If {κi : i ∈ I} is a family of cardinal numbers, we deﬁne κi = (5.15) i∈I Xi , i∈I where {Xi : i ∈ I} is a family of sets such that Xi  = κi for each i ∈ I. (We abuse the notation by using both for the product of sets and for the product of cardinals.) Again, it follows from AC that the deﬁnition does not depend on the choice of the sets Xi (Exercise 5.10). If κi = κ for each i ∈ I, and I = λ, then i∈I κi = κλ . Also, inﬁnite sums and products satisfy some of the rules satisﬁed P by ﬁnite sums and products. λ λ λi i λi . Or if I is a disjoint union For instance, κ = ( κ ) , or κ = κ i i i i i I = j∈J Aj , then (5.16) κi . κi = i∈I j∈J i∈Aj If κi ≥ 2 for each i ∈ I, then (5.17) κi ≤ i∈I κi . i∈I (The assumption κi ≥ 2 is necessary: 1 + 1 > 1 · 1.) If I is ﬁnite, then (5.17) is I certainly true; thus assume that I is inﬁnite. Since i∈I κi ≥ i∈I 2 = 2 > I, it suﬃces to show that i κi ≤ I · i κi . If {Xi : i ∈ I} is a disjoint family, we assign to each x ∈ i Xi a pair (i, f ) such that x ∈ Xi , f ∈ i Xi and f (i) = x. Thus we have (5.17). Inﬁnite product of cardinals can be evaluated using the following lemma: 54 Part I. Basic Set Theory Lemma 5.9. If λ is an inﬁnite cardinal and κi : i < λ is a nondecreasing sequence of nonzero cardinals, then κi = (supi κi )λ . i<λ Proof. Let κ = supi κi . Since κi ≤ κ for each i < λ, we have κi ≤ i<λ κ = κλ . i<λ To prove that κλ ≤ i<λ κi , we consider a partition of λ into λ disjoint sets Aj , each of cardinality λ: (5.18) λ= Aj . j<λ (To get a partition (5.18), we can, e.g., use the canonical pairing function Γ : λ × λ → λ and let Aj = Γ(λ × {j}).) Since a product of nonzero cardinals is greater than or equal to each factor, we have i∈Aj κi ≥ supi∈Aj κi = κ, for each j < λ. Thus, by (5.16), κi = κi ≥ κ = κλ . j<λ i∈Aj i<λ j<λ The strict inequalities in cardinal arithmetic that we proved in Chapter 3 can be obtained as special cases of the following general theorem. Theorem 5.10 (König). If κi < λi for every i ∈ I, then κi < λi . i∈I i∈I Proof. We shall show that i κi i λi . Let Ti , i ∈ I, be such that Ti  = λi for each i ∈ I. It suﬃces to show that if Zi , i ∈ I, are subsets of T = i∈I Ti , and Zi  ≤ κi for each i ∈ I, then i∈I Zi = T . For every i ∈ I, let Si be the projection of Zi into the ith coordinate: Si = {f (i) : f ∈ Zi }. Since Zi  < Ti , we have Si ⊂ Ti and Si = Ti . Now let f ∈ T be a function such that f (i)∈ / Si for every i ∈ I. Obviously, f does not belong to any Z