 7.7.1: Given a function f from a set X to a set Y, f (x) is _____.
 7.7.2: Given a function f from a set X to a set Y, iff (x) = y, then y is ...
 7.7.3: Given a function f from a set X to a set Y, the range of f (or the ...
 7.7.4: Given a function f from a set X to a set Y, iff (x) = y, then x is ...
 7.7.5: Given a function f from a set X to a set Y, ify Y, then f1(y) =____...
 7.7.6: Given functions f and g from a set X to a set Y, f = g if, and only...
 7.7.7: Given positive real numbers x and b with b =1, logb x =_____.
 7.7.8: Given a function f from a set X to a set Y and a subset A of X, f (...
 7.7.9: Given a function f from a set X to a set Y and a subset C of Y, f1(...
 7.7.10: Let X ={ 1,3,5} and Y ={ s,t,u,v}. Denef: X Yby the following arrow...
 7.7.11: Let X ={ 1,3,5} and Y ={ a,b,c,d}. Dene g: X Yby the following arro...
 7.7.12: Indicate whether the statements in parts (a)(d) are true or false. ...
 7.7.13: a. Find all functions from X ={ a,b}to Y ={ u,v}.b. Find all functi...
 7.7.14: Let IZ be the identity function dened on the set of all integers, a...
 7.7.15: Find functions dened on the set of nonnegative integers that dene t...
 7.7.16: Let A ={ 1,2,3,4,5}and dene a functionF :P(A)Z as follows: For all ...
 7.7.17: Let J5 ={ 0,1,2,3,4}, and dene a function F: J5J5as follows: For ea...
 7.7.18: Dene a function S: Z+ Z+ as follows: For each positive integer n, S...
 7.7.19: Let D be the set of all nite subsets of positive integers. Deneafun...
 7.7.20: Dene F: ZZZZ as follows: For all ordered pairs (a, b) of integers,F...
 7.7.21: Dene G: J5 J5 J5 J5 as follows: For all (a,b) J5 J5, G(a,b) = ((2a+...
 7.7.22: Let J5 ={ 0,1,2,3,4}, and dene functions f : J5J5and g: J5J5 as fol...
 7.7.23: Let J5 ={ 0,1,2,3,4}, and dene functions h: J5J5and k: J5J5 as foll...
 7.7.24: Let F and G be functions from the set of all real numbers to itself...
 7.7.25: Let F and G be functions from the set of all real numbers to itself...
 7.7.26: Use the denition of logarithm to ll in the blanks below. a. log2 8=...
 7.7.27: Find exact values for each of the following quantities. Do not use ...
 7.7.28: Usethedenitionoflogarithmtoprovethatforanypositive real number b wi...
 7.7.29: Usethedenitionoflogarithmtoprovethatforanypositive real number b wi...
 7.7.30: If b is any positive real number with b =1 andx is any real number,...
 7.7.31: Use the unique factorization for the integers theorem (Section 4.3)...
 7.7.32: If b and y are positive real numbers such that logb y =3, what is l...
 7.7.33: If b and y are positive real numbers such that logb y =2, what is l...
 7.7.34: Let A ={ 2,3,5} and B ={ x, y}. Letp1 and p2 be theprojections of A...
 7.7.35: Observe that mod and div can be dened as functions from Znonneg Z+ ...
 7.7.36: Student A tries to dene a function g:QZ by the rule gm n =mn,for al...
 7.7.37: Student C tries to dene a function h:QQ by the rule hm n = m2 n ,fo...
 7.7.38: Let J5 ={ 0,1,2,3,4}. ThenJ5 {0}={1,2,3,4}.R(x) is the number y so ...
 7.7.39: Let J4 ={ 0,1,2,3}. ThenJ4 {0}={ 1,2,3}. Student CS(x) is the numbe...
 7.7.40: Let X ={ a,b,c} and Y ={ r,s,t,u,v,w}. Denef :X Y asfollows: f (a) ...
 7.7.41: Let X ={ 1,2,3,4} and Y ={ a,b,c,d,e}. Deneg : X Y as follows: g(1)...
 7.7.42: Let X and Y be sets, let A and B be any subsets of X, and let F be ...
 7.7.43: Let X and Y be sets, let A and B be any subsets of X, and let C and...
 7.7.44: Let X and Y be sets, let A and B be any subsets of X, and let C and...
 7.7.45: Let X and Y be sets, let A and B be any subsets of X, and let C and...
 7.7.46: Let X and Y be sets, let A and B be any subsets of X, and let C and...
 7.7.47: Let X and Y be sets, let A and B be any subsets of X, and let C and...
 7.7.48: Let X and Y be sets, let A and B be any subsets of X, and let C and...
 7.7.49: Let X and Y be sets, let A and B be any subsets of X, and let C and...
 7.7.50: Let X and Y be sets, let A and B be any subsets of X, and let C and...
 7.7.51: Let X and Y be sets, let A and B be any subsets of X, and let C and...
 7.7.52: Given a set S and a subset A, thecharacteristic function of A, deno...
 7.7.53: Each of exercises refers to the Euler phi function, denoted , which...
 7.7.54: Each of exercises refers to the Euler phi function, denoted , which...
 7.7.55: Each of exercises refers to the Euler phi function, denoted , which...
 7.7.56: If F is a function from a set X to a set Y, thenF is onetoone if, ...
 7.7.57: If F is a function from a set X to a set Y, thenF is not onetoone...
 7.7.58: If F is a function from a set X to a set Y, thenF is onto if, and o...
 7.7.59: If F is a function from a set X to a set Y, thenF is not onto if, a...
 7.7.60: The following two statements are _____: u,vU, if H(u) = H(v) then u...
 7.7.61: Given a function F: X Y and an innite setX, to prove that F is one...
 7.7.62: Given a function F: X Y and an innite set X, to prove that F is ont...
 7.7.63: Given a function F: X Y, to prove that F is not onetoone, you _____.
 7.7.64: Given a function F: X Y, to prove that F is not onto, you _____.
 7.7.65: A onetoone correspondence from a set X to a set Y is a _____ that...
 7.7.66: If F is a onetoone correspondence from a set X to a set Y and y i...
 7.7.67: The denition of onetoone is stated in two ways: x1,x2 X,if F(x1) ...
 7.7.68: Fill in each blank with the word most or least. a. A function F is ...
 7.7.69: When asked to state the denition of onetoone, a student replies, ...
 7.7.70: Let f: X Y be a function. True or false? A sufcient condition for f...
 7.7.71: All but two of the following statements are correct ways to express...
 7.7.72: Let X ={ 1,5,9}and Y ={ 3,4,7}.a. Dene f: X Y by specifying that f ...
 7.7.73: Let X ={ a,b,c,d}and Y ={ e, f,g}. Dene functions Fand G by the arr...
 7.7.74: Let X ={ a,b,c}andY ={w,x, y,z}.Denefunctions Hand K by the arrow d...
 7.7.75: Let X ={ 1,2,3},Y ={ 1,2,3,4}, andZ ={ 1,2}. a. Dene a function f: ...
 7.7.76: a. Dene f:ZZ by the rule f (n) =2n, for all integers n. (i) Is f on...
 7.7.77: a. Dene g:ZZ by the rule g(n) =4n5, for all integers n. (i) Is g on...
 7.7.78: a. Dene F: ZZ by the rule F(n) =23n, for all integers n. (i) Is F o...
 7.7.79: a. Dene H:RR by the rule H(x) = x2, for all real numbers x. (i) Is ...
 7.7.80: Explain the mistake in the following proof. Theorem: The function f...
 7.7.81: In a function f is dened on a set of real numbers. Determine whethe...
 7.7.82: In a function f is dened on a set of real numbers. Determine whethe...
 7.7.83: In a function f is dened on a set of real numbers. Determine whethe...
 7.7.84: In a function f is dened on a set of real numbers. Determine whethe...
 7.7.85: Dene F:P({a,b,c}) Z as follows: For all A in P({a,b,c}), F(A) =the ...
 7.7.86: Dene S:Z+ Z+ by the rule: For all integers n, S(n) =the sum of the ...
 7.7.87: Let D bethesetofallnitesubsetsofpositiveintegers,and dene T:Z+ D by...
 7.7.88: Dene G:RRRR as follows: G(x, y) = (2y,x) for all (x, y) RR. a. Is G...
 7.7.89: Dene H:RRRR as follows: H(x, y) = (x +1,2y) for all (x, y) RR. a. I...
 7.7.90: Dene J: QQR by the rule J(r,s) =r +2s for all (r,s) QQ. a. Is J one...
 7.7.91: Dene F:Z+Z+ Z+ and G:Z+Z+ Z+ as follows: For all (n,m) Z+Z+, F(n,m)...
 7.7.92: a. Is log8 27=log2 3? Why or why not? b. Is log16 9=log4 3? Why or ...
 7.7.93: Prove that for all positive real numbers b,x, andy with b =1, logbx...
 7.7.94: Prove that for all positive real numbers b,x, andy with b =1, logb(...
 7.7.95: Prove that for all real numbers a,b, andx with b and x positive and...
 7.7.96: Use the following denition: If f:RR and g:RRarefunctions,thenthefun...
 7.7.97: Use the following denition: If f:RR and g:RRarefunctions,thenthefun...
 7.7.98: Use the following denition: If f:RR is a function and c is a nonzer...
 7.7.99: Use the following denition: If f:RR is a function and c is a nonzer...
 7.7.100: Suppose F: X Y is onetoone. a. Prove that for all subsets A X, F1...
 7.7.101: Suppose F:X Y is onto. Prove that for all subsets B Y, F(F1(B)) = B.
 7.7.102: Let X ={ a,b,c,d,e} and Y ={ s,t,u,v,w}. In a onetoone correspond...
 7.7.103: Let X ={ a,b,c,d,e} and Y ={ s,t,u,v,w}. In a onetoone correspond...
 7.7.104: Indicate which of the functions in the referenced exercise are one...
 7.7.105: Indicate which of the functions in the referenced exercise are one...
 7.7.106: Indicate which of the functions in the referenced exercise are one...
 7.7.107: Indicate which of the functions in the referenced exercise are one...
 7.7.108: Indicate which of the functions in the referenced exercise are one...
 7.7.109: Indicate which of the functions in the referenced exercise are one...
 7.7.110: Indicate which of the functions in the referenced exercise are one...
 7.7.111: Indicate which of the functions in the referenced exercise are one...
 7.7.112: Indicate which of the functions in the referenced exercise are one...
 7.7.113: Indicate which of the functions in the referenced exercise are one...
 7.7.114: Indicate which of the functions in the referenced exercise are one...
 7.7.115: Indicate which of the functions in the referenced exercise are one...
 7.7.116: If f is a function from X to Y, g is a function from Y to Z,andY Y,...
 7.7.117: If f is a function from X to Y and Ix and Iy are the identity funct...
 7.7.118: If f is a onetoone correspondence from X to Y, then f1f =_____ an...
 7.7.119: If f is a onetoone function from X to Y and g is a onetoone func...
 7.7.120: If f is a onetoone function from X to Y and g is a onetoone func...
 7.7.121: Functions f and g are dened by arrow diagrams. Find g f and f g and...
 7.7.122: Functions f and g are dened by arrow diagrams. Find g f and f g and...
 7.7.123: Functions F and G are dened by formulas. Find GF and FG and determi...
 7.7.124: Functions F and G are dened by formulas. Find GF and FG and determi...
 7.7.125: Dene f:RR by the rule f (x) = x for all real numbers x. Find ( f f ...
 7.7.126: Dene F:ZZ and G:ZZ by the rules F(a) =7a and G(a) =amod 5 for all i...
 7.7.127: Dene H:ZZ and K:ZZ by the rules H(a) =6a and K(a) =amod4 for all in...
 7.7.128: Dene L:ZZ and M:ZZ by the rules L(a) =a2 and M(a) =amod5 for all in...
 7.7.129: The functions of each pair are inverse to each other. For each pair...
 7.7.130: The functions of each pair are inverse to each other. For each pair...
 7.7.131: The functions of each pair are inverse to each other. For each pair...
 7.7.132: Explainhowitfollowsfromthedenitionoflogarithmthat a. logb(bx) = x, ...
 7.7.133: Prove Theorem 7.3.1(b): If f is any function from a set X toasetY,t...
 7.7.134: Prove Theorem 7.3.2(b): If f: X Y is a onetoone and onto function...
 7.7.135: Suppose Y and Z are sets and g:Y Z is a onetoone function. This m...
 7.7.136: If f: X Y and g:Y Z are functions and gf is onetoone, must g be o...
 7.7.137: If f: X Y and g:Y Z are functions and gf is onto, must f be onto? P...
 7.7.138: If f: X Y and g:Y Z are functions and gf is onetoone, must f be o...
 7.7.139: If f: X Y and g:Y Z are functions and gf is onto, must g be onto? P...
 7.7.140: Let f: W X,g: X Y, andh:Y Z be functions. Must h(gf ) = (hg)f? Prov...
 7.7.141: True or False? Given any set X and given any functions f: X X,g: X ...
 7.7.142: True or False? Given any set X and given any functions f: X X,g: X ...
 7.7.143: Find gf,(gf )1,g1, f1, andf1g1, and state how (gf )1 and f1g1 are r...
 7.7.144: Find gf,(gf )1,g1, f1, andf1g1, and state how (gf )1 and f1g1 are r...
 7.7.145: Prove or give a counterexample: If f: X Y and g:Y X are functions s...
 7.7.146: Suppose f: X Y and g:Y Z are both onetoone and onto. Prove that (...
 7.7.147: Let f: X Y and g: Y Z. Is the following property true or false? For...
 7.7.148: A set is nite if, and only if, _____.
 7.7.149: To prove that a set A has the same cardinality as a set B you must ...
 7.7.150: The reexive property of cardinality says that given any set A, _____.
 7.7.151: The symmetric property of cardinality says that given any sets A an...
 7.7.152: Thetransitivepropertyofcardinalitysaysthatgivenanysets A, B, andC, ...
 7.7.153: A set is called countably innite if, and only if, _____.
 7.7.154: A set is called countable if, and only if, _____.
 7.7.155: In each of the following, ll in the blank with the word countable o...
 7.7.156: The Cantor diagonalization process is used to prove that _____.
 7.7.157: When asked what it means to say that set A has the same cardinality...
 7.7.158: Show that there are as many squares as there are numbers by exhibit...
 7.7.159: Let 3Z={ n Zn =3k,for some integer k}. Prove thatZ and 3Z have the...
 7.7.160: Let O be the set of all odd integers. Prove that O has the same car...
 7.7.161: Let 25Z be the set of all integers that are multiples of 25. Prove ...
 7.7.162: Checkthattheformulafor F given at the end of Example 7.4.2 produces...
 7.7.163: Usethefunctionsi and j denedintheparagraphfollowing Example7.4.2tos...
 7.7.164: Use the result of exercise 3 to prove that 3Z is countable.
 7.7.165: Show that the set of all nonnegative integers is countable byexhibi...
 7.7.166: S denotes the set of real numbers strictly between 0 and 1. That is...
 7.7.167: S denotes the set of real numbers strictly between 0 and 1. That is...
 7.7.168: S denotes the set of real numbers strictly between 0 and 1. That is...
 7.7.169: S denotes the set of real numbers strictly between 0 and 1. That is...
 7.7.170: S denotes the set of real numbers strictly between 0 and 1. That is...
 7.7.171: Show that the set of all bit strings (strings of 0s and 1s) is coun...
 7.7.172: Show that Q, the set of all rational numbers, is countable.
 7.7.173: Show that the set Q of all rational numbers is dense along the numb...
 7.7.174: Must the average of two irrational numbers always be irrational? Pr...
 7.7.175: Showthatthesetofallirrationalnumbersisdensealongthe number line by ...
 7.7.176: Give two examples of functions from Z to Z that are onetoone but n...
 7.7.177: Give two examples of functions from Z to Z that are onto but not on...
 7.7.178: Dene a function g:Z+Z+ Z+ by the formula g(m,n) =2m3n for all (m,n)...
 7.7.179: a. Explain how to use the following diagram to show that Znonneg Zn...
 7.7.180: Prove that the function H dened analytically in exercise 23b is a o...
 7.7.181: Prove that 0.1999...=0.2.
 7.7.182: Prove that any innite set contains a countably innite subset.
 7.7.183: If A is any countably innite set, B is any set, and g: A B is onto,...
 7.7.184: Prove that a disjoint union of any nite set and any countably innit...
 7.7.185: Prove that a union of any two countably innite sets is countably in...
 7.7.186: Use the result of exercise 29 to prove that the set of all irration...
 7.7.187: Use the results of exercises 28 and 29 to prove that a union of any...
 7.7.188: Prove that ZZ, the Cartesian product of the set of integers with it...
 7.7.189: Use the results of exercises 27, 31, and 32 to prove the following:...
 7.7.190: Let P(S) be the set of all subsets of set S, and let T be the set o...
 7.7.191: Let S be a set and let P(S) be the set of all subsets of S. Show th...
 7.7.192: The SchroederBernstein theorem states the following: If A and B are...
 7.7.193: Prove that if A and B are any countably innite sets, then A B is co...
 7.7.194: Suppose A1, A2, A3,...isaninnitesequenceofcountable sets. Recall th...
Solutions for Chapter 7: Functions
Full solutions for Discrete Mathematics: Introduction to Mathematical Reasoning  1st Edition
ISBN: 9780495826170
Solutions for Chapter 7: Functions
Get Full SolutionsDiscrete Mathematics: Introduction to Mathematical Reasoning was written by and is associated to the ISBN: 9780495826170. This textbook survival guide was created for the textbook: Discrete Mathematics: Introduction to Mathematical Reasoning, edition: 1. Since 194 problems in chapter 7: Functions have been answered, more than 16551 students have viewed full stepbystep solutions from this chapter. Chapter 7: Functions includes 194 full stepbystep solutions. This expansive textbook survival guide covers the following chapters and their solutions.

Covariance matrix:E.
When random variables Xi have mean = average value = 0, their covariances "'£ ij are the averages of XiX j. With means Xi, the matrix :E = mean of (x  x) (x  x) T is positive (semi)definite; :E is diagonal if the Xi are independent.

Dimension of vector space
dim(V) = number of vectors in any basis for V.

Exponential eAt = I + At + (At)2 12! + ...
has derivative AeAt; eAt u(O) solves u' = Au.

Fast Fourier Transform (FFT).
A factorization of the Fourier matrix Fn into e = log2 n matrices Si times a permutation. Each Si needs only nl2 multiplications, so Fnx and Fn1c can be computed with ne/2 multiplications. Revolutionary.

GaussJordan method.
Invert A by row operations on [A I] to reach [I AI].

Hankel matrix H.
Constant along each antidiagonal; hij depends on i + j.

Independent vectors VI, .. " vk.
No combination cl VI + ... + qVk = zero vector unless all ci = O. If the v's are the columns of A, the only solution to Ax = 0 is x = o.

Inverse matrix AI.
Square matrix with AI A = I and AAl = I. No inverse if det A = 0 and rank(A) < n and Ax = 0 for a nonzero vector x. The inverses of AB and AT are B1 AI and (AI)T. Cofactor formula (Al)ij = Cji! detA.

Multiplication Ax
= Xl (column 1) + ... + xn(column n) = combination of columns.

Orthonormal vectors q 1 , ... , q n·
Dot products are q T q j = 0 if i =1= j and q T q i = 1. The matrix Q with these orthonormal columns has Q T Q = I. If m = n then Q T = Q 1 and q 1 ' ... , q n is an orthonormal basis for Rn : every v = L (v T q j )q j •

Outer product uv T
= column times row = rank one matrix.

Positive definite matrix A.
Symmetric matrix with positive eigenvalues and positive pivots. Definition: x T Ax > 0 unless x = O. Then A = LDLT with diag(D» O.

Projection matrix P onto subspace S.
Projection p = P b is the closest point to b in S, error e = b  Pb is perpendicularto S. p 2 = P = pT, eigenvalues are 1 or 0, eigenvectors are in S or S...L. If columns of A = basis for S then P = A (AT A) 1 AT.

Projection p = a(aTblaTa) onto the line through a.
P = aaT laTa has rank l.

Semidefinite matrix A.
(Positive) semidefinite: all x T Ax > 0, all A > 0; A = any RT R.

Skewsymmetric matrix K.
The transpose is K, since Kij = Kji. Eigenvalues are pure imaginary, eigenvectors are orthogonal, eKt is an orthogonal matrix.

Spectral Theorem A = QAQT.
Real symmetric A has real A'S and orthonormal q's.

Triangle inequality II u + v II < II u II + II v II.
For matrix norms II A + B II < II A II + II B II·

Vandermonde matrix V.
V c = b gives coefficients of p(x) = Co + ... + Cn_IXn 1 with P(Xi) = bi. Vij = (Xi)jI and det V = product of (Xk  Xi) for k > i.

Vector v in Rn.
Sequence of n real numbers v = (VI, ... , Vn) = point in Rn.