5: Functions and Cardinality Answer these problems on another sheet of paper. Keep everything neat and organized. Show all of your work or thinking. You do not have to simplify factorials unless explicitly told to do so. 1.) Show that the relation D = {(n, m) n, m N, nm} is a partial order. Is this is total order? 2.) Show that R = {(x, y) x, y R, (x y) Z} is an equivalence relation. 3.) Determine if the relations defined below are i.) Reflexive ii.) Symmetric iii.) Antisymmetric iv.) Transitive v.) Functions Some may have more than one of these properties. The relations are: a.) R = {(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)} b.) S = {(1, 1), (2, 2), (3, 3)} c.) T = {(1, 1), (1, 2), (2, 2)} d.) U = {(1, 2), (2, 3), (3, 1)} e.) C = {(x, y) x, y R, x2 + y 2 = 1} f.) F = {(x, y) x, y R, x = 2y} g.) G = {(n, m) n, m N, gcd(n, m) = 1} 4.) Determine if the following relations are functions. If they are determine whether they are injective, surjective, or bijective. a.) f R R, f = {(x, y) x, y R, 2x + 3y = 5} b.) f R R, f = {(x, y) x, y R, y = x2 } c.) f R [0, ), f = {(x, y) x R, y [0, ), y = x2 } d.) f [0, ) [0, ), f = {(x, y) x, y [0, ), y = x2 } 5.) Determine if the following functions are bijections. If they are find their inverses. a.) f = {(1, c), (2, a), (3, b)} b.) f = {(x, y) x, y R, y = 2x 3} c.) f = {(x, y) x, y R, y = x3 2x} 6.) Prove that if f A B is a surjection and A0 A, then f (A) f (A). 7.) Determine the cardinality of the set P = {p N p is prime}. 8.) Prove that if An = {1, 2, 3, . . . , n}, then card(N) = card(N An ). [Hint: use the division algorithm.] 9.) Use the pigeonhole principle to show that if there are 13 people in a room then at least two have the same astrological sign