Loading [MathJax]/jax/output/HTML-CSS/jax.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

6.3: Injections, Surjections, and Bijections

( \newcommand{\kernel}{\mathrm{null}\,}\)

Functions are frequently used in mathematics to define and describe certain relationships between sets and other mathematical objects. In addition, functions can be used to impose certain mathematical structures on sets. In this section, we will study special types of functions that are used to describe these relationships that are called injections and surjections. Before defining these types of functions, we will revisit what the definition of a function tells us and explore certain functions with finite domains.

Preview Activity 6.3.1: Functions with Finite Domains

Let A and B be sets. Given a function f:AB, we know the following:

  • For every xA, f(x)B. That is, every element of A is an input for the function f. This could also be stated as follows: For each xA, there exists a yB such that y=f(x).
  • For a given xA, there is exactly one yB such that y=f(x).

The definition of a function does not require that different inputs produce different outputs. That is, it is possible to have x1,x2A with x1x2 and f(x1)=f(x2). The arrow diagram for the function f in Figure 6.5 illustrates such a function.

Also, the definition of a function does not require that the range of the function must equal the codomain. The range is always a subset of the codomain, but these two sets are not required to be equal. That is, if g:AB, then it is possible to have a yB such that g(x)y for all xA. The arrow diagram for the function g in Figure 6.5 illustrates such a function.

屏幕快照 2019-03-31 下午3.37.03.png

Now let A={1,2,3}, B={a,b,c,d}, and C={s,t}. Define

屏幕快照 2019-03-31 下午3.38.25.png

  1. Which of these functions satisfy the following property for a function F?
    For all x,ydom(F), if xy, then F(x)F(y).
  2. Which of these functions satisfy the following property for a function F?
    For all x,ydom(F), if F(x)=F(y), then x=y.
  3. Determine the range of each of these functions.
  4. Which of these functions have their range equal to their codomain?
  5. Which of the these functions satisfy the following property for a function F?
    For all y in the codomain of F, there exists an xdom(F\) such that F(x)=y.
Preview Activity 6.3.1: Statements Involving Functions

Let A and B be nonempty sets and let f:AB. In Preview Activity 6.3.1, we determined whether or not certain functions satisfied some specified properties. These properties were written in the form of statements, and we will now examine these statements in more detail.

  1. Consider the following statement:
    For all x,yA, if xy, then f(x)f(y).

    (a) Write the contrapositive of this conditional statement.
    (b) Write the negation of this conditional statement.
  2. Now consider the statement:
    For all yB, there exists an xA such that f(x)=y.
    Write the negation of this statement.
  3. Let g:RR be defined by g(x)=5x+3, for all xR. Complete the following proofs of the following propositions about the function g.

    Proposition 1. For all a,bR, if g(a)=g(b), then a=b.
    Proof. We let a,bR, and we assume that g(a)=g(b) and will prove that a=b. Since g(a)=g(b), we know that
    5a+3=5b+3.
    (Now prove that in this situation, a=b.)

    Proposition 2. For all bR, there exists an aR such that g(a)=b.
    Proof. We let bR. We will prove that there exists an aR such that g(a)=b by constructing such an a in R. In order for this to happen, we need g(a)=5a+3=b.
    (Now solve the equation for a and then show that for this real number a, g(a)=b.)

Injections

In previous sections and in Preview Activity 6.3.1, we have seen examples of functions for which there exist different inputs that produce the same output. Using more formal notation, this means that there are functions f:AB for which there exist x1,x2A with x1x2 and f(x1)=f(x2). The work in the preview activities was intended to motivate the following definition.

Definition

Let f:AB be a function from the set A to the set B. The function f is called an injection provided that

for all x1,x2A, if x1x2, then f(x1)f(x2).

When f is an injection, we also say that f is a one-to-one function, or that f is an injective function.

