Discrete Mathematics: Activities and Exercises

1. A function from \(\R^2\) to \(\R^2\).

Let \(f: \R \times \R \rightarrow \R \times \R\) be defined by \(f(x,y) = (2y, x-y)\text{.}\) Is \(f\) injective? surjective? Justify your answer with either a proof or a counterexample.

2. Another function from \(\R^2\) to \(\R^2\).

Let \(f: \R \times \R \rightarrow \R \times \R\) be defined by \(f(x,y) = (5x+5y, x+y)\text{.}\) Is \(f\) injective? surjective? Justify your answer with either a proof or a counterexample.

3. Functions from \(\Z\) to \(\Z\).

1. Create a function \(f: \Z \rightarrow \Z\) that is bijective.

2. Create a function \(f: \Z \rightarrow \Z\) that is injective but not surjective.

3. Create a function \(f: \Z \rightarrow \Z\) that is surjective but not injective.

4. Create a function \(f: \Z \rightarrow \Z\) that is not injective and not surjective.

4. The Image of a Subset.

Let \(f : X \rightarrow Y\) be a function. Let \(A \subset X\) and \(B \subset X\text{.}\) For a subset \(S \subset X\text{,}\) define the subset \(f(S) \subset Y\) by

1. Prove that if \(A \subset B\) then \(f(A) \subset f(B)\)

2. Draw an example for which \(A \not\subset B\text{,}\) but \(f(A) \subset f(B)\text{.}\)

3. Prove that \(f(A \cap B) \subset f(A) \cap f(B)\text{.}\)

4. Draw an example for which \(f(A \cap B) \neq f(A) \cap f(B)\)

5. The Identity Function.

The identity function \(\mbox{Id}_X: X \rightarrow X\) is given by \(\mbox{Id}_X(x) = x\text{.}\) (So every element just maps to itself.) Let \(f : X \rightarrow Y\) and \(g: Y \rightarrow X\) be functions so that \(g \circ f = \mbox{Id}_X\text{.}\)

1. Give an example where \(g \circ f = \mbox{Id}_X\) but \(f \circ g \neq \mbox{Id}_Y\text{.}\)

2. Prove that if \(g \circ f = \mbox{Id}_X\) then \(f\) is injective.

3. Prove that if \(g \circ f = \mbox{Id}_X\) then \(g\) is surjective.

6. Clock Math.

For a fixed \(n\text{,}\) let \(\Z_n = \{ 0,1,2, \ldots, n-1 \}\text{.}\) We define a function \(f: \Z \rightarrow \Z_n\) by \(f(k) = k \mbox{ mod } n\text{,}\) which is the integer remainder when \(k\) is divided by \(n\text{.}\)

1. Consider the function \(f: \Z \rightarrow \Z_{5}\) given by \(f(k) = k \mbox{ mod } 5.\) Is \(f\) injective? Is \(f\) surjective? Justify your answers.

2. Consider the function \(g: \Z_{6} \rightarrow \Z_{6}\) given by \(g(k) = 2k \mbox{ mod } 6\text{.}\) Is \(g\) injective? Is \(g\) surjective? Justify your answer.

3. Consider the function \(h: \Z_{7} \rightarrow \Z_{7}\) given by \(g(k) = 2k \mbox{ mod } 7\text{.}\) Is \(h\) injective? Is \(f\) surjective? Justify your answer.

4. Fix a positive integer \(n\text{,}\) and consider the function the function \(g: \Z_{n} \rightarrow \Z_{n}\) given by \(g(k) = 2k \mbox{ mod } n\text{.}\) Prove that this function is injective if and only if \(n\) is odd. Then prove that this function is surjective if and only if \(n\) is odd.