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

and

are functions where f and g are both one to one correspondences, then so is gf.

Proof: Assume that f and g are both one to one correspondences. Then f and g are both one to one and onto. If f and g are both one to one then so is gf by Theorem 3.2. If f and g are both onto then so is gf by Theorem 3.3. Conclude that gf is both one to one and onto.