Ch.7: Functions

Chapter 7 of the book "Discrete Mathematics with Applications" by Susanna S. Epp (4th edition) 7.1. Functions Defined on General Sets 7.2. One-to-One and Onto, Inverse Functions 7.3. Composition of Functions 7.4. Cardinality with Applications to Computability

136 flashcards · Mathematics · by lakesare

Part of Textbooks › Discrete Mathematics with Applications (Susanna Epp) · 12 courses

1. [Functions Defined on General Sets] What is a function fff from a set XXX to a set YYY , written f:X→Yf: X \to Yf:X→Y ?

   A relation from XXX to YYY in which every element of XXX is related to exactly one element of YYY . Two properties: (1) every x∈Xx \in Xx∈X is related to some y∈Yy \in Yy∈Y ; (2) no x∈Xx \in Xx∈X is related to more than one element of YYY .Example: {(a,2),(b,4),(c,2)}\{(a, 2), (b, 4), (c, 2)\}{(a,2),(b,4),(c,2)} is a function from {a,b,c}\{a, b, c\}{a,b,c} to {1,2,3,4}\{1, 2, 3, 4\}{1,2,3,4} .

2. [Functions Defined on General Sets] For a function f:X→Yf: X \to Yf:X→Y , the set XXX is the domain of fff and the set YYY is the co-domain of fff .

   Example: f:{a,b,c}→{1,2,3,4}f: \{a, b, c\} \to \{1, 2, 3, 4\}f:{a,b,c}→{1,2,3,4} has domain {a,b,c}\{a, b, c\}{a,b,c} and co-domain {1,2,3,4}\{1, 2, 3, 4\}{1,2,3,4} .

3. [Functions Defined on General Sets] f:X→Yf: X \to Yf:X→Y is a function and x∈Xx \in Xx∈X . What four phrases name f(x)f(x)f(x) ?

   fff of xxx , the output of fff for the input xxx , the value of fff at xxx , the image of xxx under fff . f(x)f(x)f(x) is the unique element of YYY that is related to xxx by fff . One also writes xundefinedfyx \xrightarrow{f} yxf​y or f:x→yf: x \to yf:x→y and says " fff sends (maps) xxx to yyy ".

4. [Functions Defined on General Sets] f:X→Yf: X \to Yf:X→Y is a function. What is the range of fff (also called the image of XXX under fff )?

   {y∈Y∣y=f(x) for some x∈X}\boldsymbol{\{y \in Y \mid y = f(x) \text{ for some } x \in X\}}{y∈Y∣y=f(x) for some x∈X} The set of all values of fff . It can be smaller than the co-domain.Example: f:{a,b,c}→{1,2,3,4}f: \{a, b, c\} \to \{1, 2, 3, 4\}f:{a,b,c}→{1,2,3,4} with f(a)=2f(a) = 2f(a)=2 , f(b)=4f(b) = 4f(b)=4 , f(c)=2f(c) = 2f(c)=2 has range {2,4}\{2, 4\}{2,4} .

5. [Functions Defined on General Sets] f:X→Yf: X \to Yf:X→Y is a function and y∈Yy \in Yy∈Y . What is an inverse image (or preimage) of yyy , and what is the inverse image of yyy ?

   An inverse image of yyy : an x∈Xx \in Xx∈X with f(x)=yf(x) = yf(x)=y . The inverse image of yyy : the set {x∈X∣f(x)=y}\{x \in X \mid f(x) = y\}{x∈X∣f(x)=y} . The inverse image of yyy can have several elements or be empty.Example: for f(a)=2f(a) = 2f(a)=2 , f(b)=4f(b) = 4f(b)=4 , f(c)=2f(c) = 2f(c)=2 on {a,b,c}\{a, b, c\}{a,b,c} , the inverse image of 2 is {a,c}\{a, c\}{a,c} and the inverse image of 1 is ∅\emptyset∅ .

6. [Functions Defined on General Sets] Should the notation f(x)f(x)f(x) be used for the function fff itself?

   Generally no: f(x)f(x)f(x) means the value of fff at xxx . Some texts use f(x)f(x)f(x) for both the value and the function; this leads to confusion.

7. [Functions Defined on General Sets] Who first formulated a definition of function close to the modern one (for sets of numbers), and when?

   Lejeune Dirichlet, 1837. German mathematician (1805 to 1859); the name is pronounced DEER-ish-lay.

8. [Functions Defined on General Sets] XXX and YYY are finite sets. When does an arrow diagram from XXX to YYY define a function?

   Every element of XXX has exactly one arrow coming out of it. That is: (1) every element of XXX has an arrow coming out of it, and (2) no element of XXX has two arrows coming out of it that point to two different elements of YYY .

9. [Functions Defined on General Sets] Which of these arrow diagrams define functions from X={a,b,c}X = \{a, b, c\}X={a,b,c} to Y={1,2,3,4}Y = \{1, 2, 3, 4\}Y={1,2,3,4} ?

   Only (c). In (a), bbb has no arrow coming out of it. In (b), ccc has two arrows coming out of it, pointing to 2 and to 3.

10. [Functions Defined on General Sets] In the arrow diagram of a function f:X→Yf: X \to Yf:X→Y , can an element of YYY have no arrow pointing to it? Can it have two arrows pointing to it?

    Yes to both. The conditions for a function only restrict arrows coming out of elements of XXX . Nothing points to 1 or 3; two arrows point to 2.

11. [Functions Defined on General Sets] The function f:{a,b,c}→{1,2,3,4}f: \{a, b, c\} \to \{1, 2, 3, 4\}f:{a,b,c}→{1,2,3,4} is given by this arrow diagram. Find f(a),f(b),f(c)f(a), f(b), f(c)f(a),f(b),f(c) , the range of fff , and fff as a set of ordered pairs.

    f(a)=2f(a) = 2f(a)=2 , f(b)=4f(b) = 4f(b)=4 , f(c)=2f(c) = 2f(c)=2 ; range {2,4}\{2, 4\}{2,4} ; f={(a,2),(b,4),(c,2)}f = \{(a, 2), (b, 4), (c, 2)\}f={(a,2),(b,4),(c,2)} .

12. [Functions Defined on General Sets] The function f:{a,b,c}→{1,2,3,4}f: \{a, b, c\} \to \{1, 2, 3, 4\}f:{a,b,c}→{1,2,3,4} is given by this arrow diagram. Find the inverse images of 2, of 4 and of 1.

    Inverse image of 2 ={a,c}= \{a, c\}={a,c} , of 4 ={b}= \{b\}={b} , of 1 =∅= \emptyset=∅ . No arrow points to 1.

13. [Functions Defined on General Sets] A test for function equality F:X→YF: X \to YF:X→Y and G:X→YG: X \to YG:X→Y are functions. F=GF = GF=G if, and only if, … ?

    F(x)=G(x)F(x) = G(x)F(x)=G(x) for all x∈Xx \in Xx∈X . Example: f(x)=x2f(x) = x^2f(x)=x2 and g(x)=∣x∣g(x) = |x|g(x)=∣x∣ from {−1,0,1}\{-1, 0, 1\}{−1,0,1} to Z\mathbf{Z}Z are equal: both give 1,0,11, 0, 11,0,1 .

14. [Functions Defined on General Sets] For functions F,G:X→YF, G: X \to YF,G:X→Y : F=GF = GF=G if, and only if, F(x)=G(x)F(x) = G(x)F(x)=G(x) for all x∈Xx \in Xx∈X .Why does F(x)=G(x)F(x) = G(x)F(x)=G(x) for all xxx give F=GF = GF=G ?

    A function is a set of ordered pairs, and (x,y)∈F⇔y=F(x)=G(x)⇔(x,y)∈G(x, y) \in F \Leftrightarrow y = F(x) = G(x) \Leftrightarrow (x, y) \in G(x,y)∈F⇔y=F(x)=G(x)⇔(x,y)∈G . So FFF and GGG have exactly the same elements as subsets of X×YX \times YX×Y .

