5.3: One-to-One Functions
( \newcommand{\kernel}{\mathrm{null}\,}\)
We distinguish two special families of functions: one-to-one functions and onto functions. We shall discuss one-to-one functions in this section. Onto functions were introduced in section 5.2 and will be developed more in section 5.4.
One-to-One (Injective)
Recall that under a function each value in the domain has a unique image in the range. For a one-to-one function, we add the requirement that each image in the range has a unique pre-image in the domain.
Definition: One-to-One (Injection)
A function f:A→B is said to be one-to-one if
f(x1)=f(x2)⇒x1=x2
for all elements x1,x2∈A. A one-to-one function is also called an injection, and we call a function injective if it is one-to-one. A function that is not one-to-one is referred to as many-to-one.
The contrapositive of this definition is: A function f:A→B is one-to-one ifx1≠x2⇒f(x1)≠f(x2)
Any function is either one-to-one or many-to-one. A function cannot be one-to-many because no element can have multiple images. The difference between one-to-one and many-to-one functions is whether there exist distinct elements that share the same image. There are no repeated images in a one-to-one function.
Definition: Identity Function
The identity function on any nonempty set A IA:A→A,IA(x)=x, maps any element back to itself.
It is clear that all identity functions are one-to-one.
Example 5.3.1
The function h:A→A defined by h(x)=c for some fixed element c∈A, is an example of a constant function. It is a function with only one image. This is the exact opposite of an identity function. It is clearly not one-to-one unless |A|=1.
For domains with a small number of elements, one can use inspection on the images to determine if the function is one-to-one. This becomes impossible if the domain contains a larger number of elements.
In practice, it is easier to use the contrapositive of the definition to test whether a function is one-to-one:
f(x1)=f(x2)⇒x1=x2
To prove a function is One-to-One
To prove f:A→B is one-to-one:
- Assume f(x1)=f(x2)
- Show it must be true that x1=x2
- Conclude: we have shown if f(x1)=f(x2) then x1=x2, therefore f is one-to-one, by definition of one-to-one.
Example 5.3.2
Prove the function f:R→R defined by f(x)=3x+2 is one-to-one.
- Solution
-
Assume f(x1)=f(x2), which means 3x1+2=3x2+2.
Thus 3x1=3x2
so x1=x2.
We have shown if f(x1)=f(x2) then x1=x2. Therefore f is one-to-one, by definition of one-to-one.
Hands-on exercise 5.3.1
Prove the function g:R→R defined by g(x)=5−7x is one-to-one.
Hands-on exercise 5.3.2
Determine whether the function h:[2,∞)→R defined by h(x)=√x−2 is one-to-one.
Interestingly, sometimes we can use calculus to determine if a real function is one-to-one. A real function f is increasing if x1<x2⇒f(x1)<f(x2), and decreasing if x1<x2⇒f(x1)>f(x2). Obviously, both increasing and decreasing functions are one-to-one. From calculus, we know that
- A function is increasing over an open interval (a,b) if f′(x)>0 for all x∈(a,b).
- A function is decreasing over an open interval (a,b) if f′(x)<0 for all x∈(a,b).
Therefore, if the derivative of a function is always positive, or always negative, then the function must be one-to-one.
Example 5.3.4
The function p:R→R defined by p(x)=2x3−5 is one-to-one, because p′(x)=6x2>0 for any x∈R∗. Likewise, the function q:(−π2,π2)→R defined by q(x)=tanx is also one-to-one, because q′(x)=sec2x>0 for any x∈(−π2,π2).
Hands-on exercise 5.3.3
Use both methods to show that the function k:(0,∞)→R defined by k(x)=lnx is one-to-one.
To prove a function is NOT one-to-one
To prove f:A→B is NOT one-to-one:
- Exhibit one case (a counterexample) where x1≠x2 and f(x1)=f(x2).
- Conclude: we have shown there is a case where x1≠x2 and f(x1)=f(x2), therefore f is NOT one-to-one.
Example 5.3.5
Prove the function h:R→R given by h(x)=x2 is not one-to-one.
- Solution
-
Consider a=3 and b=−3. Clearly a≠b. However, h(3)=9 and h(−3)=9 so h(a)=h(b).
we have shown there is a case where a≠b and h(a)=h(b), therefore h is NOT one-to-one.
Example 5.3.6
The function f:Z→Z defined by f(n)={n2 if n is even n+12 if n is odd is not one-to-one, because, for example, f(0)=f(−1)=0. The function g:Z→Z defined by g(n)=2n is one-to-one, because if g(n1)=g(n2), then 2n1=2n2 implies that n1=n2.
hands-on exercise 5.3.4
Show that the function h:Z→N defined by h(n)={2n+1 if n≥0, −2n if n<0, is one-to-one.
Example 5.3.7
Let A be the set of all married individuals from a monogamous community who are neither divorced nor widowed. Then the function s:A→A defined by s(x)= spouse of x is one-to-one. The reason is, it is impossible to have x1≠x2 and yet s(x1)=s(x2).
Summary and Review
- A function f is said to be one-to-one if f(x1)=f(x2)⇒x1=x2.
- No two images of a one-to-one function are the same.
- Know how to write a proof to show a function is one-to-one.
- To show that a function f is not one-to-one, all we need is to find two different x-values that produce the same image; that is, find x1≠x2 such that f(x1)=f(x2).
Exercises
Exercise 5.3.1
Which of the following functions are one-to-one? Explain.
(a) f:R→R, f(x)=x3−2x2+1.
(b) g:[2,∞)→R, f(x)=x3−2x2+1.
- Solution
-
(a) No. For example, f(0)=f(2)=1
(b) Yes, since g′(x)=3x2−4x=x(3x−4)>0 for x>2.
Exercise 5.3.2
Decide if this function is one-to-one or not. Then prove your conclusion.
p:R→R, p(x)=|1−3x|.
Exercise 5.3.3
Decide if this function is one-to-one or not. Then prove your conclusion.
q:R→R, q(x)=x4.
- Solution
-
No. For example, 2≠−2, but q(2)=16 and q(−2)=16.
We have shown a case where x1≠x2 and q(x1)=q(x2), so q is NOT one-to-one.
Exercise 5.3.4
Decide if this function is one-to-one or not. Then prove your conclusion.
f:R→R, f(x)=6−5x.
Exercise 5.3.5
Determine which of the following are one-to-one functions.
- f:Z→Z; f(n)=n3+1
- g:Q→Q; g(x)=n2
- k:R→R; k(x)=5x
- Solution
-
(a) One-to-one (b) Not one-to-one (c) One-to-one
Exercise 5.3.6
Determine which of the following are one-to-one functions and explain your answer.
- p:P({1,2,3,…,n})→{0,1,2,…,n}; p(S)=|S|
- q:P({1,2,3,…,n})→P({1,2,3,…,n}); q(S)=¯S
Exercise 5.3.7
Determine which of the following functions are one-to-one.
- 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
- f2:{1,2,3,4}→{a,b,c,d,e}; f2(1)=c, f2(2)=b, f2(3)=a, f2(4)=d
- Solution
-
(a) Not one-to-one (b) One-to-one
Exercise 5.3.8
Determine which of the following functions are one-to-one.
- g1:{1,2,3,4,5}→{a,b,c,d,e}; g1(1)=b, g1(2)=b, g1(3)=b, g1(4)=a, g1(5)=d
- g2:{1,2,3,4,5}→{a,b,c,d,e}; g2(1)=d, g2(2)=b, g2(3)=e, g2(4)=a, g2(5)=c
Exercise 5.3.9
List all the one-to-one functions from {1,2} to {a,b,c,d}.
- Hint
-
List the images of each function.
- Solution
-
There are twelve one-to-one functions from {1,2} to {a,b,c,d}. The images of 1 and 2 under them are listed below. f1f2f3f4f5f6f7f8f9f10f11f121aaabbbcccddd2bcdacdabdabc
Exercise 5.3.10
Is it possible to find a one-to-one function from {1,2,3,4} to {1,2}? Explain.
Exercise 5.3.11
Determine which of the following functions are one-to-one.
- f:Z10→Z10; h(n)≡3n (mod 10).
- g:Z10→Z10; g(n)≡5n (mod 10).
- h:Z36→Z36; h(n)≡3n (mod 36).
- Solution
-
(a) One-to-one (b) Not one-to-one (c) Not one-to-one
Exercise 5.3.12
Decide if this function is one-to-one or not. Then prove your conclusion.
k:R→R defined by k(x)=3x2−5 is one-to-one.Exercise 5.3.13
Decide if this function is one-to-one or not. Then prove your conclusion.
f:R→R defined by f(x)=57 is one-to-one.
- Solution
-
No. For example, 8≠17, but f(8)=57 and f(17)=57.
We have shown a case where x1≠x2 and f(x1)=f(x2), so f is NOT one-to-one.
Exercise 5.3.14
Give an example of a one-to-one function f from N to N that is not the identity function.