Exercises Week 1 - Sets and Functions - Answers
(1.) Let \(f(n) = n+1\). This function is injective, because whenever we have \(f(n)=f(m)\), we have \(n+1=m+1\), which means that \(n=m\). This function is not surjective, because there is no \(n\) such that \(f(n)=0\).
(2.) Let
\[ g(n) = \begin{cases}n-1 & \text{if } n>0 \\ 0 & \text{if } n=0 \end{cases} \]
This function is surjective, because \(g(n+1)=n\) for any \(n\). This function is not injective, because we have \(g(0)=g(1)=0\).
(3.) No. Any injective function \(f : A \rightarrow A\) must also be surjective. Suppose we have an injective function \(f : A \rightarrow A\) that is not surjective. This means that there is an \(a\) in \(A\) such that there is no \(x\) such that \(f(x) = a\). So, really, we have \(f : A \rightarrow (A \setminus \{a\})\). We have 5 elements in \(A\), but only 4 elements in \(A\setminus\{a\}\), which means that \(f\) cannot be injective.
Note: this is because A is finite. There are of course such functions if A would be an infinite set.
(4.) Union and intersection are commutative and associative (see book).
Difference is not commutative, because {1,2} \ {1} = {2}, but {1} \ {1,2} = 0.
Difference is not associative, because ({1,2,3} \ {1,2}) \ {2} = {3}, but {1,2,3} \ ({1,2} \ {2}) = {2,3}.
(5.) We are going to map even natural numbers to positive integers, and odd natural numbers to negative integers. For example: f(0)=0, f(2)=1, f(4)=2, ... and f(1)=-1, f(3)=-2, f(5)=-3, ... In other words:
\[ f(n) = \begin{cases}n/2 & \text{if } n \text{ even} \\ -(n+1)/2 & \text{if } n \text{ odd}\end{cases} \]
This function is injective, because if we have f(n) = f(m), then either both n and m must be even, or both must be odd. If they are even, then we have n/2 = m/2, which means that n=m. If they are odd, then we have -(n+1)/2 = -(m+1)/2, which means that n=m.
This function is surjective: We can reach any y≥0 by f(2y) = 2y/2 = y, and any y<0 by f(-2y-1) = -(-2y-1+1)/2 = -(-2y)/2 = y.
(6.) | A x B | = | A | * | B |.
| A -> B | = | B || A |.
We know that | A | ≤ | A U B | and | B | ≤ | A U B |. We also know that | A U B | ≤ | A |+| B |. It does not have to be equal to | A |+| B |, because A and B can have joint elements.
We know that | A ∩ B | ≤ | A | and | A ∩ B | ≤ | B |.
(7.) Let f(x,y) = x. This is associative, because f(x,f(y,z)) = x, and f(f(x,y),z) = f(x,y) = x. This is not commutative, because f(1,2) = 1, but f(2,1) = 2.
(8.) Let f(x,y) = |x-y|. This is commutative, because f(x,y) = |x-y|, and f(y,x) = |y-x| = |x-y|. This is not associative, because f(1,f(2,3)) = f(1,1) = 0, but f(f(1,2),3) = f(1,3) = 2.
(9.) For our answer to assignment 7: No. We would need to find an e such that f(e,x) = x for all x. But we know that f(e,x) = e.
For our answer to assignment 8: Yes. The identity e is 0. We have f(0,x) = |0-x| = |x| = x. And we have f(x,0) = |x-0| = |x| = x.
(10.) Only for our answer to assignment 8. Any a, b such that f(a,b) = 0 are inverses. This means that |a-b| = 0, which means that if a and b are the same, then they are each other's inverse.