15. [Functions Defined on General Sets] J3={0,1,2}J_3 = \{0, 1, 2\}J3​={0,1,2} , and f,g:J3→J3f, g: J_3 \to J_3f,g:J3​→J3​ are defined by f(x)=(x2+x+1) mod 3f(x) = (x^2 + x + 1) \bmod 3f(x)=(x2+x+1)mod3 and g(x)=(x+2)2 mod 3g(x) = (x + 2)^2 \bmod 3g(x)=(x+2)2mod3 . Is f=gf = gf=g ?

    Yes. xx2+x+1(x+2)20141392716\begin{array}{c|c|c} x & x^2 + x + 1 & (x + 2)^2 \\ \hline 0 & 1 & 4 \\ 1 & 3 & 9 \\ 2 & 7 & 16 \end{array}x012​x2+x+1137​(x+2)24916​​ Mod 3, both columns give 1,0,11, 0, 11,0,1 , so f(x)=g(x)f(x) = g(x)f(x)=g(x) for all x∈J3x \in J_3x∈J3​ .

16. [Functions Defined on General Sets] F,G:R→RF, G: \mathbf{R} \to \mathbf{R}F,G:R→R are functions, and (F+G)(x)=F(x)+G(x)(F + G)(x) = F(x) + G(x)(F+G)(x)=F(x)+G(x) , (G+F)(x)=G(x)+F(x)(G + F)(x) = G(x) + F(x)(G+F)(x)=G(x)+F(x) for all x∈Rx \in \mathbf{R}x∈R . Is F+G=G+FF + G = G + FF+G=G+F ?

    Yes. (F+G)(x)=F(x)+G(x)=G(x)+F(x)=(G+F)(x)(F + G)(x) = F(x) + G(x) = G(x) + F(x) = (G + F)(x)(F+G)(x)=F(x)+G(x)=G(x)+F(x)=(G+F)(x) for every xxx , by the commutative law for addition of real numbers.

17. [Functions Defined on General Sets] What is the identity function IXI_XIX​ on a set XXX ?

    The function IX:X→XI_X: X \to XIX​:X→X with IX(x)=xI_X(x) = xIX​(x)=x for all x∈Xx \in Xx∈X . Example: if φ(z)\varphi(z)φ(z) is an element of XXX , then IX(φ(z))=φ(z)I_X(\varphi(z)) = \varphi(z)IX​(φ(z))=φ(z) .

18. [Functions Defined on General Sets] How is an infinite sequence defined formally as a function?

    As a function defined on the set of integers greater than or equal to some fixed integer. Example: 1,−12,13,−14,…1, -\frac{1}{2}, \frac{1}{3}, -\frac{1}{4}, \dots1,−21​,31​,−41​,… is f:Znonneg→Rf: \mathbf{Z}^{\text{nonneg}} \to \mathbf{R}f:Znonneg→R with f(n)=(−1)nn+1f(n) = \frac{(-1)^n}{n + 1}f(n)=n+1(−1)n​ .

19. [Functions Defined on General Sets] The sequence 1,−12,13,−14,15,…1, -\frac{1}{2}, \frac{1}{3}, -\frac{1}{4}, \frac{1}{5}, \dots1,−21​,31​,−41​,51​,… is the function f(n)=(−1)nn+1f(n) = \frac{(-1)^n}{n + 1}f(n)=n+1(−1)n​ on the nonnegative integers. Write it as a function ggg on the positive integers Z+\mathbf{Z}^+Z+ .

    g(n)=(−1)n+1n\boldsymbol{g(n) = \frac{(-1)^{n+1}}{n}}g(n)=n(−1)n+1​ g(1)=1g(1) = 1g(1)=1 , g(2)=−12g(2) = -\frac{1}{2}g(2)=−21​ , and g(n+1)=(−1)n+2n+1=f(n)g(n + 1) = \frac{(-1)^{n+2}}{n + 1} = f(n)g(n+1)=n+1(−1)n+2​=f(n) . Many functions define the same sequence.

20. [Functions Defined on General Sets] F:P({a,b,c})→ZnonnegF: \mathcal{P}(\{a, b, c\}) \to \mathbf{Z}^{\text{nonneg}}F:P({a,b,c})→Znonneg sends each subset XXX of {a,b,c}\{a, b, c\}{a,b,c} to the number of elements of XXX . What is the range of FFF ?

    {0,1,2,3}\boldsymbol{\{0, 1, 2, 3\}}{0,1,2,3} P(A)\mathcal{P}(A)P(A) is the power set (set of all subsets) of AAA .

21. [Functions Defined on General Sets] R:R×R→R×RR: \mathbf{R} \times \mathbf{R} \to \mathbf{R} \times \mathbf{R}R:R×R→R×R is defined by R(a,b)=(−a,b)R(a, b) = (-a, b)R(a,b)=(−a,b) . What does RRR do to a point of the plane, and what is R(−2,5)R(-2, 5)R(−2,5) ?

    RRR sends each point to its mirror image across the vertical axis; R(−2,5)=(2,5)R(-2, 5) = (2, 5)R(−2,5)=(2,5) . For functions on a Cartesian product, one writes R(a,b)R(a, b)R(a,b) instead of R((a,b))R((a, b))R((a,b)) .Example: M(a,b)=abM(a, b) = abM(a,b)=ab is the multiplication function; M(2,2)=2M(\sqrt{2}, \sqrt{2}) = 2M(2​,2​)=2 .

22. [Functions Defined on General Sets] bbb is a positive real number with b≠1b \neq 1b=1 , and x>0x > 0x>0 . What is the logarithm with base bbb of xxx , log⁡bx\log_b xlogb​x ?

    The exponent to which bbb must be raised to obtain xxx : log⁡bx=y⇔by=x\log_b x = y \Leftrightarrow b^y = xlogb​x=y⇔by=x . The logarithmic function with base bbb is the function from R+\mathbf{R}^+R+ to R\mathbf{R}R that takes each xxx to log⁡bx\log_b xlogb​x .Example: log⁡39=2\log_3 9 = 2log3​9=2 because 32=93^2 = 932=9 .

23. [Functions Defined on General Sets] Compute: log⁡212\log_2 \frac{1}{2}log2​21​ , log⁡101\ \log_{10} 1 log10​1 , log⁡2(2m)\ \log_2(2^m) log2​(2m) for real mmm , 2log⁡2m\ 2^{\log_2 m} 2log2​m for m>0m > 0m>0 .

    −1, 0, m, m\boldsymbol{-1, \ 0, \ m, \ m}−1, 0, m, m 2−1=122^{-1} = \frac{1}{2}2−1=21​ ; 100=110^0 = 1100=1 ; the exponent to which 2 must be raised to obtain 2m2^m2m is mmm ; log⁡2m\log_2 mlog2​m is the exponent that turns 2 into mmm .

24. [Functions Defined on General Sets] A message of bits is encoded by writing each bit three times. What is the encoding of 001011110010111100101111 , and how is a received string decoded?

    000000111000111111111111000000111000111111111111000000111000111111111111 ; decode by replacing each block of three identical bits by one copy of that bit. The encoding function EEE goes from the set AAA of all bit strings to the set TTT of bit strings made of consecutive triples of identical bits; the decoding function DDD goes from TTT to AAA .

25. [Functions Defined on General Sets] Bits are encoded by writing each bit three times. A received block of three bits is not all equal, e.g. 101101101 . What does the receiver do?

    Changes the one differing bit to agree with the other two, then decodes ( 101→111→1101 \to 111 \to 1101→111→1 ). If errors are rare, the single differing bit is likely the one in error.

26. [Functions Defined on General Sets] SnS_nSn​ is the set of bit strings of length nnn . What is the Hamming distance H(s,t)H(s, t)H(s,t) of s,t∈Sns, t \in S_ns,t∈Sn​ ?

    The number of positions in which sss and ttt have different values. H:Sn×Sn→ZnonnegH: S_n \times S_n \to \mathbf{Z}^{\text{nonneg}}H:Sn​×Sn​→Znonneg , named after the computer scientist Richard W. Hamming; important in coding theory.Example: H(11000,00000)=2H(11000, 00000) = 2H(11000,00000)=2 .

27. [Functions Defined on General Sets] Find the Hamming distances H(00101,01110)H(00101, 01110)H(00101,01110) and H(10001,01111)H(10001, 01111)H(10001,01111) .

    3\boldsymbol{3}3 and 4\boldsymbol{4}4 001010010100101 vs 011100111001110 differ in positions 2, 4, 5. 100011000110001 vs 011110111101111 differ in positions 1, 2, 3, 4.

28. [Functions Defined on General Sets] What is an nnn -place Boolean function?

    A function f:{0,1}n→{0,1}f: \{0, 1\}^n \to \{0, 1\}f:{0,1}n→{0,1} . {0,1}n\{0, 1\}^n{0,1}n is the set of ordered nnn -tuples of 0's and 1's. The input/output table of a digital logic circuit with nnn input wires defines such a function: each input row is sent to the output in the same row.Example: f(x1,x2)=x1x2f(x_1, x_2) = x_1 x_2f(x1​,x2​)=x1​x2​ (the AND gate) is a 2-place Boolean function.

