240 CHAPTER 4 Functions
- List all 1-1 and onto functions from {1, 2, 31 to itself.
- Let A be a set with three elements and B be a set with two elements.
(a) How many different functions are there with domain A and codomain B?
(b) How many different functions are there with domain B and codomain A?
(c) How many different 1-1 functions are there with domain A and codomain B?
(d) How many different 1-1 functions are there with domain B and codomain A? - Determine which of the following functions are onto:
(a) F 1 :]R -> R where F, (x) = x^2 - 1.
(b) F 2 : --+ Z 2 where F 2 (x) = [x] ([xl is the "ceiling" of x).
(c) F 3 : -Z 2 where F 3 (x) = x3.
(d) F 4 : R -- IR where F 4 (x) = x3.
(e) For the linear ordering < on R, list all the increasing functions among parts (a)
through (d).
(f) For the ordering < on IR, list all the strictly increasing functions among parts (a)
through (d). - Which of the functions in Exercise 12 are 1-1? Prove each of your answers.
- Two months are equivalent if their 13th day must fall on the same day of the week in
every (nonleap) year.
(a) Show that the 13th day of the 12 months occur on seven different days of the week.
(b) Conclude that there must be at least one Friday the 13th in each year.
(c) Show that there are at most three Friday the 13th's in any year.
(d) Show that the result is also true for leap years.
(Hint: Number the days of the year from 1 (January 1) to 365 (December 31), and then
show that the days representing the 13th days of these months occur on seven different
days of the week.) - Let A = {1, 2, 3, 41 and B = {a, b, c}. Define a function F : A -* B as F(1) = a,
F(2) = b, F(3) = c, and F(4) = c. List the ordered pairs of the equivalence relation
R defined on A as x R y if and only if F(x) = F(y). List the elements of the partition
of A determined by this equivalence relation. - Let FTo, 1 , 2 ) be the set of all functions with domain and codomain equal to {0, 1, 21. For
each of the following relations, prove that the relation is an equivalence relation. Also,
find the distinct equivalence classes of each equivalence relation. Let F, G E 510 , 1,21.
(a) F R G if and only if range(F) = range(G).
(b) F R G if and only if max(F) = max(G).
(c) F R G if and only if F(0) + F(1) + F(2) = G(0) + G(1) + G(2). For this prob-
lem, two functions are related if the sum of their images, seen as an operation in
the natural numbers and not in the function space, are equal. - Find two functions F, G : R --* R where F 0 G but F 1[0,1) = G I [0,1).
- Let F : R --- JR with F(x) = x^2 .The following is a function from R to RR:
IdR 1[2,.) U Zero 1[0,2) U F I(, 0 )
Write an algorithm to compute this function.- Let A, B, and C be sets, and let F : A --* C be a function. If B C A, prove that