Discrete Mathematics: Activities and Exercises

1. Listing all functions.

List all the functions from \(\{a,b,c \}\) to \(\{ x,y \}\text{.}\) For example, one function \(f_1\) is given by \(f_1(a)=x\) and \(f_1(b)=y\) and \(f_1(c)=y\text{.}\) Solution.

2. Counting functions.

How many functions are there from \(\{a,b,c,d \}\) to \(\{x,y,z \}\text{?}\) This time, justify your answer with an argument rather than listing all possible functions. Solution.

3. More counting functions.

Without making lists or drawing pictures, how many functions are there \(\ldots\)

1. from a four-element set to a ten-element set? Solution.

   \(10^4\)

2. from a ten-element set to a four-element set? Solution.

   \(4^{10}\)

3. from an \(r\)-element set to an \(s\)-element set? Solution.

   \(s^r\)

4. Different Kinds of 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 (also called the "target").

1. Create a function \(f: [n] \rightarrow [m]\) that is injective (one-to-one) but NOT surjective (onto). What is the required relationship between \(n\) and \(m\text{?}\) (One of: \(n >m\) or \(n < m\) or \(n = m\) or "none.") Solution.

   

   {Required Relationship: \(n < m\)}

2. Create a function \(f: [n] \rightarrow [m]\) that is injective (one-to-one) and surjective (onto). What is the required relationship between \(n\) and \(m\text{?}\) (One of: \(n >m\) or \(n < m\) or \(n = m\) or "none.") Solution.

   

   Required Relationship: \(n = m\)

3. Create a function \(f: [n] \rightarrow [m]\) that is NOT injective (one-to-one) but is surjective (onto). What is the required relationship between \(n\) and \(m\text{?}\) (One of: \(n >m\) or \(n < m\) or \(n = m\) or "none.") Solution.

   

   Required Relationship: \(n > m\)

4. Create a function \(f: [n] \rightarrow [m]\) that is NOT injective (one-to-one) and NOT surjective (onto). What is the required relationship between \(n\) and \(m\text{?}\) (One of: \(n >m\) or \(n < m\) or \(n = m\) or "none.") Solution.

   

   Required Relationship: none

5. Injective? Surjective?

For each of the functions below, decide whether it is injective and/or surjective. If it does not satisfy the property, explain why by giving an example that violates the property. If it does satisfy the property, then provide a proof.

1. \(f: \Z \rightarrow \Z\) given by \(\displaystyle{f(n) = \left\lfloor \frac{n}{2} \right\rfloor}\) where \(\left\lfloor x \right\rfloor\) is the floor function, which "rounds down" to the nearest integer. Solution.

   • The function is not injective. For example, \(f(0) = 0 = f(1)\)

   • The function is surjective. Given any \(n \in Z\text{,}\) we have \(f(2n)=n\text{.}\)

2. \(g: \Z \rightarrow \Z\) given by \(g(n) = 4n -1\) Solution.

   • The function is injective. Suppose that \(g(n) = g(m)\text{.}\) This means that \(4n-1=4m-1\text{,}\) so \(4n=4m\) and finally \(n=m\text{.}\)

   • The function is not surjective. It certainly misses all of the even numbers since the right hand side is odd. But we just need one counter example, so let's show that \(g(n) \neq 0\) for all \(n \in \Z\text{.}\) AFSOC (assume for the sake of contradiction) that \(g(n) =0\text{.}\) Then \(0=4n-1\) which means that \(n=1/4\text{.}\) But \(1/4 \notin \Z\text{.}\) Therefore, no element maps to \(0\text{.}\)

3. \(h: \R \backslash \{ 0 \} \rightarrow \R\) given by \(\displaystyle{h(x) = \frac{x+1}{x}}\text{.}\) Solution.

   • The function is injective. This function is equivalent to \(\displaystyle{h(x) = 1+\frac{1}{x}}\text{.}\) Suppose that \(f(a) = f(b)\text{.}\) This means that

     \begin{equation*} \begin{array}{rcl} 1+\frac{1}{a} &=& 1+\frac{1}{b} \\ \frac{1}{a} &=& \frac{1}{b} \\ a &=& b. \end{array} \end{equation*}

   • The function is not surjective. It misses the point \(y=1\text{.}\) Indeed, if \(h(x)=1\) then

     \begin{equation*} \begin{array}{rcl} 1 &=& 1+\frac{1}{x} \\ 0 &=& \frac{1}{x}, \\ \end{array} \end{equation*}

     which is impossible.