29. [Functions Defined on General Sets] The Boolean function f:{0,1}3→{0,1}f: \{0, 1\}^3 \to \{0, 1\}f:{0,1}3→{0,1} is f(x1,x2,x3)=(x1+x2+x3) mod 2f(x_1, x_2, x_3) = (x_1 + x_2 + x_3) \bmod 2f(x1​,x2​,x3​)=(x1​+x2​+x3​)mod2 . Find f(1,1,1)f(1, 1, 1)f(1,1,1) and f(1,1,0)f(1, 1, 0)f(1,1,0) . When is f(x1,x2,x3)=1f(x_1, x_2, x_3) = 1f(x1​,x2​,x3​)=1 ?

    f(1,1,1)=1f(1, 1, 1) = 1f(1,1,1)=1 , f(1,1,0)=0f(1, 1, 0) = 0f(1,1,0)=0 ; f=1f = 1f=1 exactly when an odd number of inputs are 1. (1+1+1) mod 2=3 mod 2=1(1 + 1 + 1) \bmod 2 = 3 \bmod 2 = 1(1+1+1)mod2=3mod2=1 and (1+1+0) mod 2=0(1 + 1 + 0) \bmod 2 = 0(1+1+0)mod2=0 .

30. [Functions Defined on General Sets] When is a "function" said to be not well defined?

    When it fails to satisfy at least one of the requirements for being a function. So "well-defined function" is redundant: a well-defined function is simply a function.

31. [Functions Defined on General Sets] Why does " f:R→Rf: \mathbf{R} \to \mathbf{R}f:R→R , f(x)f(x)f(x) is the real number yyy with x2+y2=1x^2 + y^2 = 1x2+y2=1 " not define a function?

    For some xxx no such yyy exists, and for others there are two. x=2x = 2x=2 : no real yyy has 4+y2=14 + y^2 = 14+y2=1 . x=0x = 0x=0 : both y=1y = 1y=1 and y=−1y = -1y=−1 work.

32. [Functions Defined on General Sets] Is f:Q→Zf: \mathbf{Q} \to \mathbf{Z}f:Q→Z given by f(mn)=mf\left(\frac{m}{n}\right) = mf(nm​)=m (for integers m,nm, nm,n with n≠0n \neq 0n=0 ) well defined?

    No: one rational number has several representations mn\frac{m}{n}nm​ that give different values. 12=36\frac{1}{2} = \frac{3}{6}21​=63​ , but the formula gives f(12)=1f\left(\frac{1}{2}\right) = 1f(21​)=1 and f(36)=3f\left(\frac{3}{6}\right) = 3f(63​)=3 .

33. [Functions Defined on General Sets] f:X→Yf: X \to Yf:X→Y is a function and A⊆XA \subseteq XA⊆X . What is the image of AAA , f(A)f(A)f(A) ?

    f(A)={y∈Y∣y=f(x) for some x∈A}\boldsymbol{f(A) = \{y \in Y \mid y = f(x) \text{ for some } x \in A\}}f(A)={y∈Y∣y=f(x) for some x∈A} Equivalently {f(x)∣x∈A}\{f(x) \mid x \in A\}{f(x)∣x∈A} .Example: for f(x)=x2f(x) = x^2f(x)=x2 on Z\mathbf{Z}Z , f({−1,1,2})={1,4}f(\{-1, 1, 2\}) = \{1, 4\}f({−1,1,2})={1,4} .

34. [Functions Defined on General Sets] f:X→Yf: X \to Yf:X→Y is a function and C⊆YC \subseteq YC⊆Y . What is the inverse image of CCC , f−1(C)f^{-1}(C)f−1(C) ?

    f−1(C)={x∈X∣f(x)∈C}\boldsymbol{f^{-1}(C) = \{x \in X \mid f(x) \in C\}}f−1(C)={x∈X∣f(x)∈C} For y∈Yy \in Yy∈Y , f−1(y)f^{-1}(y)f−1(y) means f−1({y})f^{-1}(\{y\})f−1({y}) . The notation f−1(C)f^{-1}(C)f−1(C) makes sense for every function fff , not only for those that have an inverse function.Example: for f(x)=x2f(x) = x^2f(x)=x2 on Z\mathbf{Z}Z , f−1({4,5})={−2,2}f^{-1}(\{4, 5\}) = \{-2, 2\}f−1({4,5})={−2,2} .

35. [Functions Defined on General Sets] F:{1,2,3,4}→{a,b,c,d,e}F: \{1, 2, 3, 4\} \to \{a, b, c, d, e\}F:{1,2,3,4}→{a,b,c,d,e} is given by this arrow diagram. With A={1,4}A = \{1, 4\}A={1,4} , C={a,b}C = \{a, b\}C={a,b} , D={c,e}D = \{c, e\}D={c,e} , find F(A)F(A)F(A) , F(X)F(X)F(X) , F−1(C)F^{-1}(C)F−1(C) , F−1(D)F^{-1}(D)F−1(D) .

    F(A)={b}F(A) = \{b\}F(A)={b} , F(X)={a,b,d}F(X) = \{a, b, d\}F(X)={a,b,d} , F−1(C)={1,2,4}F^{-1}(C) = \{1, 2, 4\}F−1(C)={1,2,4} , F−1(D)=∅F^{-1}(D) = \emptysetF−1(D)=∅ . F(1)=bF(1) = bF(1)=b , F(2)=aF(2) = aF(2)=a , F(3)=dF(3) = dF(3)=d , F(4)=bF(4) = bF(4)=b ; no arrow points to ccc or eee .

36. [Functions Defined on General Sets] F:X→YF: X \to YF:X→Y is a function and A,B⊆XA, B \subseteq XA,B⊆X . How are F(A∪B)F(A \cup B)F(A∪B) and F(A)∪F(B)F(A) \cup F(B)F(A)∪F(B) related?

    F(A∪B)=F(A)∪F(B)\boldsymbol{F(A \cup B) = F(A) \cup F(B)}F(A∪B)=F(A)∪F(B) Example: F(x)=x2F(x) = x^2F(x)=x2 , A={−1}A = \{-1\}A={−1} , B={1,2}B = \{1, 2\}B={1,2} : F(A∪B)={1,4}={1}∪{1,4}F(A \cup B) = \{1, 4\} = \{1\} \cup \{1, 4\}F(A∪B)={1,4}={1}∪{1,4} .

37. [Functions Defined on General Sets] F:X→YF: X \to YF:X→Y is a function and A,B⊆XA, B \subseteq XA,B⊆X . How does the proof of F(A∪B)⊆F(A)∪F(B)F(A \cup B) \subseteq F(A) \cup F(B)F(A∪B)⊆F(A)∪F(B) go?

    Take y∈F(A∪B)y \in F(A \cup B)y∈F(A∪B) , so y=F(x)y = F(x)y=F(x) for some x∈A∪Bx \in A \cup Bx∈A∪B ; in the case x∈Ax \in Ax∈A , y∈F(A)y \in F(A)y∈F(A) , and in the case x∈Bx \in Bx∈B , y∈F(B)y \in F(B)y∈F(B) . In either case y∈F(A)∪F(B)y \in F(A) \cup F(B)y∈F(A)∪F(B) .

38. [One-to-One and Onto, Inverse Functions] F:X→YF: X \to YF:X→Y is a function. When is FFF one-to-one (injective)?

    For all x1,x2∈Xx_1, x_2 \in Xx1​,x2​∈X : if F(x1)=F(x2)F(x_1) = F(x_2)F(x1​)=F(x2​) , then x1=x2x_1 = x_2x1​=x2​ . Equivalently: if x1≠x2x_1 \neq x_2x1​=x2​ , then F(x1)≠F(x2)F(x_1) \neq F(x_2)F(x1​)=F(x2​) . Any two distinct elements of XXX are sent to two distinct elements of YYY . Example: F(x)=x+1F(x) = x + 1F(x)=x+1 on Z\mathbf{Z}Z is one-to-one.

