Skip to main content

Chapter 3 Functions

Let \(X,Y\) be finite sets, perhaps of different sizes. Let \(f:X \rightarrow Y\text{.}\) We have the following definitions

Injective (One-To-One)

  • The function \(f: X \rightarrow Y\) is injective if whenever \(f(x_1) = f(x_2)\text{,}\) then \(x_1 = x_2\text{.}\)

An equivalent formulation is the contrapositive of this statement:

  • The function \(f: X \rightarrow Y\) is injective (one-to-one) if for all \(x_1 \neq x_2\text{,}\) we have \(f(x_1) \neq f(x_2)\text{.}\)

Surjective (Onto)

  • The function \(f: X \rightarrow Y\) is surjective (onto) if for every \(y \in Y\text{,}\) there exists some \(x \in X\) such that \(f(x)=y\text{.}\)

Bijective

  • The function \(f: X \rightarrow Y\) is bijective if it is both injective and surjective.

Exercises Practice Problems

1. Not Injective and Not Surjective.

By negating the statements above, write down definitions for "not injective" and "not surjective." Solution.

  • Not Injective: The function \(f: X \rightarrow Y\) is not injective if there exist \(x_1 \neq x_2\) in \(X\) such that \(f(x_1) = f(x_2)\text{.}\)

  • Not Surjective: The function \(f: X \rightarrow Y\) is not surjective if there exists \(y \in Y\) such that for all \(x \in X\text{,}\) we have \(f(x) \neq y\text{.}\)

2. Example Functions.

In each of the following problems, give an example of a function \(f: [n] \rightarrow [m]\) of the specified type. You get to pick the values for \(n\) and \(m\text{.}\) Describe your function by using a picture.

Then decide if there is a required relationship between \(n\) and \(m\text{,}\) the sizes of the domain and the codomain. Your options are:

\begin{equation*} \begin{array}{cccc} n > m, & n = m, & n < m, & \mbox{none}. \end{array} \end{equation*}

  1. \(f: [n] \rightarrow [m]\) is injective (one-to-one) but NOT surjective (onto) Solution.

    Required relationship: \(n < m\)

  2. \(f: [n] \rightarrow [m]\) is injective (one-to-one) and surjective (onto) Solution.

    Required relationship: \(n = m\)

  3. \(f: [n] \rightarrow [m]\) is NOT injective (one-to-one) but is surjective (onto) Solution.

    Required relationship: \(n > m\)

  4. \(f: [n] \rightarrow [m]\) is NOT injective (one-to-one) and NOT surjective (onto) Solution.

    Required relationship: none

3. Prove or Disprove.

Let \(X,Y,Z\) be finite sets, perhaps of different cardinalities. 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. (Pro tip: It might be easier to prove the contrapositive.)

  • If the statement is False, provide a counterexample.

Here are the statements:

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

    True. We prove the contrapositive: if \(f\) is not injective then \(g \circ f\) is not injective.

    • Since \(f\) is not injective, there exist \(x_1, x_2 \in X\) such that \(x_1 \neq x_2\) and \(f(x_1) = f(x_2)\text{.}\)

    • This means that \(g \circ f(x_1) = g (f (x_1)) = g(f(x_2)) = g \circ f(x_2)\) (and still \(x_1 \neq x_2\)).

    In other words, \(g \circ f\) is not 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: the same counterexample as in the previous problem

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

    True. We prove the contrapositive: if \(g\) is not surjective then \(g \circ f\) is not surjective.

    • Since \(g\) is not surjective, there exist \(z \in z\) such that for all \(y \in Y\text{,}\) we have \(g(y) \neq z\text{.}\)

    • This means that \(z\) is not mapped to by \(g \circ f\) as well. Indeed, for any \(x \in X\text{,}\) we have \(f(x)=y\) for some \(y \in Y\text{.}\) By the previous statement, \(z \neq g(y) = g(f(x)) = g \circ f(x).\)

    In other words, \(g \circ f\) is not surjective.