6.5: Properties of Functions
( \newcommand{\kernel}{\mathrm{null}\,}\)
In this section, we will study some properties of functions. To facilitate our discussion, we need to introduce some notations. Some students may find them confusing and difficult to use. Besides memorizing the definitions, try to understand what they really mean.
Definition: image of under
Given a function f:A→B, and C⊆A, the image of under f is defined as f(C)={f(x)∣x∈C}. In words, f(C) is the set of all the images of the elements of C.
A few remarks about the definition:
- It is about the image of a subset C of the domain of A. Do not confuse it with the image of an element x from A.
- Therefore, do not merely say “the image.” Be specific: the image of an element, or the image of a subset.
- Better yet: include the notation f(x) or f(C) in the discussion.
- While f(x) is an element in the codomain, f(C) is a subset of the codomain.
- Perhaps, the most important thing to remember is:
If y∈f(C), then y∈B, and there exists an x∈C such that f(x)=y.
This key observation is often what we need to start a proof with.
Definition: image
Let f:AB be a function. The image or range of f, denoted imf, is defined as the set f(A). Hence, imf is the set of all possible images that f can assume.
The definition implies that a function f:A→B is onto if imf=B. Unfortunately, this observation is of limited use, because it is not always easy to find imf.
Example 6.5.1
For the function f:R→R defined by
f(x)=x2,
we find imf=[0,∞). We also have, for example, f([2,∞))=[4,∞). It is clear that f is neither one-to-one nor onto.
Example 6.5.2
For the function g:Z→Z defined by g(n)=n+3, we find img=Z, and g(N)={4,5,6,…}. The function g is both one-to-one and onto.
Exercise 6.5.1
The function p:R→R is defined as p(x)=3x+11. Find p(R+) and imp.
Exercise 6.5.2
The function q:R→R is defined as q(x)=x2−x−7. Find imq.
Example 6.5.3
The function h:Z15→Z15 is defined by
h(x)≡5x−11(mod15).
From the tabulated data
x0123456⋯14f(x)491449144⋯14
it becomes clear that the images repeat the pattern 4, 9, 14 five times. Therefore, we determine that imh={4,9,14}.
Exercise 6.5.3
Determine h({0,3,4}), where h is defined in Example 6.5.3.
Example 6.5.4
Determine f({(0,2),(1,3)}), where the function f:{0,1,2}×{0,1,2,3}Z is defined according to
f(a,b)=a+b.
Remark: Strictly speaking, we should write f((a,b)) because the argument is an ordered pair of the form (a,b). However, we often write f(a,b), because f can be viewed as a two-variable function. The first variable comes from {0,1,2}, the second comes from {0,1,2,3}, and we add them to form the image.
- Solution
-
Because f(0,2)=0+2=2,andf(1,3)=1+3=4, we determine that f({(0,2),(1,3)})={2,4}.
Exercise 6.5.4
Find imf, where f is defined in Example 6.5.4.
We are now ready to present the first collection of properties of functions.
Theorem 6.5.1
Given f:A→B, the following properties hold for any C1,C2⊆A.
- f(C1∪C2)=f(C1)∪f(C2)
- f(C1∩C2)⊆f(C1)∩f(C2)
- f(C1−C2)⊇f(C1)−f(C2)
- C1⊆C2⇒f(C1)⊆f(C2)
Remark
These results provide excellent opportunities to learn how to write mathematical proofs. We only provide the proof of (a) below, and leave the proofs of (b)–(d) as exercises. In (a), we want to establish the equality of two sets. One way to prove that S=T is to show that S⊆T, and T⊆S. Now, in order to prove that S⊆T, we need to show that z∈S implies z∈T; to show that T⊆S, we want to prove that z∈T implies z∈s.
- Proof of (a)
-
First, we want to show that f(C1∪C2)⊆f(C1)∪f(C2). Let y∈f(C1∪C2), then there exists x∈C1∪C2 such that f(x)=y. Having x∈C1∪C2 means either x∈C1 or x∈C2, so we have to consider two cases.
- If x∈C1, then f(x)∈f(C1).
- If x∈C2, then f(x)∈f(C2).
Thus, y=f(x) belongs to either f(C1) or f(C2), which means y=f(x)∈f(C1)∪f(C2). This proves that f(C1∪C2)⊆f(C1)∪f(C2).
Next, we want to show that f(C1)∪f(C2)⊆f(C1∪C2). Let y∈f(C1)∪f(C2), then y belongs to either f(C1) or f(C2).
- If y∈f(C1), then there exists x1∈C1 such that f(x1)=y.
- If y∈f(C2), then there exists x2∈C2 such that f(x2)=y.
These two possibilities together imply that there exists an element x belonging to either C1 or C2, that is, x∈C1∪C2, such that f(x)=y. This means f(x)∈f(C1∪C2). This proves that f(C1)∪f(C2)⊆f(C1∪C2). This concludes the proof of f(C1∪C2)=f(C1)∪f(C2).
Exercise 6.5.5
Prove part (b) of Theorem 6.5.1.
Remark
Part (b) of Theorem 6.5.2 only gives a subset relationship. The reason is: having y∈f(C1) and y∈f(C2) does not necessarily mean that y is the image of the same element. Since f can be many-to-one, it is possible to have x1∈C1−C2 and x2∈C2−C1 such that f(x1)=f(x2)=y. Consider f:{1,2,3}→{a,b} defined by f(1)=f(3)=a,andf(2)=b. If C1={1,2} and C2={2,3}, then f(C1)=f(C2)={a,b}, and f(C1∩C2)=f({2})={b}⊂{a,b}=f(C1)∩f(C2). Therefore, we can only conclude that y∈f(C1∩C2)⇒y∈f(C1)∩f(C2).
Definition: preimage of under
Given a function f:A→B, and D⊆B, the preimage of under is defined as f−1(D)={x∈A∣f(x)∈D}. Hence, f−1(D) is the set of elements in the domain whose images are in C. The symbol f−1(D) is also pronounced as “f inverse of D.”
Some remarks about the definition:
- The preimage of D is a subset of the domain A.
- In particular, the preimage of B is always A.
- The key thing to remember is:
If x∈f−1(D), then x∈A, and f(x)∈D.
- It is possible that f−1(D)=∅ for some subset D. If this happens, f is not onto.
- Therefore, f is onto if and only if f−1({b})≠∅ for every b∈B.
Example 6.5.5
If t:R→R is defined by t(x)=x2−5x+5, find t−1({−1}).
- Solution
-
We want to find x such that t(x)=x2−5x+5=−1. Hence, we have to solve the equation 0=x2−5x+6=(x−2)(x−3). The solutions are x=2 and x=3. Therefore, t−1({−1})={2,3}.
Exercise 6.5.6
If k:Q→R is defined by k(x)=x2−x−7, find k−1({3}).
Example 6.5.6
For the function f:{0,1,2}×{0,1,2,3}→Z defined by f(a,b)=a+b, we find f−1({3})={(0,3),(1,2),(2,1)},f−1({4})={(1,3),(2,2)}. Since preimages are sets, we need to write the answers in set notation.
Exercise 6.5.7
Find h−1({4}) and h−1({2}), where the function h is defined in Example 6.5.3.
Theorem 6.5.2
Given f:A→B, and D1,D2⊆B, the following properties hold.
- f−1(D1∪D2)=f−1(D1)∪f−1(D2)
- f−1(D1∩D2)=f−1(D1)∩f−1(D2)
- f−1(D1−D2)=f−1(D1)−f−1(D2)
- D1⊆D2⇒f−1(D1)⊆f−1(D2)
- Proof of (a)
-
First, we want to prove that f−1(D1∪D2)⊆f−1(D1)∪f−1(D2). Let x∈f−1(D1∪D2), then f(x)∈D1∪D2. This means either f(x)∈D1 or f(x)∈D2.
- If f(x)∈D1, then x∈f−1(D1).
- If f(x)∈D2, then x∈f−1(D2).
Since x belongs to either f−1(D1) or f−1(D2), we determine that x∈f−1(D1)∪f−1(D2). Therefore, f−1(D1∪D2)⊆f−1(D1)∪f−1(D2).
Next, we want to prove that f−1(D1)∪f−1(D2)⊆f−1(D1∪D2). Let x∈f−1(D1)∪f−1(D2). Then x belongs to either f−1(D1) or x∈f−1(D2).
- If x∈f−1(D1), then f(x)∈D1.
- If x∈f−1(D2), then f(x)∈D2.
Hence, f(x) belongs to either D1 or D2, which means f(x)∈D1∪D2. Thus, x∈f−1(D1∪D2). We have proved that f−1(D1)∪f−1(D2)⊆f−1(D1∪D2). Together with f−1(D1∪D2)⊆f−1(D1)∪f−1(D2), we conclude that f−1(D1∪D2)=f−1(D1)∪f−1(D2).
Exercise 6.5.8
Prove part (b) of Theorem 6.5.2.
Whether a function f:AB is one-to-one or onto can be determined by the cardinality of the preimages.
- f is one-to-one if and only if |f−1({b})|≤1 for every b∈B.
- f is onto if and only if |f−1({b})|≥1 for every b∈B.
If A and B are finite sets, then
- |A|≤|B| if f is one-to-one, and
- |A|≥|B| if f is onto.
In particular, if f is one-to-one and onto, we have |A|=|B|.
Example 6.5.7
A function f:Z14→Z10 cannot be one-to-one because in order for it to be one-to-one, we need 14 distinct images. Since the codomain has only 10 elements, it is impossible for it to come up with 14 different images.
Likewise, a function g:Z23→Z57 cannot be onto because the domain has 23 elements, hence, we can have at most 23 different images. But the codomain has 57 elements, therefore, some of its elements must be left unused.
Example 6.5.8
Consider the function h:Z23→Z57 defined by h(x)≡43x(mod57). If y≡43x (mod 57), then, since 43−1≡4 (mod 57), we find, in Z23, x=43−1y=4y. Since we can also express x in terms of y, we declare that f is onto. Yet, we have learned from the previous example that f cannot be onto. Is there any contradiction?
- Solution
-
There is an error in the argument. We should have said x≡43−1y≡4y(mod57). Since x is reduced modulo 57, its value may exceed 23. If this happens, x∉Z23. For example, if y=11, we would have x=44∉Z23. Even if we reduce 44 modulo 23, we obtain x≡21 (mod 23), we would have 43⋅21≡48≢11(mod57). So it is still not the correct preimage. This example again illustrates the importance of taking caution when a function involves different moduli in its domain and codomain.
Summary and Review
- Given a function f:A→B, the image of C⊆A is defined as f(C)={f(x)∣x∈C}.
- If y∈f(C), then y∈B, and there exists an x∈C such that f(x)=y.
- See Theorem 6.5.1 for a list of properties of the image of a set.
- The preimage of D⊆B is defined as f−1(D)={x∈A∣f(x)∈D}.
- If x∈f−1(D), then x∈A, and f(x)∈D.
- See Theorem 6.5.2 for a list of properties of the preimage of a set.
Exercise 6.5.1
For each of the following functions, find the image of C, and the preimage of D.
- f1:{1,2,3,4,5}→{a,b,c,d}; f1(1)=b, f1(2)=c, f1(3)=a, f1(4)=a, f1(5)=c;C={1,3}, D={a.c}.
- f2:{1,2,3,4}→{a,b,c,d,e}; f2(1)=c, f2(2)=b, f2(3)=a, f2(4)=d;C={1,3}, D={b,d}.
- f3:{1,2,3,4,5}→{a,b,c,d,e}; f3(1)=b, f3(2)=b, f3(3)=b, f3(4)=a, f3(5)=d;C={1,3,5}, D={c}.
- f4:{1,2,3,4,5}→{a,b,c,d,e}; f4(1)=d, f4(2)=b, f4(3)=e, f4(4)=a, f4(5)=c;C={3}, D={c}.
Exercise 6.5.2
For each of the following functions, find the image of C, and the preimage of D.
- f5:Z→Z; f5(n)=−n; C=2Z, D=N.
- f6:Z→Z; f6(n)={2n if n<0, −3n if n≥0,; C=N, D=2Z.
- f7:N→N; f7(n)={n+12 if n is odd n2 if n is even ; C=D=2N.
- f8:N→N; f8(n)={n+1 if n is odd n−1 if n is even ; C=D=2N.
Exercise 6.5.3
The function s:Z12→Z12 is defined as s(x)≡4x+7(mod12).
- Find s({2,5,7}).
- Find s−1({2,5,7}).
- Find ims.
Exercise 6.5.4
The function t:Z15→Z15 is defined as t(x)≡3x2−5(mod15).
- Find t({2,3,5,13}).
- Find t−1({1,5,7}).
- Find imt.
Exercise 6.5.5
The function u:R→R is defined as u(x)=3x+11, and the function v:Z→R is defined as v(x)=3x+11.
- Find u([3,5)) and v({3,4,5}).
- Find u−1((2,7]) and v−1((2,7]).
Exercise 6.5.6
Is the function h:Z→Z defined by h(n)={2n if n≥0 −n if n<0 one-to-one? Is it onto?
Exercise 6.5.7
Define the r:Z×Z→Q according to r(m,n)=3m5n.
- Find r({1,2,3}×{−1,0,1}).
- Find r−1({2527}).
- Find r−1(D), where D={3,9,27,81,…}.
Exercise 6.5.8
Define the function p:Z×Z→Z according to p(x,y)=12x+15y.
- Find p−1({18}). You may use the set-builder notation to describe your answer.
- Find imp.
Exercise 6.5.9
The sum of the entries in a particular row in a matrix is called a row sum, and the sum of the entries in a particular column is called a column sum. Discuss how can we use the row sums and column sums of the incidence matrix of a function to determine if the function is well-defined, one-to-one, and onto.
Exercise 6.5.10
Below is the incidence matrix of the function f:{a,b,c,d,e}→{α,β,γ,δ,ϵ}: αβγδϵabcde(0000100010100000010010000)
- Find f({a,d,e}).
- Find f−1({α,β,ϵ}).
- Find imf.
Exercise 6.5.11
Consider the function h1 defined in Problem 6.5.8a in Exercises 1.2. What is h−11({m}), if m represents your mother?
Exercise 6.5.12
Let S denote the maternal family tree, that includes you, your mother, your maternal grandmother, your maternal great-grandmother, and so on. Define a function M:S→S by letting M(x) be the mother of x. Determine imM.
Exercise 6.5.13
Prove part (c) of Theorem 6.5.1.
Exercise 6.5.14
Prove part (c) of Theorem 6.5.2.
Exercise 6.5.15
- (a) Prove part (d) of Theorem 6.5.1.
- (b) Prove part (d) of Theorem 6.5.2.
Exercise 6.5.16
Construct an example of a function f:AB, and C1,C2⊆A such that f(C1−C2)⊋f(C1)−f(C2). See part (c) of Theorem 6.5.1.
Exercise 6.5.17
Given a function f:A→B, and C⊂A, since f(C) is a subset of B, the preimage of this subset is indicated by the notation f−1(f(C)). Consider the function f:Z→Z defined by f(x)=x2, and C={0,1,2,3}.
- Find f(C).
- Find f−1(f(C)).
Exercise 6.5.18
Prove that C⊆f−1(f(C)) for any function f:A→B, and C⊆A.