39. [One-to-One and Onto, Inverse Functions] F:X→YF: X \to YF:X→Y is a function. Write the negation: FFF is not one-to-one if, and only if, … ?

    There exist x1,x2∈Xx_1, x_2 \in Xx1​,x2​∈X with F(x1)=F(x2)F(x_1) = F(x_2)F(x1​)=F(x2​) and x1≠x2x_1 \neq x_2x1​=x2​ . Example: F(x)=x2F(x) = x^2F(x)=x2 on Z\mathbf{Z}Z : F(2)=F(−2)F(2) = F(-2)F(2)=F(−2) but 2≠−22 \neq -22=−2 .

40. [One-to-One and Onto, Inverse Functions] H:U→VH: U \to VH:U→V is a function. Why do these two statements say the same thing? ∀u,v∈U\forall u, v \in U∀u,v∈U , if H(u)=H(v)H(u) = H(v)H(u)=H(v) then u=vu = vu=v . ∀u,v∈U\forall u, v \in U∀u,v∈U , if u≠vu \neq vu=v then H(u)≠H(v)H(u) \neq H(v)H(u)=H(v) .

    The second is the contrapositive of the first, so they are logically equivalent. Both are ways of saying that HHH is one-to-one.

41. [One-to-One and Onto, Inverse Functions] F:X→YF: X \to YF:X→Y is a function. In terms of its arrow diagram, when is FFF one-to-one?

    When every element of YYY has at most one arrow pointing to it. Each element of the range is the image of at most one element of the domain.

42. [One-to-One and Onto, Inverse Functions] Which of the functions FFF and GGG is one-to-one?

    FFF is one-to-one; GGG is not. G(a)=G(c)=wG(a) = G(c) = wG(a)=G(c)=w but a≠ca \neq ca=c .

43. [One-to-One and Onto, Inverse Functions] H,K:{1,2,3}→{a,b,c,d}H, K: \{1, 2, 3\} \to \{a, b, c, d\}H,K:{1,2,3}→{a,b,c,d} with H(1)=cH(1) = cH(1)=c , H(2)=aH(2) = aH(2)=a , H(3)=dH(3) = dH(3)=d and K(1)=dK(1) = dK(1)=d , K(2)=bK(2) = bK(2)=b , K(3)=dK(3) = dK(3)=d . Which is one-to-one?

    HHH is one-to-one; KKK is not. HHH sends the three elements to three different elements. K(1)=K(3)=dK(1) = K(3) = dK(1)=K(3)=d but 1≠31 \neq 31=3 .

44. [One-to-One and Onto, Inverse Functions] How can an algorithm check whether a function FFF on a finite set {a[1],…,a[n]}\{a[1], \dots, a[n]\}{a[1],…,a[n]} is one-to-one?

    Use a nested loop over all pairs (a[i],a[j])(a[i], a[j])(a[i],a[j]) with i<ji < ji<j : if some pair has F(a[i])=F(a[j])F(a[i]) = F(a[j])F(a[i])=F(a[j]) , FFF is not one-to-one; otherwise it is. This needs an independent algorithm to compute values of FFF .

45. [One-to-One and Onto, Inverse Functions] F:X→YF: X \to YF:X→Y is a function on an infinite set XXX . How do you prove that FFF is one-to-one, and how that it is not?

    Is: suppose x1,x2∈Xx_1, x_2 \in Xx1​,x2​∈X with F(x1)=F(x2)F(x_1) = F(x_2)F(x1​)=F(x2​) and show x1=x2x_1 = x_2x1​=x2​ . Is not: find concrete x1≠x2x_1 \neq x_2x1​=x2​ in XXX with F(x1)=F(x2)F(x_1) = F(x_2)F(x1​)=F(x2​) . The first is a direct proof, with x1,x2x_1, x_2x1​,x2​ particular but arbitrarily chosen. A good start is to try proving one-to-one; if it fails, the difficulty often shows a counterexample.

46. [One-to-One and Onto, Inverse Functions] Is f:R→Rf: \mathbf{R} \to \mathbf{R}f:R→R , f(x)=4x−1f(x) = 4x - 1f(x)=4x−1 , one-to-one?

    Yes. Suppose f(x1)=f(x2)f(x_1) = f(x_2)f(x1​)=f(x2​) , i.e. 4x1−1=4x2−14x_1 - 1 = 4x_2 - 14x1​−1=4x2​−1 . Adding 1 gives 4x1=4x24x_1 = 4x_24x1​=4x2​ , and dividing by 4 gives x1=x2x_1 = x_2x1​=x2​ .

47. [One-to-One and Onto, Inverse Functions] Is g:Z→Zg: \mathbf{Z} \to \mathbf{Z}g:Z→Z , g(n)=n2g(n) = n^2g(n)=n2 , one-to-one?

    No. g(2)=4=g(−2)g(2) = 4 = g(-2)g(2)=4=g(−2) but 2≠−22 \neq -22=−2 .

48. [One-to-One and Onto, Inverse Functions] What is a hash function, as used for storing records in a table?

    A function from a larger set of integers to a smaller one, often using mod; the record with key nnn is placed at position Hash(n)\mathit{Hash}(n)Hash(n) . Example: for at most 7 records keyed by social security numbers, Hash(n)=n mod 7\mathit{Hash}(n) = n \bmod 7Hash(n)=nmod7 ; Hash(328343419)=328343419−7⋅46906202=5\mathit{Hash}(328343419) = 328343419 - 7 \cdot 46906202 = 5Hash(328343419)=328343419−7⋅46906202=5 .

49. [One-to-One and Onto, Inverse Functions] When a hash function assigns the same table position to two records with different keys, this is called a collision.

    It happens because a hash function is usually not one-to-one.Example: with Hash(n)=n mod 7\mathit{Hash}(n) = n \bmod 7Hash(n)=nmod7 , the keys 9 and 16 both get position 2.

50. [One-to-One and Onto, Inverse Functions] In a hash table, what is a simple way to resolve a collision at position Hash(n)\mathit{Hash}(n)Hash(n) ?

    If position Hash(n)\mathit{Hash}(n)Hash(n) is occupied, search downward to the first empty position, going back to the top if necessary. To find the record with key nnn , compute Hash(n)\mathit{Hash}(n)Hash(n) and search downward from there. This is efficient as long as there are not too many collisions.

51. [One-to-One and Onto, Inverse Functions] A hash table has positions 0,…,60, \dots, 60,…,6 , with positions 0, 2, 3, 5 occupied. Hash(n)=n mod 7\mathit{Hash}(n) = n \bmod 7Hash(n)=nmod7 , and collisions are resolved by searching downward to the first empty position. Where is the record with key 908371011908371011908371011 placed?

    Position 4. 908371011 mod 7=2908371011 \bmod 7 = 2908371011mod7=2 ; positions 2 and 3 are occupied, 4 is free.

52. [One-to-One and Onto, Inverse Functions] F:X→YF: X \to YF:X→Y is a function. When is FFF onto (surjective)?

    For every y∈Yy \in Yy∈Y there is an x∈Xx \in Xx∈X with F(x)=yF(x) = yF(x)=y . Symbolically ∀y∈Y,∃x∈X\forall y \in Y, \exists x \in X∀y∈Y,∃x∈X such that F(x)=yF(x) = yF(x)=y . Equivalently, the range of FFF equals its co-domain. Example: F(x)=x+1F(x) = x + 1F(x)=x+1 on Z\mathbf{Z}Z is onto: y=F(y−1)y = F(y - 1)y=F(y−1) .

53. [One-to-One and Onto, Inverse Functions] F:X→YF: X \to YF:X→Y is a function. Write the negation: FFF is not onto if, and only if, … ?

    There is a y∈Yy \in Yy∈Y such that F(x)≠yF(x) \neq yF(x)=y for all x∈Xx \in Xx∈X . Some element of YYY is the image of no element of XXX . Example: F(n)=2nF(n) = 2nF(n)=2n on Z\mathbf{Z}Z is not onto: 1 is the image of no integer.

54. [One-to-One and Onto, Inverse Functions] Fill in "most" or "least": FFF is one-to-one if, and only if, each element of the co-domain is the image of at most one element of the domain; FFF is onto if, and only if, each element of the co-domain is the image of at least one element of the domain.

    In arrow diagrams: one-to-one means at most one arrow points to each element of the co-domain; onto means at least one arrow does.

55. [One-to-One and Onto, Inverse Functions] Which of the functions FFF and GGG is onto?

    GGG is onto; FFF is not. No arrow of FFF points to bbb . For GGG : a=G(3)a = G(3)a=G(3) , b=G(1)b = G(1)b=G(1) , c=G(2)=G(4)c = G(2) = G(4)c=G(2)=G(4) , d=G(5)d = G(5)d=G(5) .

