CmSc 180 – Discrete mathematics
Homework 07 Solutions
1. Give an example of a function that is one-to-one but not onto
Let A = {1,2}, B = {a, b, c}
f: A ® B f = {(1,a), (2,b)}
2. Give an example of a function that is onto but not one-to-one.
Let A = {1,2,3}, B = {a, b}
f: A ® B f = {(1,a), (2,b), (3,b)}
3. Give an example of a function that is neither one-to-one nor onto
Let A = {1,2,3}, B = {a, b, c}
f: A ® B f = {(1,a), (2,b), (3,b)}
4. Give an example of a function that is both one-to-one and onto
Let A = {1,2,3}, B = {a, b, c}
f: A ® B f = {(1,a), (2,b), (3,c)}
5. How many functions are there from A = {1,2} to B = {a, b}? Write them as sets of ordered pairs. Which are one-to-one? Which are onto?
Each function is a subset of the Cartesian product A x B. Therefore all functions are elements of the power set of A x B
A x B = {(1,a), (1,b), (2, a), (2, b)}
P(A x B) =
{ Æ, not a function
{(1,a)}, not a function
{(1,b)}, not a function
{(2, a)}, not a function
{(2, b)}, not a function
{(1,a), (1,b)}, not a function
{(1,a), (2, a)}, function
{(1,a), (2, b)}, function, one-to-one, onto
{(1,b), (2, a)}, function, one-to-one, onto
{(1,b), (2, b)}, function
{(2,a), (2, b)}, not a function
{(1,a), (1,b), (2, a)}, not a function
{(1,a), (1,b), (2, b)}, not a function
{(1,a), (2,a), (2, b)}, not a function
{(1,b), (2,a), (2, b)}, not a function
{(1,a), (1,b), (2, a), (2, b)} } not a function
6. Let X = {1, 2, 3, 4}, Y = {a, b, c, d}. For each of the following subsets of X x Y determine whether it is a function or not. If it is a function, determine whether it is one-to-one, onto, or both. If it is a bijection, determine its inverse function as a set of ordered pairs.
A1 = {(1,a), (2,a), (3,c), (4, b)}
A2 = {(1, c), (2, a), (3, b), (4, c), (2, d)}
A3 = {(1, c), (2, d), (3, a), (4, b)}
A4 = {(1, d), (2, d), (4, a)}
A5 = {(1, b), (2, b), (3, b), (4, b)}
Record the solution in the table below; check the boxes “function”, “1 – 1”, and “onto” if the set has the corresponding properties. Write the inverse in the last column, if the function is a bijection (i.e. both 1 – 1 and onto)
function / 1 - 1 / onto / Inverse (if present)A1 = {(1,a), (2,a),
(3,c), (4, b)} / X
A2 = {(1, c), (2, a), (3, b),
(4, c), (2, d)}
A3 = {(1, c), (2, d),
(3, a), (4, b)} / X / X / X / A3-1 =
{ (a, 3), (b, 4),
(c, 1), (d, 2) }
A4 = {(1, d), (2, d), (4, a)}
A5 = {(1, b), (2, b),
(3, b), (4, b)} / X
7. Do the following sets define functions? If so, give their domain and range:
F1 = {(1, (2,3)), (2, (3,4)), (3, (1,4)), (4, (2,4))}
Function, Domain : {1, 2, 3, 4}, Range: {(2,3), (3,4), (1,4), (2,4)}
F2 = {((1,2), 3), ((2,3), 4), ((3,3), 2)}
Function, Domain : {(1, 2), (2, 3), (3, 3)}, Range: {2, 3, 4}
F3 = {(1, (2,3)), (2, (3,4)), (1, (2,4))}
Not a function
F4 = {(1, (2,3)), (2, (2,3)), (3, (2,3))}
Function, Domain : {1, 2, 3}, Range: { (2, 3)}
8. Let N be the set of all non-negative integers. Determine which of the following functions are one-to-one, which are onto, and which are one-to-one and onto:
a. f: N® N f(n) = n2 + 2 one-to-one, not onto
b. f: N® N f(n) = n(mod 3) not one-to-one, not onto
c. f: N® N f(n) = 1 if n is odd, 0 if n is even , not one-to-one, not onto
d. f: N® {0, 1} f(n) = 1 if n is odd, 0 if n is even, not one-to-one, onto
9. Let X and Y be finite sets. Find a necessary condition for the existence of one-to-one mappings from X to Y.
The number of elements in Y must be greater or equal to the number of elements in X
10. Show that there exists a one-to-one function from A x B to B x A. Is it also onto?
A x B = {(a, b) | a ÎA L bÎB}
B x A = {(b, a) | a ÎA L bÎB}
Define f: A x B ®B x A = {((a,b),(b,a)) | (a,b) Î A x B , (b,a) Î B x A}
It is one-to-one and onto.
One-to-one: (a,b) ¹ (c,d) ® (b, a) ¹ (d, c) (1)
f((a,b)) = (b,a)
f((c,d)) = (d,c)
from (1): f((a,b)) ¹ f((c,d))
onto: show that "y Î B x A $ x Î A x B such that f(x) = y
Let y is (y1, y2) in B x A. (1)
From (1) and by def of Cartesian product B x A: y1 Î B, y2Î A (2)
From (2) and by def of Cartesian product A x B : (y2,y1) Î A x B (3)
From (3) and by def. of f: f((y2,y1)) = (y1,y2).
The choice of y = (y1,y2) was arbitrary.
Thus "y = (y1,y2)Î B x A $ x = (y2,y1) Î A x B such that f(x) = y
Therefore any element in B x A is an image of some element in A x B.
The next problems refer to composition of functions. By definition
f ° g = g(f(x))
11. Let g = {(1, a), (2, c), (3, a)} be a function from X = {1, 2, 3} to Y = {a, b, c, d}, and f = {(a, x), (b, x), (c, z), (d, w)} be a function from Y to Z = {w, x, y, z}. Write g ° f as a set of ordered pairs.
g ° f = f(g(x)) = {(1,x), (2, z), (3,x)}
12. Let f and g be functions from N to N defined by the equations:
f(n) = 2n + 1, g(n) = 3n -1
Find the compositions f ° f , g ° g, g ° f , and f ° g
f ° f = f(f(n)) = 2(2n+1) + 1 = 4n + 3
g ° g = g(g(n)) = 3 (3n – 1) – 1 = 6n - 4
g ° f = f (g(n)) = 2(3n – 1) + 1 = 6n - 1
f ° g = g(f(n)) = 3(2n + 1) – 1 = 6n + 2
13. Let f and g be functions from N to N defined by the equations:
f(n) = n2 , g(n) = 2n
Find the compositions f ° f , g ° g, g ° f , and f ° g
f ° f = f(f(n)) = (n2 ) 2 = n4
g ° g = g(g(n)) = pow(2, 2n )
g ° f = f (g(n)) = (2n )2 = 22n
f ° g = g(f(n)) = pow(2, n2 ) = 2 n*n
14. Represent each function below as a composition of simpler functions
Example:
Let f(x) = 2sin(x + 1)
Consider the functions:
g(x) = x + 1
h(x) = sin(x)
k(x) = 2x
f(x) is the composition (g ° h) ° k = k(h(g(x))
a. f(x) = log 2 (x2 + 2)
Let g(x) = x + 2
h(x) = x2
k(x) = log 2 (x)
f(x) = k (g(h(x))) = h ° g ° k
b. f(x) = sin(2x)
Let g(x) = 2x
h(x) = sin(x)
f(x) = h (g(x)) = g ° h
c. f(x) = (3 + sin (x) ) 4
Let g(x) = sin(x)
h(x) = 3 + x
k(x) = x4
f(x) = k (h(g(x))) = g ° h ° k
d. f(x) = 2sin(x)
Let g(x) = 2x
h(x) = sin(x)
f(x) = g (h(x)) = h ° g
e. f(x) = 1 / (cos(x))3
Let g(x) = cos(x)
h(x) = 1/ x
k(x) = x3
f(x) = h (k(g(x))) = g ° k ° h
5