Description

Discrete Mathematics TAs
(plaigarised primarily from the book)
Questions
1. 10 points Determine whether f : Z × Z → Z is onto if
(a) f(m,n) = 2m − n
(b) f(m,n) = m2 − n2
(c) f(m,n) = m + n + 1
(d) f(m,n) = |m| − |n|
(e) f(m,n) = m2 − 4
2. 5 points if f : A →− B is a one to one function show that there exists a function g : B →− A such that g is onto
3. 5 points if f : A →− B is a onto function show that there exists a function g : B →− A such that g is one to one
4. 5 points Show that for every one-to-one and onto function f : A →− B it has an inverse function g, such that ∀a ∈ A,g(f(a)) = a and ∀b ∈ A,f(g(b)) = b
5. 7 points 1. Let I be the set of decimals of the form 0.d1d2d3d4… Construct a one to one function from I to I × I
2. Find either an onto function from I to I × I or a one to one function from for I × I to I
3. Do I and I × I have the same cardinality?
6. 5 points Let f : A → B and g : B → C
If C0 ⊆ C, show that (g ◦ f)−1(C0) = f−1(g−1(C0))
7. 5 points Let f : A → B and g : B → C
If f and g are injective, show that g ◦ f is injective.
8. 5 points Let f : A → B and g : B → C
If f and g are surjective, show that g ◦ f is surjective.
9. 5 points In mathematics and computer science, the floor function is the function that takes as input a real number x, and gives as output the greatest integer less than or equal to x.
Let g be a function from the set A to the set B. Let S be a subset of B. We define the inverse image of S to be the subset of A whose elements are precisely all pre-images of all elements of S. We denote the inverse image of S by g−1(S), so g−1(S) = {a ∈ A | g(a) ∈ S}. (Beware: The notation g−1 is used in two different ways. Do not confuse the notation introduced here with the notation g−1(y) for the value at y of the inverse of the invertible function g. Notice also that g−1(S), the inverse image of the set S, makes sense for all functions g , not just invertible functions.)
Let g(x) = ⌊x⌋. Find
1
Discrete Mathematics TAs
CS 113 Spring 201 Recitation: Functions (plaigarised primarily from the book)

(a) g−1({0}).
(b) g−1({−1,0,1})
(c) g−1({x | 0 < x < 1}).
10. 5 points Let f be a function from the set A to the set B. Let S be a subset of B. We define the inverse image of S to be the subset of A whose elements are precisely all pre-images of all elements of S. We denote the inverse image of S by f−1(S), so f−1(S) = {a ∈ A | f(a) ∈ S}. (Beware: The notation f−1 is used in two different ways. Do not confuse the notation introduced here with the notation f−1(y) for the value at y of the inverse of the invertible function f. Notice also that f−1(S), the inverse image of the set S, makes sense for all functions f , not just invertible functions.) Let f be a function from A to B. Let S and T be subsets of B. Show that f−1(S ∩ T) = f−1(S) ∩ f−1(T).

Page 2 of 2