56. [One-to-One and Onto, Inverse Functions] H,K:{1,2,3,4}→{a,b,c}H, K: \{1, 2, 3, 4\} \to \{a, b, c\}H,K:{1,2,3,4}→{a,b,c} with H(1)=cH(1) = cH(1)=c , H(2)=aH(2) = aH(2)=a , H(3)=cH(3) = cH(3)=c , H(4)=bH(4) = bH(4)=b and K(1)=cK(1) = cK(1)=c , K(2)=bK(2) = bK(2)=b , K(3)=bK(3) = bK(3)=b , K(4)=cK(4) = cK(4)=c . Which is onto?

    HHH is onto; KKK is not. a=H(2)a = H(2)a=H(2) , b=H(4)b = H(4)b=H(4) , c=H(1)c = H(1)c=H(1) . But a≠K(x)a \neq K(x)a=K(x) for every xxx .

57. [One-to-One and Onto, Inverse Functions] How can an algorithm check whether a function FFF from a finite set XXX to a finite set YYY is onto?

    For each y∈Yy \in Yy∈Y in turn, search through XXX for an xxx with F(x)=yF(x) = yF(x)=y ; if some search fails, FFF is not onto, otherwise it is. XXX and YYY are stored as arrays a[1..n]a[1..n]a[1..n] and b[1..m]b[1..m]b[1..m] , and a nested loop does the searches.

58. [One-to-One and Onto, Inverse Functions] F:X→YF: X \to YF:X→Y is a function and YYY is infinite. How do you prove that FFF is onto, and how that it is not?

    Is: suppose yyy is any element of YYY and show there is an x∈Xx \in Xx∈X with F(x)=yF(x) = yF(x)=y . Is not: find a concrete y∈Yy \in Yy∈Y with F(x)≠yF(x) \neq yF(x)=y for every x∈Xx \in Xx∈X . The first is the method of generalizing from the generic particular.

59. [One-to-One and Onto, Inverse Functions] Is f:R→Rf: \mathbf{R} \to \mathbf{R}f:R→R , f(x)=4x−1f(x) = 4x - 1f(x)=4x−1 , onto?

    Yes: for y∈Ry \in \mathbf{R}y∈R , x=y+14x = \frac{y + 1}{4}x=4y+1​ is a real number with f(x)=yf(x) = yf(x)=y . f(y+14)=4⋅y+14−1=(y+1)−1=yf\left(\frac{y + 1}{4}\right) = 4 \cdot \frac{y + 1}{4} - 1 = (y + 1) - 1 = yf(4y+1​)=4⋅4y+1​−1=(y+1)−1=y .

60. [One-to-One and Onto, Inverse Functions] To prove f(x)=4x−1f(x) = 4x - 1f(x)=4x−1 onto R\mathbf{R}R , scratch work solves 4x−1=y4x - 1 = y4x−1=y and gets x=y+14x = \frac{y + 1}{4}x=4y+1​ .Why is this scratch work not yet a proof, and what must the proof still check?

    It only shows what xxx has to be if it exists. The proof must check that y+14\frac{y + 1}{4}4y+1​ (1) is in the domain and (2) is really sent to yyy . Here (1) holds because sums and quotients (other than by 0) of real numbers are real.

61. [One-to-One and Onto, Inverse Functions] Is h:Z→Zh: \mathbf{Z} \to \mathbf{Z}h:Z→Z , h(n)=4n−1h(n) = 4n - 1h(n)=4n−1 , onto?

    No: 0 is the image of no integer. 4n−1=04n - 1 = 04n−1=0 gives n=14n = \frac{1}{4}n=41​ , which is not an integer. The same formula on R\mathbf{R}R is onto, so the domain and co-domain matter.

62. [One-to-One and Onto, Inverse Functions] bbb is a positive real number with b≠1b \neq 1b=1 . What is the exponential function with base bbb , exp⁡b\exp_bexpb​ ?

    The function exp⁡b:R→R+\exp_b: \mathbf{R} \to \mathbf{R}^+expb​:R→R+ with exp⁡b(x)=bx\exp_b(x) = b^xexpb​(x)=bx , where b0=1b^0 = 1b0=1 and b−x=1bxb^{-x} = \frac{1}{b^x}b−x=bx1​ . Example: exp⁡2(−3)=18\exp_2(-3) = \frac{1}{8}exp2​(−3)=81​ .

63. [One-to-One and Onto, Inverse Functions] Laws of exponents. For positive reals b,cb, cb,c and reals u,vu, vu,v : bubv= ?b^u b^v = \; ?bubv=? , (bu)v= ?\quad (b^u)^v = \; ?(bu)v=? , bubv= ?\quad \dfrac{b^u}{b^v} = \; ?bvbu​=? , (bc)u= ?\quad (bc)^u = \; ?(bc)u=?

    bu+v,buv,bu−v,bucu\boldsymbol{b^{u+v}, \quad b^{uv}, \quad b^{u-v}, \quad b^u c^u}bu+v,buv,bu−v,bucu Example: 22⋅23=32=252^2 \cdot 2^3 = 32 = 2^522⋅23=32=25 , (22)3=64=26\ (2^2)^3 = 64 = 2^6 (22)3=64=26 , 25/22=8=23\ 2^5 / 2^2 = 8 = 2^3 25/22=8=23 , (2⋅3)2=36=4⋅9\ (2 \cdot 3)^2 = 36 = 4 \cdot 9 (2⋅3)2=36=4⋅9 .

64. [One-to-One and Onto, Inverse Functions] bbb is a positive real number with b≠1b \neq 1b=1 . What follows from bu=bvb^u = b^vbu=bv (for reals u,vu, vu,v ), and from log⁡bu=log⁡bv\log_b u = \log_b vlogb​u=logb​v (for positive reals u,vu, vu,v )?

    u=vu = vu=v in both cases. The exponential and logarithmic functions with base bbb are one-to-one (and onto), which can be shown using calculus.

