21 127 Exam 2 Review Materials Mary Radcli e Major topics for your second exam include Basics of set theory Including understanding of unions intersections power sets Cartesian Products and how to prove two sets are equal DeMorgan s Laws for sets Well Ordering Principle Basics of functions Including de nition of function as well as key terms domain codomain graph well de ned composition image preimage Understanding of how to prove that a function is well de ned and ma nipulate other basic properties More sophisticated function stu understanding of injectivity surjectiv ity bijectivity Understanding of how to prove a function satis es any of these criteria Knowing how these properties relate to left right and two side inverses theorems about counting unions intersections products etc Finite counting De nitions and theorems Basic combinatorial tools permutations cid 0 X k Inclusion Exclusion Basic cid 1 binomial coe cients Count ing techniques Counting in 2 ways bijections using Cartesian products Binomial Theorem applications In nite sets De nitions of countable uncountable Theorems about how to determine if a set is countably in nite Know which sets are which sizes and how to tell 1 Let A B C be subsets of the universe Z Prove each of the following Some practice problems identities a A B C A B A C b A B A Bc A c Ac Z c A d A B C A B A C 2 Let f x x2 3 and let g x x2 2 Let A f R and let B g R the images of R under these functions Prove that B A but A cid 54 B 3 Let A x R 3 x 2 and let B x R x2 x 6 0 Prove that A B 1 4 Let S N be a set that has the following property n m S n m S Let cid 96 be the minimum of S note the minimum exists because of Well Ordering Prove that every element of S is divisible by cid 96 using the Well Ordering Principle 5 Use the Well Ordering Principle to formally prove something we have as sumed all along every integer n N is either even or odd 6 Let f X Y be a function Suppose there exists y1 y2 Y with y1 cid 54 y2 such that f 1 y1 f 1 y2 Prove that y1 f X and y2 f X 7 Let Q be the set of positive rational numbers Let f Q N be de ned by f q n where n is the numerator of q Is this a well de ned function If so prove it If not explain why not and make an appropriate modi cation to produce a well de ned function 8 Let f X Y be a function and let A X Prove that for all B Y f 1 A B f 1 B A 9 Let f R2 R be a function de ned by f x y x and let g R R2 be a function de ned by g x x 0 Show that g is a right inverse for f but not a left inverse Show that g is not unique as a right inverse that is there exists another function h that is a right inverse to f and h cid 54 g 10 Determine the number of positive integers less than 2000 that are multiples of 4 7 and 13 11 Talking to one of your professors you nd out that he has been working at CMU for 30 years and has taught 2 di erent courses each semester You also nd out that he has only taught 10 di erent courses Your friend then immediately says that at least two of his semesters must have been the same Is your friend right How did he know 12 Let n m N How many functions f n m are injections 13 Let n N How many surjective functions are there from n to 3 Hint rst think about counting functions that are NOT surjective 14 You are planning to volunteer at a homeless shelter for 3 days in May hey good for you You can pick any 3 days but you don t ever want to work two days in a row How many di erent ways can you choose the days 15 How many ags can you make that consist of three horizontal stripes of the colors red white blue green and black where consecutive stripes must be di erent colors 16 Prove by counting in two ways that for any n s N we have cid 18 n n k cid 19 cid 18 s 1 cid 19 k 1 cid 18 n s 1 cid 19 n 1 n cid 88 k 1 17 Prove using counting in two ways that for all k n N Hint think about a subset in terms of its largest element cid 18 j cid 19 k n cid 88 j k cid 18 n 1 cid 19 k 1 2 18 Prove that n cid 88 n k cid 88 k 0 j 0 n k j n k j 3n 19 Let X be an in nite set and let S X be nite Prove that X X S 20 Let A be nite B be countably in nite C be countable and D be un countable What can you say about the cardinalities of the following sets a A B b A C c A C d B D e D B f B D g C D 21 Explain Cantor s diagonalization argument 22 Let B R be a set of numbers having the properties b 0 b B If S B is a nite set then cid 88 b S b 3 Prove that B is countable Hint how many elements of B can be greater than 1 n for each n N 3