Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 3] FUNCTIONS AND ALGORITHMS 67

ONE-TO-ONE, ONTO, AND INVERTIBLE FUNCTIONS

3.30. Determine if each function is one-to-one.

(a) To each person on the earth assign the number which corresponds to his age.

(b) To each country in the world assign the latitude and longitude of its capital.

(c) To each book written by only one author assign the author.

(d) To each country in the world which has a prime minister assign its prime minister.

3.31. Let functionsf,g,hfromV={ 1 , 2 , 3 , 4 }intoVbe defined by:f (n)= 6 −n,g(n)=3,

h={( 1 , 2 ), ( 2 , 3 ), ( 3 , 4 ), ( 4 , 1 )}. Decide which functions are:

(a) one-to-one; (b) onto; (c) both; (d) neither.

3.32. Let functionsf,g,hfromNintoNbe defined byf (n)=n+2, (b)g(n)= 2 n;

h(n)=number of positive divisors ofn. Decide which functions are:

(a) one-to-one; (b) onto; (c) both; (d) neither; (e) Findh′( 2 )={x|h(x)= 2 }.

3.33. Decide which of the following functions are: (a) one-to-one; (b) onto; (c) both; (d) neither.

(1)f:Z^2 →Zwheref (n, m)=n−m; (3)h:Z×(Z\ 0 )→Qwhereh(n, m)=n/m;

(2)g:Z^2 →Z^2 whereg(n, m)=(m, n); (4)k:Z→Z^2 wherek(n)=(n, n).

3.34. Letf:R→Rbe defined byf(x)= 3 x−7. Find a formula for the inverse functionf−^1 :R→R.

3.35. Consider permutationsσ=

(

123456

256134

)

andτ=

(

123456

643125

)

inS 6.

Find: (a)τ◦σ; (b)σ◦τ; (c)σ^2 ; (d)σ−^1 ; (e)τ−^1

PROPERTIES OF FUNCTIONS

3.36. Prove: Supposef:A→Bandg:B→Asatisfyg◦f= (^1) A. Thenfis one-to-one andgis onto.
3.37. Prove Theorem 3.1: A functionf:A→Bis invertible if and only iffis both one-to-one and onto.
3.38. Prove: Supposef:A→Bis invertible with inverse functionf−^1 :B→A. Thenf−^1 ◦f= (^1) Aandf◦f−^1 = (^1) B.
3.39. Supposef:A→Bis one-to-one andg:A→Bis onto. Letxbe a subset ofA.
(a) Showf (^1) x, the restriction offtox, is one-to-one.
(b) Showg (^1) x, need not be onto.
3.40. For eachn∈N, consider the open intervalAn=( 0 , 1 /n)={x| 0 <x< 1 /n}. Find:
(a) A 2 ∪A 8 ; (c)∪(Ai|i∈J); (e)∪(Ai|i∈K);
(b) A 3 ∩A 7 ; (d)∩(Ai|i∈J); (f)∩(Ai|i∈K).
whereJis a finite subset ofNandKis an infinite subset ofN.
3.41. For eachn∈N, letDn={n, 2 n, 3 n,...}={multiples ofn}.
(a) Find: (i)D 2 ∩D 7 ; (ii)D 6 ∩D 8 ; (iii)D 3 ∩D 12 ; (iv)D 3 ∪D 12.
(b) Prove that∩(Di|i∈K)=Ø whereKis an infinite subset ofN.
3.42. Consider an indexed class of sets{Ai|i∈I}, a setBand an indexi 0 in I.
Prove: (a)B∩(∪iAi)=∪i(B∩Ai);(b)∩(Ai|i∈I)⊆Ai 0 ⊆∪(Ai|i∈I).