65. [One-to-One and Onto, Inverse Functions] Properties of logarithms. For positive reals b,c,x,yb, c, x, yb,c,x,y with b≠1b \neq 1b=1 , c≠1c \neq 1c=1 , what are the four properties?

    Product log⁡b(xy)=log⁡bx+log⁡by\log_b(xy) = \log_b x + \log_b ylogb​(xy)=logb​x+logb​y Example: log⁡232=log⁡2(4⋅8)=2+3=5\log_2 32 = \log_2(4 \cdot 8) = 2 + 3 = 5log2​32=log2​(4⋅8)=2+3=5 . Quotient log⁡bxy=log⁡bx−log⁡by\log_b \frac{x}{y} = \log_b x - \log_b ylogb​yx​=logb​x−logb​y Example: log⁡2324=5−2=3=log⁡28\log_2 \frac{32}{4} = 5 - 2 = 3 = \log_2 8log2​432​=5−2=3=log2​8 . Power log⁡b(xa)=alog⁡bx\log_b(x^a) = a \log_b xlogb​(xa)=alogb​x (for real aaa ) Example: log⁡2(82)=2⋅3=6=log⁡264\log_2(8…

66. [One-to-One and Onto, Inverse Functions] Change of base: log⁡cx=log⁡bxlog⁡bc\log_c x = \dfrac{\log_b x}{\log_b c}logc​x=logb​clogb​x​ for positive reals b,c,xb, c, xb,c,x with b,c≠1b, c \neq 1b,c=1 .How does the proof go?

    Let u=log⁡bcu = \log_b cu=logb​c , v=log⁡cxv = \log_c xv=logc​x , w=log⁡bxw = \log_b xw=logb​x . Then x=cv=(bu)v=buvx = c^v = (b^u)^v = b^{uv}x=cv=(bu)v=buv and x=bwx = b^wx=bw , so uv=wuv = wuv=w by the one-to-oneness of exp⁡b\exp_bexpb​ . So (log⁡bc)(log⁡cx)=log⁡bx(\log_b c)(\log_c x) = \log_b x(logb​c)(logc​x)=logb​x ; divide by log⁡bc\log_b clogb​c , which is nonzero because c≠1c \neq 1c=1 .

67. [One-to-One and Onto, Inverse Functions] A calculator shows ln⁡5≈1.609437912\ln 5 \approx 1.609437912ln5≈1.609437912 and ln⁡2≈0.6931471806\ln 2 \approx 0.6931471806ln2≈0.6931471806 . How do you get log⁡25\log_2 5log2​5 ?

    log⁡25=ln⁡5ln⁡2≈2.321928095\boldsymbol{\log_2 5 = \frac{\ln 5}{\ln 2} \approx 2.321928095}log2​5=ln2ln5​≈2.321928095 By the change of base formula log⁡cx=log⁡bxlog⁡bc\log_c x = \frac{\log_b x}{\log_b c}logc​x=logb​clogb​x​ with b=eb = eb=e .

68. [One-to-One and Onto, Inverse Functions] Logarithms with base 10 are called common logarithms (written log); logarithms with base eee are called natural logarithms (written ln).

    Example: log⁡1000=3\log 1000 = 3log1000=3 , ln⁡e2=2\ln e^2 = 2lne2=2 .

69. [One-to-One and Onto, Inverse Functions] What is a one-to-one correspondence (or bijection) from a set XXX to a set YYY ?

    A function F:X→YF: X \to YF:X→Y that is both one-to-one and onto. It pairs each element of XXX with exactly one element of YYY and each element of YYY with exactly one element of XXX ; so it can be used for counting. This bijection shows that XXX has 5 elements.

70. [One-to-One and Onto, Inverse Functions] A one-to-one correspondence is a function F:X→YF: X \to YF:X→Y that is one-to-one and onto.For a one-to-one correspondence FFF and y∈Yy \in Yy∈Y , why is there exactly one x∈Xx \in Xx∈X with F(x)=yF(x) = yF(x)=y ?

    At least one because FFF is onto; at most one because FFF is one-to-one.

71. [One-to-One and Onto, Inverse Functions] h:P({a,b})→{00,01,10,11}h: \mathcal{P}(\{a, b\}) \to \{00, 01, 10, 11\}h:P({a,b})→{00,01,10,11} sends a subset AAA to the string whose first bit is 1 if a∈Aa \in Aa∈A (else 0) and whose second bit is 1 if b∈Ab \in Ab∈A (else 0). Is hhh a one-to-one correspondence?

    Yes. Every string has exactly one arrow pointing to it.

72. [One-to-One and Onto, Inverse Functions] TTT is the set of all finite strings of xxx 's and yyy 's, and g:T→Tg: T \to Tg:T→T writes the characters of a string in reverse order. Is ggg a one-to-one correspondence?

    Yes. One-to-one: if s1s_1s1​ and s2s_2s2​ are equal when reversed, they are equal. Onto: given ttt , the string s=g(t)s = g(t)s=g(t) has g(s)=g(g(t))=tg(s) = g(g(t)) = tg(s)=g(g(t))=t .Example: g(xxy)=yxxg(xxy) = yxxg(xxy)=yxx .

73. [One-to-One and Onto, Inverse Functions] Is F:R×R→R×RF: \mathbf{R} \times \mathbf{R} \to \mathbf{R} \times \mathbf{R}F:R×R→R×R , F(x,y)=(x+y,x−y)F(x, y) = (x + y, x - y)F(x,y)=(x+y,x−y) , one-to-one? Why?

    Yes: x1+y1=x2+y2x_1 + y_1 = x_2 + y_2x1​+y1​=x2​+y2​ and x1−y1=x2−y2x_1 - y_1 = x_2 - y_2x1​−y1​=x2​−y2​ added give 2x1=2x22x_1 = 2x_22x1​=2x2​ , so x1=x2x_1 = x_2x1​=x2​ , and then y1=y2y_1 = y_2y1​=y2​ . F(x1,y1)=F(x2,y2)F(x_1, y_1) = F(x_2, y_2)F(x1​,y1​)=F(x2​,y2​) means both components are equal, which gives these two equations.

74. [One-to-One and Onto, Inverse Functions] Is F:R×R→R×RF: \mathbf{R} \times \mathbf{R} \to \mathbf{R} \times \mathbf{R}F:R×R→R×R , F(x,y)=(x+y,x−y)F(x, y) = (x + y, x - y)F(x,y)=(x+y,x−y) , onto? Which pair is sent to (u,v)(u, v)(u,v) ?

    Yes: (u+v2,u−v2)\left(\frac{u + v}{2}, \frac{u - v}{2}\right)(2u+v​,2u−v​) is sent to (u,v)(u, v)(u,v) . Solve r+s=ur + s = ur+s=u , r−s=vr - s = vr−s=v : adding gives r=u+v2r = \frac{u + v}{2}r=2u+v​ , subtracting gives s=u−v2s = \frac{u - v}{2}s=2u−v​ . Check: F(r,s)=(2u2,2v2)=(u,v)F(r, s) = \left(\frac{2u}{2}, \frac{2v}{2}\right) = (u, v)F(r,s)=(22u​,22v​)=(u,v) .

75. [One-to-One and Onto, Inverse Functions] Theorem 7.2.2 F:X→YF: X \to YF:X→Y is a one-to-one correspondence. Then there is a function F−1:Y→XF^{-1}: Y \to XF−1:Y→X defined for each y∈Yy \in Yy∈Y by … ?

    F−1(y)=F^{-1}(y) =F−1(y)= the unique x∈Xx \in Xx∈X with F(x)=yF(x) = yF(x)=y . In other words, F−1(y)=x⇔y=F(x)F^{-1}(y) = x \Leftrightarrow y = F(x)F−1(y)=x⇔y=F(x) . Such an xxx exists because FFF is onto, and it is unique because FFF is one-to-one.

76. [One-to-One and Onto, Inverse Functions] F:X→YF: X \to YF:X→Y is a one-to-one correspondence. What is the inverse function F−1F^{-1}F−1 for FFF ?

    The function F−1:Y→XF^{-1}: Y \to XF−1:Y→X that sends each yyy to the unique xxx with F(x)=yF(x) = yF(x)=y . Example: the logarithmic function with base bbb is the inverse of the exponential function with base bbb : log⁡28=3\log_2 8 = 3log2​8=3 because 23=82^3 = 823=8 .

77. [One-to-One and Onto, Inverse Functions] h:P({a,b})→{00,01,10,11}h: \mathcal{P}(\{a, b\}) \to \{00, 01, 10, 11\}h:P({a,b})→{00,01,10,11} is the one-to-one correspondence ∅↦00\emptyset \mapsto 00∅↦00 , {a}↦10\{a\} \mapsto 10{a}↦10 , {b}↦01\{b\} \mapsto 01{b}↦01 , {a,b}↦11\{a, b\} \mapsto 11{a,b}↦11 . How do you get h−1h^{-1}h−1 ?

    Reverse the arrows of hhh : h−1(00)=∅h^{-1}(00) = \emptyseth−1(00)=∅ , h−1(10)={a}h^{-1}(10) = \{a\}h−1(10)={a} , h−1(01)={b}h^{-1}(01) = \{b\}h−1(01)={b} , h−1(11)={a,b}h^{-1}(11) = \{a, b\}h−1(11)={a,b} .

78. [One-to-One and Onto, Inverse Functions] g:T→Tg: T \to Tg:T→T writes the characters of a string in reverse order ( TTT = all finite strings of xxx 's and yyy 's). What is g−1g^{-1}g−1 ?

    g−1=g\boldsymbol{g^{-1} = g}g−1=g Reversing a string twice gives back the original string.

79. [One-to-One and Onto, Inverse Functions] f:R→Rf: \mathbf{R} \to \mathbf{R}f:R→R , f(x)=4x−1f(x) = 4x - 1f(x)=4x−1 , is a one-to-one correspondence. What is f−1(y)f^{-1}(y)f−1(y) ?

    f−1(y)=y+14\boldsymbol{f^{-1}(y) = \frac{y + 1}{4}}f−1(y)=4y+1​ f(x)=y⇔4x−1=y⇔x=y+14f(x) = y \Leftrightarrow 4x - 1 = y \Leftrightarrow x = \frac{y + 1}{4}f(x)=y⇔4x−1=y⇔x=4y+1​ .

80. [One-to-One and Onto, Inverse Functions] F:R×R→R×RF: \mathbf{R} \times \mathbf{R} \to \mathbf{R} \times \mathbf{R}F:R×R→R×R , F(x,y)=(x+y,x−y)F(x, y) = (x + y, x - y)F(x,y)=(x+y,x−y) , is a one-to-one correspondence. What is F−1(u,v)F^{-1}(u, v)F−1(u,v) ?

    F−1(u,v)=(u+v2,u−v2)\boldsymbol{F^{-1}(u, v) = \left(\frac{u + v}{2}, \frac{u - v}{2}\right)}F−1(u,v)=(2u+v​,2u−v​) FFF sends this pair to (u,v)(u, v)(u,v) , and because FFF is one-to-one it is the only such pair.Example: F(2,1)=(3,1)F(2, 1) = (3, 1)F(2,1)=(3,1) and F−1(3,1)=(2,1)F^{-1}(3, 1) = (2, 1)F−1(3,1)=(2,1) .

81. [One-to-One and Onto, Inverse Functions] Theorem 7.2.3 If F:X→YF: X \to YF:X→Y is one-to-one and onto, then F−1:Y→XF^{-1}: Y \to XF−1:Y→X is … ?

    Also one-to-one and onto.

82. [One-to-One and Onto, Inverse Functions] F:X→YF: X \to YF:X→Y is one-to-one and onto, and F−1(y)F^{-1}(y)F−1(y) is the unique xxx with F(x)=yF(x) = yF(x)=y .Why is F−1F^{-1}F−1 one-to-one, and why is it onto?

    One-to-one: if F−1(y1)=F−1(y2)=xF^{-1}(y_1) = F^{-1}(y_2) = xF−1(y1​)=F−1(y2​)=x , then y1=F(x)=y2y_1 = F(x) = y_2y1​=F(x)=y2​ . Onto: each x∈Xx \in Xx∈X equals F−1(F(x))F^{-1}(F(x))F−1(F(x)) .

83. [Composition of Functions] f:X→Y′f: X \to Y&#x27;f:X→Y′ and g:Y→Zg: Y \to Zg:Y→Z are functions, and the range of fff is a subset of the domain YYY of ggg . What is the composition g∘fg \circ fg∘f of fff and ggg ?

    The function g∘f:X→Zg \circ f: X \to Zg∘f:X→Z with (g∘f)(x)=g(f(x))(g \circ f)(x) = g(f(x))(g∘f)(x)=g(f(x)) for all x∈Xx \in Xx∈X . g∘fg \circ fg∘f is read " ggg circle fff ", and g(f(x))g(f(x))g(f(x)) is read " ggg of fff of xxx ". Example: f(n)=n+1f(n) = n + 1f(n)=n+1 and g(n)=n2g(n) = n^2g(n)=n2 on Z\mathbf{Z}Z give (g∘f)(3)=g(4)=16(g \circ f)(3) = g(4) = 16(g∘f)(3)=g(4)=16 .

84. [Composition of Functions] When can the composition g∘fg \circ fg∘f of two functions fff and ggg be formed?

    When the range of fff is a subset of the domain of ggg . Every output of fff must be an acceptable input of ggg .Example: f:R→Rf: \mathbf{R} \to \mathbf{R}f:R→R , f(x)=−1f(x) = -1f(x)=−1 and g:R+→Rg: \mathbf{R}^+ \to \mathbf{R}g:R+→R , g(x)=xg(x) = \sqrt{x}g(x)=x​ : the range {−1}\{-1\}{−1} of fff is not a subset of R+\mathbf{R}^+R+ , so g∘fg \circ fg∘f is not defined.

85. [Composition of Functions] Why is g∘fg \circ fg∘f called the composition "of fff and ggg ", with fff named first?

    An element xxx is acted upon first by fff , then by ggg . Example: in (g∘f)(x)=g(f(x))(g \circ f)(x) = g(f(x))(g∘f)(x)=g(f(x)) , the value f(x)f(x)f(x) is computed before ggg is applied.

86. [Composition of Functions] What is the difference between g∘fg \circ fg∘f and g(f(x))g(f(x))g(f(x)) ?

    g∘fg \circ fg∘f is the name of a function; g(f(x))g(f(x))g(f(x)) is the value of that function at xxx . Example: with f(n)=n+1f(n) = n + 1f(n)=n+1 and g(n)=n2g(n) = n^2g(n)=n2 , g∘fg \circ fg∘f is the function n↦(n+1)2n \mapsto (n + 1)^2n↦(n+1)2 , while g(f(2))=9g(f(2)) = 9g(f(2))=9 is a number.

87. [Composition of Functions] f:Z→Zf: \mathbf{Z} \to \mathbf{Z}f:Z→Z is the successor function f(n)=n+1f(n) = n + 1f(n)=n+1 , and g:Z→Zg: \mathbf{Z} \to \mathbf{Z}g:Z→Z is the squaring function g(n)=n2g(n) = n^2g(n)=n2 . Find g∘fg \circ fg∘f and f∘gf \circ gf∘g .

    (g∘f)(n)=(n+1)2(g \circ f)(n) = \boldsymbol{(n + 1)^2}(g∘f)(n)=(n+1)2 and (f∘g)(n)=n2+1(f \circ g)(n) = \boldsymbol{n^2 + 1}(f∘g)(n)=n2+1 for all n∈Zn \in \mathbf{Z}n∈Z . (g∘f)(n)=g(f(n))=g(n+1)=(n+1)2(g \circ f)(n) = g(f(n)) = g(n + 1) = (n + 1)^2(g∘f)(n)=g(f(n))=g(n+1)=(n+1)2 and (f∘g)(n)=f(g(n))=f(n2)=n2+1(f \circ g)(n) = f(g(n)) = f(n^2) = n^2 + 1(f∘g)(n)=f(g(n))=f(n2)=n2+1 .

88. [Composition of Functions] Is composition of functions commutative, i.e. does g∘f=f∘gg \circ f = f \circ gg∘f=f∘g always hold?

    No. g∘fg \circ fg∘f and f∘gf \circ gf∘g need not be equal (although they may be). Two functions from one set to another are equal if, and only if, they take the same value at every element.Example: f(n)=n+1f(n) = n + 1f(n)=n+1 and g(n)=n2g(n) = n^2g(n)=n2 on Z\mathbf{Z}Z : (g∘f)(1)=(1+1)2=4(g \circ f)(1) = (1 + 1)^2 = 4(g∘f)(1)=(1+1)2=4 , but (f∘g)(1)=12+1=2(f \circ g)(1) = 1^2 + 1 = 2(f∘g)(1)=12+1=2 .

89. [Composition of Functions] X={1,2,3}X = \{1, 2, 3\}X={1,2,3} , Y′={a,b,c,d}Y&#x27; = \{a, b, c, d\}Y′={a,b,c,d} , Y={a,b,c,d,e}Y = \{a, b, c, d, e\}Y={a,b,c,d,e} , Z={x,y,z}Z = \{x, y, z\}Z={x,y,z} , and f:X→Y′f: X \to Y&#x27;f:X→Y′ and g:Y→Zg: Y \to Zg:Y→Z are given by the arrow diagrams below. Find g∘fg \circ fg∘f and its range.

    (g∘f)(1)=z(g \circ f)(1) = z(g∘f)(1)=z , (g∘f)(2)=y(g \circ f)(2) = y(g∘f)(2)=y , (g∘f)(3)=y(g \circ f)(3) = y(g∘f)(3)=y ; range {y,z}\{y, z\}{y,z} . Trace the arrows from XXX to ZZZ through YYY : g(f(1))=g(c)=zg(f(1)) = g(c) = zg(f(1))=g(c)=z , g(f(2))=g(b)=yg(f(2)) = g(b) = yg(f(2))=g(b)=y , g(f(3))=g(a)=yg(f(3)) = g(a) = yg(f(3))=g(a)=y .

90. [Composition of Functions] Theorem 7.3.1 (Composition with an Identity Function) fff is a function from a set XXX to a set YYY , and IXI_XIX​ , IYI_YIY​ are the identity functions on XXX and YYY ( IX(x)=xI_X(x) = xIX​(x)=x for all x∈Xx \in Xx∈X ). Then f∘IX= ?f \circ I_X = \; ?f∘IX​=? and IY∘f= ?I_Y \circ f = \; ?IY​∘f=?

    f∘IX=ff \circ I_X = \boldsymbol{f}f∘IX​=f and IY∘f=fI_Y \circ f = \boldsymbol{f}IY​∘f=f Example: X={a,b}X = \{a, b\}X={a,b} , Y={u,v}Y = \{u, v\}Y={u,v} , f:X→Yf: X \to Yf:X→Y with f(a)=vf(a) = vf(a)=v , f(b)=vf(b) = vf(b)=v : (f∘IX)(a)=f(a)=v(f \circ I_X)(a) = f(a) = v(f∘IX​)(a)=f(a)=v and (IY∘f)(b)=IY(v)=v=f(b)(I_Y \circ f)(b) = I_Y(v) = v = f(b)(IY​∘f)(b)=IY​(v)=v=f(b) .

91. [Composition of Functions] f:X→Yf: X \to Yf:X→Y is a function and IXI_XIX​ is the identity function on XXX . Why is f∘IX=ff \circ I_X = ff∘IX​=f ?

    For every x∈Xx \in Xx∈X : (f∘IX)(x)=f(IX(x))=f(x)(f \circ I_X)(x) = f(I_X(x)) = f(x)(f∘IX​)(x)=f(IX​(x))=f(x) . So the two functions take the same value at every element of XXX , which is the definition of equal functions.

92. [Composition of Functions] Theorem 7.3.2 (Composition of a Function with Its Inverse) f:X→Yf: X \to Yf:X→Y is one-to-one and onto, with inverse function f−1:Y→Xf^{-1}: Y \to Xf−1:Y→X . Then f−1∘f= ?f^{-1} \circ f = \; ?f−1∘f=? and f∘f−1= ?f \circ f^{-1} = \; ?f∘f−1=?

    f−1∘f=IXf^{-1} \circ f = \boldsymbol{I_X}f−1∘f=IX​ and f∘f−1=IYf \circ f^{-1} = \boldsymbol{I_Y}f∘f−1=IY​ fff assigns to xxx the element f(x)f(x)f(x) , and f−1f^{-1}f−1 assigns to f(x)f(x)f(x) the element xxx again.Example: f:{a,b,c}→{x,y,z}f: \{a, b, c\} \to \{x, y, z\}f:{a,b,c}→{x,y,z} with f(a)=zf(a) = zf(a)=z , f(b)=xf(b) = xf(b)=x , f(c)=yf(c) = yf(c)=y : (f−1∘f)(a)=f−1(z)=a(f^{-1} \circ f)(a) = f^{-1}(z) = a(f−1∘f)(a)=f−1(z)=a , (f−1∘f)(b)=f−1(x)=b(f^{-1} \circ f)(b) = f^{-1}(x) = b(f−1∘f…

93. [Composition of Functions] f:X→Yf: X \to Yf:X→Y is one-to-one and onto with inverse f−1f^{-1}f−1 , where f−1(b)=a⇔f(a)=bf^{-1}(b) = a \Leftrightarrow f(a) = bf−1(b)=a⇔f(a)=b for all a∈Xa \in Xa∈X , b∈Yb \in Yb∈Y .How does the proof show that (f−1∘f)(x)=x(f^{-1} \circ f)(x) = x(f−1∘f)(x)=x for every x∈Xx \in Xx∈X ?

    Let x′=f−1(f(x))x&#x27; = f^{-1}(f(x))x′=f−1(f(x)) . By the property of f−1f^{-1}f−1 , f(x′)=f(x)f(x&#x27;) = f(x)f(x′)=f(x) , and since fff is one-to-one, x′=xx&#x27; = xx′=x . So (f−1∘f)(x)=f−1(f(x))=x′=x(f^{-1} \circ f)(x) = f^{-1}(f(x)) = x&#x27; = x(f−1∘f)(x)=f−1(f(x))=x′=x .

94. [Composition of Functions] Theorem 7.3.3 If f:X→Yf: X \to Yf:X→Y and g:Y→Zg: Y \to Zg:Y→Z are both one-to-one functions, then … ?

    g∘fg \circ fg∘f is one-to-one. Example: here g∘fg \circ fg∘f assigns a↦1a \mapsto 1a↦1 , b↦4b \mapsto 4b↦4 , c↦5c \mapsto 5c↦5 : three different values.

95. [Composition of Functions] f:X→Yf: X \to Yf:X→Y and g:Y→Zg: Y \to Zg:Y→Z are one-to-one. With what supposition does a direct proof that g∘fg \circ fg∘f is one-to-one start, and what must it show?

    Suppose x1,x2∈Xx_1, x_2 \in Xx1​,x2​∈X with (g∘f)(x1)=(g∘f)(x2)(g \circ f)(x_1) = (g \circ f)(x_2)(g∘f)(x1​)=(g∘f)(x2​) ; show x1=x2x_1 = x_2x1​=x2​ . This is the definition of one-to-one with g∘fg \circ fg∘f substituted: ∀x1,x2∈X\forall x_1, x_2 \in X∀x1​,x2​∈X , if (g∘f)(x1)=(g∘f)(x2)(g \circ f)(x_1) = (g \circ f)(x_2)(g∘f)(x1​)=(g∘f)(x2​) then x1=x2x_1 = x_2x1​=x2​ .

96. [Composition of Functions] f:X→Yf: X \to Yf:X→Y and g:Y→Zg: Y \to Zg:Y→Z are one-to-one, and x1,x2∈Xx_1, x_2 \in Xx1​,x2​∈X satisfy (g∘f)(x1)=(g∘f)(x2)(g \circ f)(x_1) = (g \circ f)(x_2)(g∘f)(x1​)=(g∘f)(x2​) .What are the steps to x1=x2x_1 = x_2x1​=x2​ ?

    g(f(x1))=g(f(x2))g(f(x_1)) = g(f(x_2))g(f(x1​))=g(f(x2​)) , so f(x1)=f(x2)f(x_1) = f(x_2)f(x1​)=f(x2​) because ggg is one-to-one, so x1=x2x_1 = x_2x1​=x2​ because fff is one-to-one. The first step is the definition of composition. This proves that a composition of one-to-one functions is one-to-one.

97. [Composition of Functions] Theorem 7.3.4 If f:X→Yf: X \to Yf:X→Y and g:Y→Zg: Y \to Zg:Y→Z are both onto functions, then … ?

    g∘fg \circ fg∘f is onto. Example: in these diagrams fff and ggg are onto, and g∘fg \circ fg∘f assigns a↦1a \mapsto 1a↦1 , b↦3b \mapsto 3b↦3 , c↦2c \mapsto 2c↦2 , d↦2d \mapsto 2d↦2 , e↦3e \mapsto 3e↦3 , so every element of ZZZ is a value of g∘fg \circ fg∘f .

98. [Composition of Functions] f:X→Yf: X \to Yf:X→Y and g:Y→Zg: Y \to Zg:Y→Z are onto. With what supposition does a direct proof that g∘fg \circ fg∘f is onto start, and what must it show?

    Suppose zzz is a particular but arbitrarily chosen element of ZZZ ; show there is an x∈Xx \in Xx∈X with (g∘f)(x)=z(g \circ f)(x) = z(g∘f)(x)=z . A proof that a function is onto must start with an arbitrary element of the co-domain and show that it is the image of some element of the domain.

99. [Composition of Functions] f:X→Yf: X \to Yf:X→Y and g:Y→Zg: Y \to Zg:Y→Z are onto, and zzz is an arbitrary element of ZZZ .How does the proof find x∈Xx \in Xx∈X with (g∘f)(x)=z(g \circ f)(x) = z(g∘f)(x)=z ?

    ggg is onto, so g(y)=zg(y) = zg(y)=z for some y∈Yy \in Yy∈Y ; fff is onto, so f(x)=yf(x) = yf(x)=y for some x∈Xx \in Xx∈X . Then (g∘f)(x)=g(f(x))=g(y)=z(g \circ f)(x) = g(f(x)) = g(y) = z(g∘f)(x)=g(f(x))=g(y)=z . This proves that a composition of onto functions is onto.

100. [Composition of Functions] To prove that g∘fg \circ fg∘f is onto for onto f:X→Yf: X \to Yf:X→Y and g:Y→Zg: Y \to Zg:Y→Z , a student wrote: ∀y∈Y,∃x∈X\forall y \in Y, \exists x \in X∀y∈Y,∃x∈X such that f(x)=yf(x) = yf(x)=y (*), and ∀z∈Z,∃y∈Y\forall z \in Z, \exists y \in Y∀z∈Z,∃y∈Y such that f(y)=zf(y) = zf(y)=z . So (g∘f)(x)=g(f(x))=g(y)=z(g \circ f)(x) = g(f(x)) = g(y) = z(g∘f)(x)=g(f(x))=g(y)=z , and thus g∘fg \circ fg∘f is onto.What is wrong?

     The proof never starts with an arbitrary z∈Zz \in Zz∈Z , and the xxx and yyy in (*) are not specific elements. (*) only says that fff is onto; renaming its x,yx, yx,y to u,vu, vu,v gives an equivalent statement, after which "So (g∘f)(x)=…(g \circ f)(x) = \dots(g∘f)(x)=… " has no justification. (The second statement should also read g(y)=zg(y) = zg(y)=z .)