Notice that the condition that specifies that a function f is an injection is given in the form of a conditional statement. As we shall see, in proofs, it is usually easier to use the contrapositive of this conditional statement. Although we did not define the term then, we have already written the contrapositive for the conditional statement in the definition of an injection in Part (1) of Preview Activity 6.3.2. In that preview activity, we also wrote the negation of the definition of an injection. Following is a summary of this work giving the conditions for f being an injection or not being an injection.

Let f:AB

"The function f is an injection" means that

  • for all x1,x2A, if x1x2, then f(x1)f(x2); or
  • for all x1,x2A, if f(x1)=f(x2), then x1=x2.

“The function f is not an injection” means that

  • There exist x1,x2A such that x1x2 and f(x1)=f(x2).
Progress Check 6.10 (Working with the Definition of an Injection)

Now that we have defined what it means for a function to be an injection, we can see that in Part (3) of Preview Activity 6.3.2, we proved that the function g:RR is an injection, where g(x/)=5x+3 for all xR. Use the definition (or its negation) to determine whether or not the following functions are injections.

  1. k:AB, where A={a,b,c}, B={1,2,3,4}, and k(a)=4,k(b)=1, and k(c)=3.
  2. f:AC, where A={a,b,c}, C={1,2,3}, and f(a)=2,f(b)=3, and f(c)=2.
  3. F:ZZ defined by F(m)=3m+2 for all mZ
  4. h:RR defined by h(x)=x23x for all xR
  5. s:Z5Z5 defined by sx)=x3 for all xZ5
Answer

Add texts here. Do not delete this text first.

Surjections

In previous sections and in Preview Activity 6.3.1, we have seen that there exist functions f:AB for which range(f)=B. This means that every element of B is an output of the function f for some input from the set A. Using quantifiers, this means that for every yB, there exists an xA such that f(x)=y. One of the objectives of the preview activities was to motivate the following definition.

Definition

Let f:AB be a function from the set A to the set B. The function f is called a surjection provided that the range of f equals the codomain of f. This means that

for every yB, there exists an xA such that f(x)=y.

When f is a surjection, we also say that f is an onto function or that f maps A onto B. We also say that f is a surjective function.

One of the conditions that specifies that a function f is a surjection is given in the form of a universally quantified statement, which is the primary statement used in proving a function is (or is not) a surjection. Although we did not define the term then, we have already written the negation for the statement defining a surjection in Part (2) of Preview Activity 6.3.2. We now summarize the conditions for f being a surjection or not being a surjection.

Let f:AB

"The function f is a surjection" means that

  • range(f) = codom(f)=B; or
  • For every yB, there exsits an xA such that f(x)=y.

“The function f is not a surjection” means that

  • rang(f) \ne codom(f); or
  • There exists a yB such that for all xA, f(x)y.

One other important type of function is when a function is both an injection and surjection. This type of function is called a bijection.

Definition

A bijection is a function that is both an injection and a surjection. If the function f is a bijection, we also say that f is one-to-one and onto and that f is a bijective function.

Progress Check 6.11 (Working with the Definition of a Surjection)

Now that we have defined what it means for a function to be a surjection, we can see that in Part (3) of Preview Activity 6.3.2, we proved that the function g:RR is a surjection, where g(x)=5x+3 for all xR. Determine whether or not the following functions are surjections.

  1. k:AB, where A={a,b,c}, B={1,2,3,4}, and k(a)=4,k(b)=1, and k(c)=3.
  2. f:RR defined by f(x)=3x+2 for all xR.
  3. F:ZZ defined by F(m)=3m+2 for all mZ.
  4. s:Z5Z5 defined by s(x)=x3 for all xZ5.
Answer

Add texts here. Do not delete this text first.

The Importance of the Domain and Codomain

The functions in the next two examples will illustrate why the domain and the codomain of a function are just as important as the rule defining the outputs of a function when we need to determine if the function is a surjection.

Example 6.12 (A Function that Is Neither an Injection nor a Surjection)

Let f:RR be defined by f(x)=x2+1. Notice that

