Massachusetts Institute of Technology Handout 33 6.042J/18.062J: Mathematics for Computer Science October 27, 2000 Professors Nancy Lynch and Srinivas Devadas

Mini-Quiz 7

1. Write your name:

2. Injections, Surjections, and Bijections

Let g be a function from A to B, and f a function from B to C. The composition f ∘ g is defined by: f ∘ g(x) = f(g(x)).

Determine whether each of the following statements is true or false. If it’s true, prove it. If it’s false, give a counterexample.

(a) If f and g are both injective then f ∘ g is injective.

Solution: Let x,y be any two distint elements in A. Since g is one-to-one (surjective), g(x) and g(y) are distinct elements in B. Since f is one-to-one, f(g(x)) and f(g(y)) are distince elements of C. Thus, f ∘ g is injective.

(b) If f and g are both surjective then f ∘ g is surjective.

Solution: Let y be an arbitrary element in C. Since f is surjective, y = f(b) for some element b ∈ B. Since g is also surjective, there must exist an x ∈ A such that b = g(x). Therefore, for any element y ∈ C, there exists an element x ∈ A such that y = f(g(x)). Thus, f ∘ g is surjective.