Theorem 3.3: If A, B, and C are sets and

and

are functions where f and g are both onto, then so is gf.

Proof: From Definition 3.6, we must show that if c is an element of C, then there is an element a of A such that

gf(a) = c

Let c be an element of C. Since g is onto, there exists an element b in B such that

c = g(b).

Since f is onto, there exists an element a of A such that

b = f(a).

then

gf(a) = g(f(a)) = g(b) = c