MATH 2203: Discrete Mathematics Winter 2015 Assignment 4 Due in class, Wednesday, March 11 1. Let S = {1, 2, 3, 4, 5} and let f, g, h : S → S be the functions defined by f = {(1, 2),(2, 1),(3, 4),(4, 5),(5, 3)} g = {(1, 3),(2, 5),(3, 1),(4, 2),(5, 4)} h = {(1, 2),(2, 2),(3, 4),(4, 3),(5, 1)}. (a) Explain why f and g have inverses but h does not. (b) Show that (f ◦ g) −1 = g −1 ◦ f −1 but (f ◦ g) −1 6= f −1 ◦ g −1 . 2. Let A = {x ∈ R | x 6= −3} and define f : A → R by f(x) = x − 3 x + 3 . (a) Show that f is one-to-one. (b) Find rng(f). (c) Define g : A → rng(f) by g(x) = f(x) for all x ∈ A. Find g −1 . 3. Show that the given sets have the same cardinality by finding a bijection between them. In each part, state whether the pair of sets is finite, countably infinite, or uncountable. (a) {Z, Q, R} and {1, 2, 3}. (b) Z and 2Z + 1. (c) The intervals (2, 4) and (1, 7). (d) (0, π 2 ) and R +. (e) Z + and a 2 b | a, b ∈ Z + . 4. (a) Without giving a bijection, explain why the set of all prime numbers is countable. (b) Explain why the set of all continuous functions f : R → R is uncountable. 5. Suppose A and B are sets with A $ B. If A and B are infinite, is it necessarily true that |A| < |B|? Give a proof or a counterexample. 6. Suppose A and B are countably infinite sets. Show that A × B is countably infinite by proving that |A × B| = |Z + × Z +|. 1
