Exercises for Unit VI Infinite constructions in set theory VI 1 Indexed families and set theoretic operations Halmos 4 8 9 Lipschutz 5 3 5 4 Problems for study Lipschutz 5 3 5 6 5 29 5 32 9 14 Exercises to work 1 Generalize Exercise 12 from Section I I I 1 to unions and intersections of arbitrary indexed families of sets Suppose that we have nonempty indexed families of sets A j j J and C j j J such that A j C j for all j Prove the following relationships j J A j j J Cj j J A j j J Cj 2 Generalize DeMorgan s laws to unions and intersections of arbitrary indexed families of sets as follows Suppose that S is a set and we have a nonempty indexed families of subsets of S of the form A j j J Prove the following identities S S j J j J Aj Aj j J j J S A j S A j 3 Halmos p 35 a Given that A j j X and B k k Y are nonempty indexed families of sets prove the following indexed distributive identities j J A j k K B k j k A j B k j J A j k K B k j k A j B k b Suppose that I j j J is an indexed family of sets and write K Ij j J Suppose we are also given an indexed family of sets A k k K Prove the following identities assuming in the second case that each of the indexed families is nonempty k K Ak j J Ai i Ij Ak k K j J Ai i Ij 4 Halmos p 37 a Let A j j J and B k k K be indexed families of sets Prove that j J A j k K B k j k A j B k another indexed distributive law and that a similar formula holds for intersections provided that all the indexing sets are nonempty b Let X j j J be an indexed family of sets Prove that j J X j j J Xk X j for all k J Furthermore if M and N are sets such that M X j N for all j prove that M j J X j and j J X j N V I 2 Infinite Cartesian products Halmos 9 Lipschutz 5 4 9 2 Problems for study Lipschutz 5 11 Exercises to work 1 A product of products is a product Let X j be a family of nonempty sets with Jk indexing set J and let J map from j X j to the set k K be a partition of J Construct a bijective k K X j j Jk Hint Use the Universal Mapping Property 2 Let J be a set and for each j Prove that there is a unique map F J let f j X j Y j be a set theoretic map j fj j Xj j Yj defined by the conditions pj Y F f j pjX where p j and p j denote the j th coordinate projections for j X j and j Y j respectively Also prove that this map is the identity map if each f j is an identity map X Y Finally if we are also given sets Z j with maps g j Y j Z j and G j g j show that G F j gj then f j Notation The map of products j f j constructed in the preceding exercise is frequently called the product of the maps f j 3 Let X j and Y j be indexed families sets with the same indexing set J and assume that for each j J the mapping f j X j Y j is a bijection Prove that the product map j f j j X j j Y j is also a bijection Hint What happens when one takes the product of the inverse maps 4 Suppose in the preceding exercise we only know that each mapping f j is an injection or each mapping f j is a surjection Is the corresponding statement true for the product map In each case either prove the answer is yes or find a counterexample Coequalizers Here is another fundamental example of a universal mapping property Given two functions f g A B a coequalizer of f and g is defined to be a map p B C such that p f p g which has the following universality property Given an arbitrary map q B D such that q f q g then there exists a unique mapping h C D such that q h p In geometrical studies such constructions arise naturally if one tries to build an object out of two simpler pieces by gluing them together in some manner say along their edges and there are also numerous other mathematical situations where examples of this concept arise 5 Prove that every pair of functions f g A B has a coequalizer Hint Consider the equivalence relation generated by requiring that f x be related to g x for all x in A 6 In the setting of the previous exercise suppose that p B C and r B E are coequalizers of f and g Prove that there is a unique bijection H C E such that r H p Hint Imitate the proof of the corresponding result for products VI 3 Transfinite cardinal numbers Halmos 22 23 Lipschutz 6 1 6 3 6 5 Problems for study Lipschutz 6 4 6 12 Exercises to work 1 Halmos p 92 Prove that the set F S of finite subsets of a countable set S is countable and it is countably infinite if and only if S is countably infinite 2 Suppose that E is an equivalence relation on a countably infinite set S and let S E be the associated family of equivalence classes Explain why S E is countable VI 4 Countable and uncountable sets Halmos 23 23 Lipschutz 6 3 6 7 Problems for study Lipschutz 6 2 6 3 6 14 6 32 Exercises to work 1 2 Halmos p 95 Let be cardinal numbers such that Prove that and and Let 0 be a cardinal number Prove that 0 0 1 and 1 1 3 Let R denote the set of all 1 1 correspondences from the real numbers to R R itself Prove that the cardinal number of R is equal to 2 Hint Why is 2 equal R R to R Why is R a subset of R and what conclusion does this yield Next for each subset of R define a 1 1 correspondence from R to itself as follows Since we have R R R it follows that we can partition R into two pairwise disjoint subsets A and B that are each in 1 1 correspondence with R let f and g be 1 1 correspondences from R to A and B respectively For C R define …