Discrete Mathematics for Computer Scientists -- Exercises Week 1 - Sets and Functions - Answers | DIT980, HT 2017 | ||||||
Home | Schedule | Assignments | Exercises | Book | Exam | About | Fire | Forum | TimeEdit | Links | ||||||
Exercises Week 1 - Sets and Functions - Answers
Exercises 1. Let f(n) = n+1. This function is injective, because whenever we have f(n1)=f(n2), we have n1+1=n2+1, which means that n1=n2. This function is not surjective, because there is no n such that f(n)=0.
2. Let
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 -> A must be surjective. Suppose we have an injective function f : A -> 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 -> (A \ {a}). We have 5 elements in A, but only 4 elements in A\{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 (false,x) to even numbers, and (true,x) to odd numbers:
This function is injective, because if we have f(b1,x1) = f(b2,x2), then we have that b1=b2 (they must be either both even or both odd). If b1=b2=false, we have that 2x1 = 2x2, which means x1=x2. If b1=b2=true, we have that 2x1+1 = 2x2+2, which also means that x1=x2. This function is surjective: We can reach any even number 2n by using f(true,n), and we can reach any odd number 2n+1 by using f(false,n).
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.
|