f(2)=5 and f(2)=5.

This is enough to prove that the function f is not an injection since this shows that there exist two different inputs that produce the same output.

Since f(x)=x2+1, we know that f(x)1 for all xR. This implies that the function f is not a surjection. For example, -2 is in the codomain of f and f(x)2 for all x in the domain of f.

Example 6.13 (A Function that Is Not an Injection but Is a Surjection)

Let T={yR | y1}, and define F:RT by F(x)=x2+1. As in Example 6.12, the function F is not an injection since F(2)=F(2)=5.

Is the function F a surjection? That is, does F map R onto T? As in Example 6.12, we do know that F(x)1 for all xR.

To see if it is a surjection, we must determine if it is true that for every yT, there exists an xR such that F(x)=y. So we choose yT. The goal is to determine if there exists an xR such that

F(x)=y, orx2+1=y.

One way to proceed is to work backward and solve the last equation (if possible) for x. Doing so, we get

x2=y1

x=y1 or x=y1.

Now, since yT, we know that y1 and hence that y10. This means that y1R. Hence, if we use x=y1, then xR, and

F(x)=F(y1)=(y1)2+1=(y1)+1=y.

This proves that F is a surjection since we have shown that for all yT, there exists an

xR such that F(x)=y. Notice that for each yT, this was a constructive proof of the existence of an xR such that F(x)=y.

An Important Lesson.

In Examples 6.12 and 6.13, the same mathematical formula was used to determine the outputs for the functions. However, one function was not a surjection and the other one was a surjection. This illustrates the important fact that whether a function is surjective not only depends on the formula that defines the output of the function but also on the domain and codomain of the function.

The next example will show that whether or not a function is an injection also depends on the domain of the function.

Example 6.14 (A Function that Is a Injection but Is Not a Surjection)

Let Z={xZ | x0}=N{0}. Define g:ZN by g(x)=x2+1. (Notice that this is the same formula used in Examples 6.12 and 6.13.) Following is a table of values for some inputs for the function g.

屏幕快照 2019-03-31 下午4.48.49.png

Notice that the codomain is N, and the table of values suggests that some natural numbers are not outputs of this function. So it appears that the function g is not a surjection.

To prove that g is not a surjection, pick an element of N that does not appear to be in the range. We will use 3, and we will use a proof by contradiction to prove that there is no x in the domain (Z) such that g(x)=3. So we assume that there exists an xZ with g(x)=3. Then

x2+1=3x2=2x=±2.

But this is not possible since 2Z. Therefore, there is no xZ with g(x)=3. This means that for every xZ, g(x)3. Therefore, 3 is not in the range of g, and hence g is not a surjection.

The table of values suggests that different inputs produce different outputs, and hence that g is an injection. To prove that g is an injection, assume that s,tZ (the domain) with g(s)=g(t). Then

s2+1=t2+1s2=t2.

Since s,tZ, we know that s0 and t0. So the preceding equation implies that s=t. Hence, g is an injection.

An Important Lesson

The functions in the three preceding examples all used the same formula to determine the outputs. The functions in Exam- ples 6.12 and 6.13 are not injections but the function in Example 6.14 is an injection. This illustrates the important fact that whether a function is injective not only depends on the formula that defines the output of the function but also on the domain of the function.

Progress Check 6.15 (The Importance of the Domain and Codomain)

Let R+={yR | y>0}. Define

