Set Theory MATH 771
Popular in Course
Popular in Mathematics (M)
This 10 page Class Notes was uploaded by Zechariah Hilpert on Thursday September 17, 2015. The Class Notes belongs to MATH 771 at University of Wisconsin - Madison taught by Joseph Miller in Fall. Since its upload, it has received 44 views. For similar materials see /class/205284/math-771-university-of-wisconsin-madison in Mathematics (M) at University of Wisconsin - Madison.
Reviews for Set Theory
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/17/15
AMiller M771 Jan 1998 httpwwwmathwisceduNmillerm771 A selected list of books about set theory Beginning Roitman Introduction to modern set theory Vaught Set theory an introduction Monk Introduction to set theory Moschovakis Notes on set theory Just and Weese Discovering modern set theory I II Hausdorff Set theory Intermediate Kunen Set theory Jech Set theory Handbook of mathematical logic chapter on set theory Ciesielski Set theory for the working mathematician Advanced Bartoszynski and Judah Set theory on the structure of the real line Kanamori The higher in nite Shelah Proper forcing Shelah Cardinal arithmetic Devlin Constructibility Jech The axiom of choice F remlin Consequences of Martin7s axiom Prerequisites The prerequisite for this course is Math 770 Introduction to Mathematical Logic Usually the following topics are among those covered in 770 Naive set Theory cardinal and ordinal arithmetic axioms of Zermelo Fraenkel set theory with the axiom of choice First order logic formulas sentences theories structures models satisfaction the compactness completeness and incompleteness theorems What follows is excerpted from a manuscript which can be found on my home page The Axioms of Set Theory Here are some The whole system is known as ZF for Zermelo F raenkel set theory When the axiom of choice is included it is denoted ZFC39 It was originally developed by Zermelo to make precise what he meant when he said that the well ordering principal follows from the axiom of choice Latter P raenkel added the axiom of replacement Another interesting system is GBN which is Godel Bernays von Neumann set theory Empty Set Emay 6 96 The empty set is usually written 0 Extensionality Vszz y ltgt Vzz E z ltgt 2 E Hence there is only one empty set Pairing VszHzVum E z ltgt u z Vu y We usually write 2 Union Vx y Vzz E y ltgt Huu E zAz E We usually write y Ux A U B abbreviates UA7 B 2 Q z is an abbreviation for Vuu62 u z Power Set VzHszz E y ltgt 2 Q We usually write y For any set x 7 z 1 x U In nity 3y EyVxz ya1 y The smallest such y is denoted u so u 07 127 Comprehension Scheme Vz yV s E y ltgt x E z0x The comprehension axiom is being invoked when we say given 2 let y x E z The formula 6 may refer to z and to other sets7 but not to y In general given a formula 0x the family x is referred to as a class7 it may not be a set For example7 the class of all sets is Vx 11 12 11 O H Classes that are not sets are referred to as proper classes Every set a is a class7 since the formula z E 177 de nes it The comprehension axioms say that the intersection of a class and a set is a set We use boldface characters to refer to classes De ne X Y7 X Y7 and X and show they exist The ordered pair is de ned by 710 ln Lid Show it exists Show the ltz7ygt ltu7pgt iff z u and y i The cartesian product is de ned by XgtltYltxygtz Xandy Y Show it exists A function is identi ed with its graph For any sets X and Y we let YX be the set of all functions with domain X and range Y Show this set exists Given a function f A gt gt B and set C Q A the restriction of f to 0 written f r C is the function with domain 0 and equal to f everywhere in C Show that it exists f C is the set of all elements of B that are in the image of C Show that it exists Prove w exists ie that there does exist a smallest such Prove for any formula 0p if 90 and Vd E w6p a 6p 1 then Vd E w Suppose G Z a Z Show that for any x E Z there exists a unique f u a Z such that f0 z and for all n E w fn 1 Let V7 E be a graph lnformally7 two vertices in any graph are connected iff either they are the same or there is a nite path using the edges of the graph connecting one to the other Use the preceding problem to formally de ne and prove that the relation z is connected to y written z N y exists and is an equivalence relation on V Equivalence classes of N are called the components of the graph Let A and B be disjoint sets and f A a B and g B a A be one to one functions Consider the bipartite graph V which has vertices A U B and edges given by the union of the graphs of f and g ie7 there is an edge between a E A and b E B iff either fa b or gb 1 Describe what the nite components of V must look like as a subgraph of V Describe the in nite components of V De ne le lYl iff there is a one to one onto map from X to Y We say X and Y have the same cardinality De ne le S lYl iff there is a one to one map from X to Y De ne le lt lYl iff le S lYl and le 31 Cantor Shroder Bernstein Show that if lAl 3 Bl and lBl S lAl then lAl Bl Show that lAl S Show that if lAl 3 Bl and lBl S 0 then lAl S 112 113 114 115 116 117 118 119 120 121 122 126 127 128 129 Show that lPXl l01Xl Cantor Show that le lt Show that the class of sets7 V7 is not a set Show that 1A gtlt B gtlt O 1A gtlt B gtlt Cl Show that lABXCl 1ABCl Show that if there is a function f A gt gt B that is onto7 then lBl S 1 A set is nite i it can be put into one to one correspondence with an element ofw A set is countable i it is either nite or of the same cardinality as u A set is uncountable i it is not countable R is the set of real numbers and we use c lRl to denote its cardinality which is also called the cardinality of the continuum Below7 you may use whatever set theoretic de nitions of the integers7 rationals and real numbers that you know For example7 you may regard the reals as either Dedekind cuts in the rationals7 equivalences classes of Cauchy sequences of rationals7 in nitely long decimals7 or 7points on a line Show that the set of integers Z is countable Show that the set of odd positive integers is countable Show that the set of points in the plane with integer coordinates is countable Show that the countable union of countable sets is countable 2 For any set X let X be the nite subsets of X Show that the set of nite subsets of u which is written wltw is countable Show that if there are only countably many atomic sentences then the set of all propo sitional sentences is countable Show that the set of rationals Q is countable Remark A clever mapping of the positive rationals to the positive integers is M kn Z7 quot3917 2k 2k Zl 1 21 1 qtq 1s mapped to 191 1mmquot q11 qmm 1 m A number is algebraic i it is the root of some polynomial with rational coef cients Show that the set of algebraic numbers is countable Show that any nontrivial interval in R has cardinality c Show that Pw has cardinality c Show that the set of all in nite subsets of u which is written MW7 has cardinality c Show that the cardinality of R gtlt R is c 1This requires the axiom of choice It is open if it is equivalent to AC1 2Do you think you needed to use the Axiom of Choice 130 131 132 133 For any set X let X be the countably in nite subsets of X Show that lRwl HRH 3 c Show that the cardinality of the set of open subsets of R is c Show that the set of all continuous functions from R to R has size c Show that to has cardinality c Wellorderings A linear order L7 3 is a wellorder iff for every nonempty X Q L there exists z E X such that for every y E X x S y x is the minimal element of X For an ordering S we use lt to refer to the strict ordering7 ie z lt y iff x S y and not z 31 y We use gt to refer to the converse order7 ie z gt y iff y lt x Prove Let L7 3 be any well ordering and f L a L an increasing function Way 6 L x lt y a f lt Then for every x in L x S For two binary relations R on A and S on B we write AR 2 B75 iff there exists a one to one onto map f A a B such that for every my in A mRy iff fzSfy Such a map is called an isomorphism lf L1L7 1 and L27 32 are well orders and L1L7 1 2 L27 lt2 then show the isomorphism is unique Let L7 3 be a wellorder and for any a E L let La c E L c lt a Show that L7 3 is not isomorphic to La7 lt for any a E L Cantor Show that for any two wellorders exactly one of the following occurs they are isomorphic7 the rst is isomorphic to an initial segment of the second7 or the second is isomorphic to an initial segment of the rst Hint Let L7 3 and K7 3 be two wellorders Let G lta7bgt Lav 2 K177 Show that G is the graph of an order preserving bijection whose domain is all of L or whose range is all of K Axiom of Choice AC Axiom of Choice For every family F of nonempty sets there exists a choice function7 ie a function f with domain F such that for every x in F7 f E x WO Well ordering Principle Every nonempty set can be well ordered 3See previous footnotei 31 32 33 34 TL Tuekey s Lemma Every family of sets with nite character has a maximal ele ment A family of sets F has nite character iff for every set X7 X E F iff for every nite Y Q X7 Y E F MP Maaimality Principle Every family of sets closed under the unions of chains has a maximal member ZL Zara s Lemma Every family of sets contains a maximal chain Show that ZL implies MP Show that MP implies TL Show that TL implies AC Zermelo Show that AC implies WO Hint Given X use AC to get a function f PX gt gt X such that fA E X A for all A a proper subset of X Call a well ordering L7 3 respectful iff L Q X and for every a E L fLa a Show that the union of all respectful well orderings is a well ordering of X Given a nonempty family f let lt be a strict well ordering of f Say that a chain C Q f is greedy iff for every a E f if b CbltaUa is a chain7 then either a E C or b lt a for every b E C Show that the union of all greedy chains is a maximal chain Conclude that WO implies ZL Ordinals A set X is transitive iff Va 6 X x Q X A set 04 is an ordirial iff it is transitive and strictly well ordered by the membership relation de ne x S y iff z E y or z y then 047 S is a wellordering We also include the empty set as an ordinal For ordinals oz and B we write 04 lt B for 04 E B The rst in nite ordinal is written w We usually write 0W1m mhnqnQLHWn71L3wQLZH Show If 04 is an ordinal then so is 04 1 Remember oz 04 U a Such ordinals are called successor ordirials Ordinals that are not successors are called limit ordirials Show If 04 is an ordinal and B lt 04 then B is an ordinal and B Q 04 and B y 6 oz V66 Axiom of Regularity V7 3yy 32z yzEx 43 44 45 46 410 411 412 413 Another way to say this is that the binary relation R uv E z gtlt z u E 1 has a minimal element ie there exist 2 such that for every y E x it is not the case that zRy Note a minimal element is not the same as a least element Show 04 is an ordinal iff 04 is transitive and linearly ordered by the membership relation For any ordinals Oz and 6 show that 04 6 04 or 04 6 B Show any two ordinals are comparable ie for any two distinct ordinals Oz and 6 either 04 E B or B E a The union of set A of ordinals is an ordinal and is supA Show that the intersection of a nonempty set A of ordinals is the least element of A written mfA Hence any nonempty set of ordinals has a least element Prove trans nite induction Suppose 0 and Va 6 ORD if VB lt 04 156 then a Then Va 6 ORD a Replacement Scheme Axioms Va Vz E a ly 7xy a 3bV 6 y 6 b 7xy The formula 7 may refer to a and to other sets but not to b Replacement says that for any function that is a class the image of a set is a set If F is a function then for any set a there exists a set b such that for every x E a there exists a y E b such that y von Neumann Let L S be any well ordering Show that the following is a set zoz z E La E ORD and th 2 04 Show that every well ordered set is isomorphic to a unique ordinal Let ORD denote the class of all ordinals Trans m39te Recursion If F is any function de ned on all sets then there exists a unique function G with domain ORD such that for every 04 in ORD 1a FG 04 This is also referred to as a trans nite construction of G Suppose F V a V ie a class function De ne g an ordinary set function to be a good guess iff domg 04 E ORD 90 F and 96 Fg 6 for every 6 lt a Show that if g is a good guess then 9 B is good guess for any 6 lt a Show that if g and g are good guesses with the same domain then 9 9 Show that for every 04 E ORD there exists a necessarily unique good guess 9 with domain a Fraenkel Prove trans nite recursion Explain the proof of WO implies ZL in terms of a trans nite construction 416 For an example7 consider the de nition of Va for every ordinal a Let Vb Q V0411 PVa power set for successor ordinals7 and for limit ordinals VA U ltAV Thus if we de ne F as follows Pa if z is a function with domain 04 1 E ORD i UKA xoz if z is a function with domain limit ordinal A 7 139 if z 7 otherwise then 1a Va Show that if 04 S B then Va Q V and if 04 lt B then Va 6 Show that each Va is transitive Show that every set is included in a transitive set Show that for every transitive set x there exists an ordinal 04 such that z 6 Va ie7 V UQEORDVD Ordinal arithmetic 046 are ordinals7 and A is a limit ordinal Addition 04 0 Oz a 1a 1 ozAsupoz ltA Multiplication 040 0 MB 1 a H a DA supoz B lt A Exponentiation Oz 1 09 ago 04quot supoz B lt A So for example the addition function ORD gtlt ORD gt gt ORD exists by trans nite recursion For each 04 E ORD de ne a function Fa on all sets as follows Fag 96 1 if g is a map with domain an ordinal 6 17 Fag supg y y lt A if g is a map with domain a limit ordinal A7 and Fag Oz otherwise Hence for each 04 we have a unique Ga ORD gt gt ORD which will exactly be Gum 04 6 Since each Ga is unique we have de ned the function on all pairs of ordinals Note that more intuitively 04 6 is the unique ordinal isomorphic to the well order 0 gtlt 04 U gtlt B ordered lexicographically Similarly 04 B is the unique ordinal isomorphic to the well order B gtlt 04 ordered lexicographically Exponentiation is much harder to describe Showthatoz rya y 51 52 54 55 For any ordinals oz and B gt 0 show there exists unique ordinals y and 6 such that oz y6and6lt Show for any 6 gt 0 there exists unique ordinals 71 72gt gt7 0ltd1d2dnltw and 77md17dn such that 71 gt B wlldl wlzdg rowdy This is called Cantor normalform Cardinal Arithmetic An ordinal H is a cardinal i for every oz lt H lozl lt The cardinality of a set A is the least cardinal H lAl W and we write lAl H The oz h uncountable cardinal is written either Na or Low Show that for any ordinal oz the cardinal Na exists ls there a cardinal such that Na oz 7 For cardinals H and y we de ne Ivy to be the cardinality of the cross product and H y to be the cardinality of the union of A and B where A and B are disjoint and lAl H and lBl 7 Let H be an in nite cardinal De ne the lewicographical order 3 on H gtlt H by my 3 um i z lt u or x u and y S 1 De ne 3 on H gtlt H by my 3 um i maxzy lt mauv or mazxy mauv and pg 3 1111 Show that 29201 x n 3 Show that for in nite cardinals H and y H y Ivy mazH y Show that for any in nite cardinal H the union of H many sets of cardinality H has cardinality H The co rzalz39ty of an in nite limit ordinal B of 7 is the least oz 3 B such that there is a map f oz a 6 whose range is unbounded in B For A a limit ordinal show the following are all equivalent a oz is the minimum ordinal such that 3X Q A unbounded in A such that X7 3 2 oz7 S b oz is the minimum ordinal such that 3f oz a A such that f is one to one7 order preserving7 and the range of f is co nal unbounded in A c ofA oz For Is an in nite cardinal show that of oz i oz is the minimum cardinal such that H is the union of oz many sets of cardinality less than H 513 514 Let Oz and B be lirnit ordinals and suppose f a a B is strictly increasing and co nal in B Show cfa cf H is regular iff cfs H H is singular iff cfs lt H Show that for any limit ordinal B cf is a regular cardinal K is the least cardinal greater than H regular cardinal For 04 a limit ordinal show that cfNa cfa Show that for any in nite cardinal H K is a H7 is the set of all functions from y to H but we often use it to denote its own cardinality Hlt7 is UHD 04 lt 7 but we often use it to denote its own cardi nality7 ie7 Hlt7 Moll Note in the section all exponentiation is cardinal exponentiation Show that l ltwl HHFWl H for any in nite cardinal H HEW is the set of nite subsets of H Show that NW lt NE Show that for any cardinal H H lt Hm Konig Show that cf2 gt H
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'