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. Even and Odd Subsets.

Let \(\mathcal{E} = \{S \subseteq [7] : |S| \text{ is even}\}\) and let \(\mathcal{O} = \{S \subseteq [7] : |S| \text{ is odd}\}\text{.}\) Consider the function \(\mathcal{C}:\mathcal{E} \to \mathcal{O}\) defined by the rule \(\mathcal{C}(S) = \overline{S}\text{,}\) the complement of \(S\text{.}\)

1. Give an example of an element \(S\) of the domain of this function, then compute \(\mathcal{C}(S)\text{.}\)

2. How do we know that \(\mathcal{C}\) is well-defined; that is, given \(S \in \mathcal{E}\text{,}\) how do we know \(\mathcal{C}(S) \in \mathcal{O}\text{?}\) Is there anything special about the choice of the number \(7\) in this problem?

3. What are the steps to prove that \(\mathcal{C}\) is injective?

4. What are the steps to prove that \(\mathcal{C}\) is surjective?

5. 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)\)

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.