Skip to main content

Chapter 6 Injections and Surjections

Let \(X,Y,Z\) be finite sets, perhaps of different sizes. Let \(f:X \rightarrow Y\) and \(g:Y \rightarrow Z\text{.}\) Decide whether each of the following statements is true or false.

  • If the statement is true, provide a proof. (It will be easier to prove the contrapositive.)

  • If the statement is false, provide a counterexample.

Exercises Practice Problems

1.

If \(g \circ f\) is injective then \(f\) is injective. Solution.

true. We will give TWO proofs. First, we prove the contrapositive statement. If \(f\) is not injective then \(g \circ f\) is not injective. Know: There exist \(x_1, x_2 \in X\) such that \(x_1 \neq x_2\) and \(f(x_1) = f(x_2)\text{.}\) Show: There exist \(a_1, a_2 \in X\) such that \(a_1 \neq a_2\) and \(g \circ f(a_1) = g \circ f(a_2)\text{.}\)

  • Pick \(x_1, x_2 \in X\) such that \(x_1 \neq x_2\) and \(f(x_1) = f(x_2)\text{.}\)

  • Then we have \(x_1 \neq x_2\) and \[ g \circ f (x_1) = g(f(x_1)) = g(f(x_2)) = g \circ f(x_2). \]

  • In other words, taking \(a_1=x_1\) and \(a_2=x_2\) satisfies our Show statement.

  • Therefore \(g \circ f: X \rightarrow Z\) is not injective.

Next, we prove the original statement. Know: If \(x_1 \neq x_2 \) then \(g \circ f(x_1) \neq g \circ f(x_2)\text{.}\) Show: If \(x_1 \neq x_2 \) then \(f(x_1) \neq f(x_2)\text{.}\)

  • Pick any \(x_1 \neq x_2\text{.}\) We know that \(g \circ f(x_1) \neq g \circ f(x_2).\)

  • Let \(y_1=f(x_1)\) and \(y_2 = f(x_2)\text{.}\)

  • Then \(g \circ f(x_1) \neq g \circ f(x_2)\) is equivalent to \(g (y_1) \neq g (y_2).\)

  • Since \(g\) is well defined function, we must have \(y_1 \neq y_2\text{.}\)

  • This is the same as saying that \(f(x_1) \neq f(x_2)\text{.}\)

  • Therefore \(f: X \rightarrow Y\) is injective.

2.

If \(g \circ f\) is injective then \(g\) is injective. Solution.

false. Here is a counterexample.

3.

If \(g \circ f\) is surjective then \(f\) is surjective. Solution.

false. Here is a counterexample.

4.

If \(g \circ f\) is surjective then \(g\) is surjective. Solution.

true. We give two proofs. First, we prove the contrapositive: If \(g\) is not surjective then \(g \circ f\) is not surjective. Know: There exists \(z \in Z\) such that for all \(y \in Y\text{,}\) \(g(y) \neq z\text{.}\) Show: There exists \(z \in Z\) such that for all \(x \in X\text{,}\) \(g \circ f (x) \neq z\text{.}\)

  • Let \(f(X) = \{ f(x) \mid x \in X \}\) be the image of \(f\text{.}\)

  • Obviously \(f(X)\) is a subset of \(Y\text{.}\) So for all \(y \in f(X)\text{,}\) we know that \(f(y) \neq z\text{.}\)

  • Pick any \(x \in X\text{.}\) Then \(g \circ f(x) = g(f(x))\text{.}\) We have \(f(x) \in Y\text{,}\) and therefore \(g(f(x)) \neq z\text{.}\)

  • This proves that \(g \circ f: X \rightarrow Z\) is not surjective.

Next, we prove the original statement: Know: For all \(z \in Z\) there exists \(x \in X\) such that \(g \circ f(x) = z\text{.}\) Show: For all \(z \in Z\) there exists \(y \in Y\) such that \(g (y) = z\text{.}\)

  • Pick any \(z \in Z\text{.}\)

  • There is an \(x \in X\) such that \(g \circ f(x) = z\text{.}\)

  • Let \(y= f(x)\text{.}\)

  • Then \(g(y) = g(f(x)) = g \circ f(x) =z\text{.}\)

  • We found a \(y \in Y\) such that \(g(y)=z\text{.}\)

  • Therefore \(g\) is surjective.