\[\begin{array} {rcl} {f} &: & {\mathbb{R} \to \mathbb{R} \text{ by } f(x) = e^{-x}, \text{ for each } x \in \mathbb{R}, \text{ and }} \\ {g} &: & {\mathbb{R} \to \mathbb{R}^{+} \text{ by } g(x) = e^{-x}, \text{ for each } x \in \mathbb{R}.}

Determine if each of these functions is an injection or a surjection. Justify your conclusions. Note: Before writing proofs, it might be helpful to draw the graph of y=ex. A reasonable graph can be obtained using 3x3 and 2y10. Please keep in mind that the graph is does not prove your conclusions, but may help you arrive at the correct conclusions, which will still need proof.

Answer

Add texts here. Do not delete this text first.

Working with a Function of Two Variables

It takes time and practice to become efficient at working with the formal definitions of injection and surjection. As we have seen, all parts of a function are important (the domain, the codomain, and the rule for determining outputs). This is especially true for functions of two variables.

For example, we define f:R×RR×R by

f(a,b)=(2a+b,ab) for all (a,b)R×R.

Notice that both the domain and the codomain of this function is the set R×R. Thus, the inputs and the outputs of this function are ordered pairs of real numbers. For example,

f(1,1)=(3,0) and f(1,2)=(0,3).

To explore wheter or not f is an injection, we assume that (a,b)R×R, (c,d)R×R, and f(a,b)=f(c,d). This means that

(2a+b,ab)=(2c+d,cd).

Since this equation is an equality of ordered pairs, we see that

2a+b=2c+d, and ab=cd.

By adding the corresponding sides of the two equations in this system, we obtain 3a=3c and hence, a=c. Substituting a=c into either equation in the system give us b=d. Since a=c and b=d, we conclude that

(a,b)=(c,d).

Hence, we have shown that if f(a,b)=f(c,d), then (a,b)=(c,d). Therefore, f is an injection.

Now, to determine if f is a surjection, we let (r,s)R×R, where (r,s) is considered to be an arbitrary element of the codomain of the function f . Can we find an ordered pair (a,b)R×R such that f(a,b)=(r,s)? Working backward, we see that in order to do this, we need

(2a+b,ab)=(r,s).

That is, we need

2a+b=r and ab=s.

Solving this system for a and b yields

a=r+s3 and b=r2s3.

Since r,sR, we can conclude that aR and bR and hence that (a,b)R×R.

We now need to verify that for. these values of a and b, we get f(a,b)=(r,s). So

f(a,b)=f(r+s3,r2s3)=(2(r+s3)+r2s3,r+s3r2s3)=(2r+2s+r2s3,r+sr+2s3)=(r,s).

This proves that for all (r,s)R×R, there exists (a,b)R×R such that f(a,b)=(r,s). Hence, the function f is a surjection. Since f is both an injection and a surjection, it is a bijection.

Progress Check 6.16 (A Function of Two Variables)

Let g:R×RR be defined by g(x,y)=2x+y, for all (x,y)R×R.

Note: Be careful! One major difference between this function and the previous example is that for the function g, the codomain is R, not R×R. It is a good idea to begin by computing several outputs for several inputs (and remember that the inputs are ordered pairs).

  1. Notice that the ordered pair (1,0)R×R. That is (1, 0) is in the domain of g. Also notice that g(1,0)=2. Is it possible to find another ordered pair (a,b)R×R such that g(a,b)=2?
  2. Let zR. Then (0,z)R×R and so (0,z)dom(g). Now determine g(0,z)?
  3. Is the function g an injection? Is the function g a surjection? Justify your conclusions.
Answer

Add texts here. Do not delete this text first.

Exercise 6.3
  1. (a) Draw an arrow diagram that represents a function that is an injection but is not a surjection.
    (b) Draw an arrow diagram that represents a function that is an injection and is a surjection.
    (c) Draw an arrow diagram that represents a function that is not an injection and is not a surjection.
    (d) Draw an arrow diagram that represents a function that is not an injection but is a surjection.
    (e) Draw an arrow diagram that represents a function that is not a bijection.
  2. Let Z5={0,1,2,3,4} and let Z6={0,1,2,3,4,5}. For each of the following functions, determine if the function is an injection and determine if the function is a surjection. Justify all conclusions.

    (a) f:Z5Z5 by f(x)=x2+4 (mod 5), for all xZ5
    (b) g:Z6Z6 by g(x)=x2+4 (mod 6), for all xZ6
    (c) F:Z5Z5 by F(x)=x3+4 (mod 5), for all xZ5
  3. For each of the following functions, determine if the function is an injection and determine if the function is a surjection. Justify all conclusions.

    (a) f:ZZ defined by f(x)=3x+1, for all xZ.
    (b) F:QQ defined by F(x)=3x+1, for all xQ.
    (c) g:RR defined by g(x)=x3, for all xR.
    (d) G:QQ defined by G(x)=x3, for all xQ.
    (e) k:RR defined by k(x)=ex2, for all xR.
    (f) K:RR defined by K(x)=ex2, for all xR.
    Note: R={xR | x0}.
    (g) K1:RT defined by K1(x)=ex2, for all xR, where T={yR | 0<y1}.
    (h) h:RR defined by h(x)=2xx2+4, for all xR.
    (i) H:{xR | x0}{yR | 0y12} defined by H(x)=2xx2+4, for all x{xR | x0}.
  4. For each of the following functions, determine if the function is a bijection. Justify all conclusions.

    (a) F:RR defined by F(x)=5x+3, for all xR.
    (b) G:ZZ defined by G(x)=5x+3, for all xZ.
    (c) f:(R{4})R defined by f(x)=3xx4, for all x(R{4}).
    (d) g:(R{4})(R{3}) defined by g(x)=3xx4, for all x(R{4}).
  5. Let s:NN, where for each nN, s(n) is the sum of the distinct natural number divisors of n. This is the sum of the divisors function that was introduced in Preview Activity 6.3.2 from Section 6.1. Is s an injection? Is s a surjection? Justify your conclusions.
  6. Let d:NN, where d(n) is the number of natural number divisors of n. This is the number of divisors function introduced in Exercise (6) from Section 6.1. Is the function d an injection? Is the function d a surjection? Justify your conclusions.
  7. In Preview Activity 6.3.2 from Section 6.1 , we introduced the birthday function. Is the birthday function an injection? Is it a surjection? Justify your conclusions.
  8. (a) Let f:Z×ZZ be defined by f(m,n)=2m+n. Is the function f an injection? Is the function f a surjection? Justify your conclusions.
    (b) Let g:Z×ZZ be defined by g(m,n)=6m+3n. Is the function g an injection? Is the function g a surjection? Justify your conclusions.
  9. (a) Let f:R×RR×R be defined by f(x,y)=(2x,x+y). Is the function f an injection? Is the function f a surjection? Justify your conclusions.
    (b) Let g:Z×ZZ×Z be defined by g(x,y)=(2x,x+y). Is the function g an injection? Is the function g a surjection? Justify your conclusions.
  10. Let f:R×RR be the function defined by f(x,y)=x2y+3y, for all (x,y)R×R. Is the function f and injection? Is the function f a surjection? Justify your conclusions.
  11. Let g:R×RR be the function defined by g(x,y)=(x3+2)siny, for all (x,y)R×R. Is the function g and injection? Is the function g a surjection? Justify your conclusions.
  12. Let A be a nonempty set. The identity function on the set A, denoted by IA, is the function IA:AA defined by IA(x)=x for every x in A. Is IA an injection? Is IA a surjection? Justify your conclusions.
  13. Let A and B be two nonempty sets. Define
    p1:A×BA by p1(a,b)=a
    for every (a,b)A×B. That is the first projection function introduced in Exercise (5) in Section 6.2.
    (a) Is the function p1 a surjection? Justify your conclusion.
    (b) If B={b}, is the function p1 an injection? Justify your conclusion.
    (c) Under what condition(s) is the function p1 not an injection? Make a conjecture and prove it.
  14. Define f:NZ be defined as follows: For each nN,
    f(n)=1+(1)n(2n1)4.
    Is the function f an injection? Is the function f a surjection? Justify your conclusions.

    Suggestions. Start by calculating several outputs for the function before you attempt to write a proof. In exploring whether or not the function is an injection, it might be a good idea to uses cases based on whether the inputs are even or odd. In exploring whether f is a surjection, consider using cases based on whether the output is positive or less than or equal to zero.
  15. Let C be the set of all real functions that are continuous on the closed interval [0, 1]. Define the function A:CR as follows: For each fC.
    A(f)=10f(x)dx.
    Is the function A an injection? Is it a surjection? Justify your conclusions.
  16. Let A={(m,n) | mZ,nZ, and n0}. Define f:AQ as follows:
    For each (m,n)A, f(m,n)=m+nn.
    (a) Is the function f an injection? Justify your conclusion.
    (b) Is the function f a surjection? Justify your conclusion.
  17. Evaluation of proofs
    See the instructions for Exercise (19) on page 100 from Section 3.1.
    (a)

    Proposition. The function f:R×RR×R defined by f(x,y)=(2x+y,xy) is an injection.

    Proof

    For each (a,b) and (c,d) in R×R, if f(a,b)=f(c,d), then

    (2a+b,ab)=(2c+d,cd).

    We will use systems of equations to prove that a=c and b=d.

    2a+b=2c+dab=cd3a=3ca=c

    Since a=c, we see that

    (2c+b,cb)=(2c+d,cd).

    So b=d. Therefore, we have proved that the function f is an injection.

    (b)

    Proposition. The function f:R×RR×R defined by f(x,y)=(2x+y,xy) is an surjection.

    Proof

    We need to find an ordered pair such that f(x,y)=(a,b) for each (a,b) in R×R. That is, we need (2x+y,xy)=(a,b), or

    2x+y=a and xy=b.

    Treating these two equations as a system of equations and solving for x and y, we find that

    x=a+b3 and y=a2b3.

    Hence, x and y are real numbers, (x,y)R×R, and

    f(x,y)=f(a+b3,a2b3)=(2(a+b3)+a2b3,a+b3a2b3)=(2a+2b+a2b3,a+ba+2b3)=(3a3,3b3)=(a,b).

    Therefore, we. have proved that for every (a,b)R×R, there exists an (x,y)R×R such that f(x,y)=(a,b). This proves that the function f is a surjection.

    Explorations and Activities

  18. Piecewise Defined Functions. We often say that a function is a piecewise defined function if it has different rules for determining the output for different parts of its domain. For example, we can define a function f:RR by giving a rule for calculating f(x) when x0 and giving a rule for calculating f(x) when x < 0 as follows:
    f(x)={x2+1, if x  0;x1 if x < 0.
    (a) Sketch a graph of the function f. Is the function f and injection? Is the function f a surjection? Justify your conclusions.

    For each of the following functions, determine if the function is an injection and determine if the function is a surjection. Justify all conclusions.

    (b) g:[0,1](0,1) by
    g(x)={0.8, if x=0;0.5x if 0<x<1;0.6 if x=1.
    (c) h:Z{0,1} by
    h(x)={0, if x is even;1, if x is odd.
  19. Functions Whose Domain is M2(R). Let M2(R). represent the set of all 2 by 2 matrices over R.

    (a) Defien det: M2(R)R by
    det[abcd]=adbc.
    This is the determinant function introduced in Exercise (9) from Section 6.2. Is the determinant function an injection? Is the determinant function a surjection? Justify your conclusions.

    (b) Define tran: M2(R)M2(R) by
    tran[abcd]=AT=[acbd].
    This is the transpose function introduced in Exercise (10) from Section 6.2. Is the transpose function an injection? Is the transpose function a surjection? Justify your conclusions.

    (c) Define F:M2(R)R by
    F[abcd]=a2+d2b2c2.
    Is the function F an injection? Is the function F a surjection? Justify your conclusions.
Answer

Add texts here. Do not delete this text first.


This page titled 6.3: Injections, Surjections, and Bijections is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by Ted Sundstrom (ScholarWorks @Grand Valley State University) via source content that was edited to the style and standards of the LibreTexts platform.

Support Center

How can we help?