Advanced Lecture Notes on Functions Part 4:

Surjective (Onto) & Bijective Functions

For the Serious Aspirant

Contents

1 Recap: Injectivity and Fibers 1

2 Surjective (Onto) Functions 1

2.1 Proving Surjectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
2.2 Graphical Interpretation of Surjectivity . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.3 Surjectivity and Compositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2.4 Number of Surjective Functions (Principle of Inclusion-Exclusion) . . . . . . . . . . . 3

3 Bijective Functions (One-to-One Correspondences) 4

3.1 Properties of Bijections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

4 Problems for the Adept: Part 4 5

5 Answer Key (Part 4) 7

Part 4: Surjective & Bijective Functions Advanced Functions by Yuki

1 Recap: Injectivity and Fibers

In Part 3, we defined an injective (one-to-one) function f : X → Y as one where distinct elements
in X map to distinct elements in Y , or equivalently, f (x1 ) = f (x2 ) =⇒ x1 = x2 . We established
that f is injective if and only if every fiber f −1 ({y}) contains at most one element. We now turn to
surjectivity, which concerns whether every element in the codomain is ”hit” by the function.

2 Surjective (Onto) Functions

Definition 2.1. Surjective Function

A function f : X → Y is said to be surjective (or onto) if its range is equal to its codomain.
That is, Ran(f ) = Y . Equivalently, f is surjective if for every element y ∈ Y , there exists at
least one element x ∈ X such that f (x) = y.

∀y ∈ Y, ∃x ∈ X such that f (x) = y

Remark 2.1. Connection to Fibers

A function f : X → Y is surjective if and only if every fiber f −1 ({y}) for y ∈ Y is non-empty.
If there were some y0 ∈ Y for which f −1 ({y0 }) = ∅, it would mean no x ∈ X maps to y0 , so
y0 ∈/ Ran(f ), and thus f would not be surjective.

2.1 Proving Surjectivity

Example 2.1. Linear Function (Revisited)

Let f : R → R be defined by f (x) = 3x + 5. Is f surjective?

Proof
Let y ∈ R be an arbitrary element in the codomain. We need to find an x ∈ R (the
domain) such that f (x) = y. Set 3x + 5 = y. Solving for x, we get 3x = y − 5, so
x = y−5
3
. Since y ∈ R, y − 5 is also a real number, and y−5
3
is a well-defined real number.
Thus, for any y ∈ R, we found an x = 3 ∈ R such that f (x) = y. Therefore, f is
y−5

surjective.

Example 2.2. Quadratic Function (Revisited)

Let f : R → R be defined by f (x) = x2 . Is f surjective?

Proof
The codomain is R. The range of f (x) = x2 is [0, ∞). Since Ran(f ) = [0, ∞) ̸= R (the
codomain), the function is not surjective. For example, let y = −1 ∈ R (the codomain).
There is no x ∈ R such that x2 = −1. So the fiber f −1 ({−1}) is empty.

1
Part 4: Surjective & Bijective Functions Advanced Functions by Yuki

Remark 2.2. Codomain Matters!

If we change the codomain for f (x) = x2 to Y = [0, ∞), defining g : R → [0, ∞) by g(x) = x2 .
Now, the codomain is [0, ∞). The range is also [0, ∞). Since Range = Codomain, this function g
is surjective. This highlights that surjectivity depends critically on how the codomain is specified.

2.2 Graphical Interpretation of Surjectivity

For a function f : X → Y (where X, Y ⊆ R), f is surjective if every horizontal line y = c where
c ∈ Y (the codomain) intersects the graph of y = f (x) at least once. If there is any horizontal line
within the specified codomain that does not intersect the graph, the function is not surjective.

2.3 Surjectivity and Compositions

Theorem 2.1. Composition of Surjective Functions
If f : X → Y and g : Y → Z are both surjective functions, then their composition g◦f : X → Z
is also surjective.

Proof
Let z ∈ Z be an arbitrary element in the codomain of g ◦ f . We need to find an x ∈ X such
that (g ◦ f )(x) = z. Since g : Y → Z is surjective, for this z ∈ Z, there exists a y ∈ Y such
that g(y) = z. Since f : X → Y is surjective, for this y ∈ Y , there exists an x ∈ X such that
f (x) = y. Now, consider (g ◦ f )(x) = g(f (x)). Since f (x) = y, we have g(f (x)) = g(y). And
since g(y) = z, we have (g ◦ f )(x) = z. We have found an x ∈ X that maps to z under g ◦ f .
Therefore, g ◦ f is surjective.

Theorem 2.2. Surjectivity of Composite Implies Surjectivity of Outer Function

If g ◦ f : X → Z is surjective, then g : Y → Z must be surjective. (Note: f need not be

surjective).

Proof
Assume g ◦ f : X → Z is surjective. We want to show g : Y → Z is surjective. Let z ∈ Z
be an arbitrary element. We need to find some y0 ∈ Y such that g(y0 ) = z. Since g ◦ f is
surjective, for this z ∈ Z, there exists an x0 ∈ X such that (g ◦ f )(x0 ) = z. This means
g(f (x0 )) = z. Let y0 = f (x0 ). Since x0 ∈ X and f : X → Y , y0 is an element of Y . And we
have g(y0 ) = g(f (x0 )) = z. So, for an arbitrary z ∈ Z, we found y0 = f (x0 ) ∈ Y such that
g(y0 ) = z. Therefore, g is surjective.
Counterexample to show f need not be surjective (Yuki’s Insight): Let X = {1},
Y = {a, b}, Z = {p}. Let f : X → Y be f (1) = a. f is not surjective (since b ∈ Y is not
in the range). Let g : Y → Z be g(a) = p, g(b) = p. g is surjective (every element p ∈ Z is
hit). Then g ◦ f : X → Z is (g ◦ f )(1) = g(f (1)) = g(a) = p. The range of g ◦ f is {p},
which is equal to the codomain Z = {p}. So g ◦ f is surjective. Here g ◦ f is surjective and g
is surjective, but f is not.

2
Part 4: Surjective & Bijective Functions Advanced Functions by Yuki

2.4 Number of Surjective Functions (Principle of Inclusion-Exclusion)

Counting surjective functions is more complex than counting injective ones and requires the Principle
of Inclusion-Exclusion.

Theorem 2.3. Counting Surjective Functions

Let A and B be finite sets with |A| = m and |B| = n. The number of surjective functions from
A to B (where m ≥ n) is:
∑n ( )
k n
(−1) (n − k)m
k=0
k
This is also written as n!S(m, n), where S(m, n) are Stirling numbers of the second kind. If
m < n, the number of surjective functions is 0.

Proof Sketch using Inclusion-Exclusion

Let Stotal be the set of all nm functions from A to B. We want to subtract functions that are
*not* surjective. A function is not surjective if its range misses at least one element of B. Let
B = {b1 , b2 , . . . , bn }. Let Pi be the property that the element bi ∈ B is *not* in the range of
the function. We want to count functions that have none of these properties. The number of
functions whose range does not contain bi is (n −(1))m (each of the m elements in A can map
to the remaining n − 1 elements in B). There are n1 ways to choose such a bi . The number (n) of
functions whose range does not contain bi and bj (i.e., Pi ∩ Pj ) is (n − 2) . There are 2 ways
m

to choose such a pair bi , bj . By the Principle of Inclusion-Exclusion, the number of functions

that have at least one of the properties Pi (i.e., are not surjective) is:
( ) ( ) ( ) ( )
n n n n−1 n
Nnot surjective = (n − 1) −
m
(n − 2) +
m
(n − 3) − · · · + (−1)
m
(n − n)m
1 2 3 n

The total number of surjective functions is Ntotal − Nnot surjective :

[( ) ( ) ( ) ]
n n n−1 n
Nsurj = n −
m
(n − 1) −
m
(n − 2) + · · · + (−1)
m
(n − n) m
1 2 n
( ) ( ) ( ) ( )
n n n n n
Nsurj = (n − 0) −m
(n − 1) +
m
(n − 2) − · · · + (−1)
m
(n − n)m
0 1 2 n
∑ n ( )
n
Nsurj = (−1)k (n − k)m
k=0
k

Note: (n − n)m = 0m . If m > 0, 0m = 0. If m = 0 (function from ∅), then 00 is usually taken

as 1 in this combinatorial context if n = 0 also (empty function to empty set). For m ≥ n > 0,
the last term for k = n correctly contributes zero to the sum.

Example 2.3. Counting Surjections

Number of surjective
∑ functions( from
) A = {1, 2, 3}( (m
) = 3) to B = ({a, ) b} (n = 2). Using( ) the
formula: Nsurj = 2k=0 (−1)k k2 (2−k)3 = (−1)0 20 (2−0)3 +(−1)1 21 (2−1)3 +(−1)2 22 (2−
2)3 = (1)(1)(23 ) − (1)(2)(13 ) + (1)(1)(03 ) (Corrected (−1)1 coefficient) = 1 · 8 − 2 · 1 + 1 · 0 =
8 − 2 + 0 = 6. Total functions are 23 = 8. The only non-surjective ones are f (x) = a∀x and
f (x) = b∀x. There are 2 such functions. So 8 − 2 = 6.

3
Part 4: Surjective & Bijective Functions Advanced Functions by Yuki

3 Bijective Functions (One-to-One Correspondences)

A function that is both injective and surjective holds a special place in mathematics.

Definition 3.1. Bijective Function

A function f : X → Y is said to be bijective if it is both injective and surjective. A bijective
function is also called a one-to-one correspondence.

This means:

• Every element in Y has at least one element from X mapping to it (surjective).

• No element in Y has more than one element from X mapping to it (injective, when considering
elements in the range).

Combining these, for a bijection f : X → Y , every element y ∈ Y has exactly one x ∈ X such that
f (x) = y. In terms of fibers: f is bijective if and only if every fiber f −1 ({y}) for y ∈ Y contains
exactly one element.

Example 3.1. Linear Function as a Bijection

f : R → R by f (x) = 3x + 5. We showed it’s injective and surjective. Thus, it’s bijective.

Example 3.2. f (x) = x3 as a Bijection

f : R → R by f (x) = x3 . Injectivity: x31 = x32 =⇒ x1 = x2 . (Injective) Surjectivity: For any

√ √
y ∈ R, let x = 3 y. Then x ∈ R and f (x) = ( 3 y)3 = y. (Surjective) Thus, f (x) = x3 is a
bijection from R to R.

3.1 Properties of Bijections

Theorem 3.1. Composition of Bijections
If f : X → Y and g : Y → Z are both bijective functions, then their composition g ◦f : X → Z
is also bijective.

Proof
Since f, g are injective, g ◦ f is injective (from Part 3, Theorem on composition of injective
functions). Since f, g are surjective, g ◦ f is surjective (Theorem 4.2.1). Since g ◦ f is both
injective and surjective, it is bijective.

Theorem 3.2. Existence of Inverse Function

A function f : X → Y is bijective if and only if it has an inverse function f −1 : Y → X. This
inverse function f −1 is also bijective. (This will be the central topic of Part 5).

4
Part 4: Surjective & Bijective Functions Advanced Functions by Yuki

Theorem 3.3. Cardinality and Bijections

For finite sets X and Y , a bijective function f : X → Y can exist if and only if |X| = |Y |. The
number of bijective functions from a set A with n elements to a set B with n elements is n!. (This
follows from the count for injective functions where m = n: P (n, n) = n!/(n−n)! = n!/0! = n!,
as 0! = 1).

For the Curious

Infinite Sets and Cardinality (Yuki’s Perspective) The concept of bijection is crucial for comparing
the ”sizes” of infinite sets. Two sets (finite or infinite) are said to have the same cardinality if
there exists a bijection between them.

• Georg Cantor showed that there is a bijection between N (natural numbers) and Z (inte-
gers), meaning they have the same cardinality (denoted ℵ0 , aleph-null). This is surprising
as N is a proper subset of Z.

• He also showed a bijection exists between N and Q (rational numbers). So |N| = |Z| =
|Q| = ℵ0 .

• However, Cantor famously proved that there is no bijection between N and R (real num-
bers). The cardinality of R (denoted c, for continuum) is strictly greater than ℵ0 . This is
proven using Cantor’s diagonal argument.

• Cantor’s Theorem (revisited): For any set A, there is no surjection from A to its power
set P(A). This implies there’s no bijection, so |A| < |P(A)|.

These ideas form the bedrock of transfinite arithmetic.

4 Problems for the Adept: Part 4

Problem 4.1. prob:P4.1

Determine if f : R → R defined by f (x) = ex − e−x is surjective and/or bijective.

Problem 4.2. prob:P4.2

x2
Let f : R → A where f (x) = 1+x2
. If f is surjective, what is the set A? Is f injective?

Problem 4.3. prob:P4.3

Let A = {1, 2, 3} and B = {a, b}. How many surjective functions are there from A to B? List
them.

Problem 4.4. prob:P4.4

Let f : X → Y and g : Y → X be two functions such that g ◦ f = IX (identity on X) and

f ◦ g = IY (identity on Y ). Prove that f (and g) must be bijective. (This shows g is the unique
inverse of f ).

5
Part 4: Surjective & Bijective Functions Advanced Functions by Yuki

Problem 4.5. prob:P4.5

Consider f : Z → Z defined by f (n) = 2n.

(a) Is f injective?

(b) Is f surjective?

(c) Is f bijective?

Now consider g : Q → Q defined by g(q) = 2q. Answer the same questions for g.

Problem 4.6. prob:P4.6

If f : A → B is injective and g : B → C is surjective. Can g ◦ f be bijective? What conditions
are needed for g ◦ f to be bijective?

6
Part 4: Surjective & Bijective Functions Advanced Functions by Yuki

5 Answer Key (Part 4)

Solutions (Part 4)

1. Problem 4.1: f (x) = ex − e−x . In Part 3, Problem 3.6, we showed f ′ (x) = ex + e−x > 0
for all x, so f is strictly increasing and thus injective. For surjectivity: We need to check
if the range of f is R. As x → ∞, ex → ∞ and e−x → 0, so f (x) → ∞. As x → −∞,
let x = −t where t → ∞. f (x) = e−t − et . As t → ∞, e−t → 0 and et → ∞, so
f (x) → −∞. Since f (x) is continuous (sum/difference of continuous functions) and its
limits at ±∞ are ±∞ respectively, by the Intermediate Value Theorem, its range is R.
Since Range = Codomain (R), f is surjective. Since f is both injective and surjective, it
is bijective.
x 2 x 2
2. Problem 4.2: f (x) = 1+x 2 . For surjectivity, A must be the range of f (x). Let y = 1+x2 .
x2
Since x2 ≥ 0, we have 1 + x2 > 0. Also, x2 < 1 + x2 (for x ∈ R), so y = 1+x 2 < 1.
x2
And y = 1+x2 ≥ 0 (equality holds when x = 0). To find the limit as x → ±∞:
x2
2 +1) = 1/x2 +1 . As x → ±∞, 1/x → 0, so y → 0+1
1 2 1
y = x2 (1/x = 1. Since f (x) is
continuous, f (0) = 0, and f (x) → 1 as x → ±∞, and f (x) ≥ 0, the range is [0, 1).
For f to be surjective, the codomain A must be equal to the range. So, A = [0, 1).
(−1)2 12
2 = 2 . f (1) = 1+12 = 2 . Since f (−1) = f (1) but −1 ̸= 1, f
1 1
Injectivity: f (−1) = 1+(−1)
is not injective on R.
3. Problem 4.3: ∑ A = {1, ) 3} (m = 3), B( )= {a, b} (n = 2).
( 2, ( ) Number of surjective
()
functions = 2k=0 (−1)k k2 (2−k)3 = (−1)0 20 (2−0)3 +(−1)1 21 (2−1)3 +(−1)2 22 (2−
2)3 = (1)(1)(23 ) − (2)(13 ) + (1)(03 ) = 8 − 2 + 0 = 6. The 6 surjective functions are:
(Each element of A maps to a or b, such that both a and b are images). This means
either two elements map to one of {a, b} and one maps to the other, or vice-versa.
• To a, a, b: {(1, a), (2, a), (3, b)}, {(1, a), (2, b), (3, a)}, {(1, b), (2, a), (3, a)} (3
ways)
• To b, b, a: {(1, b), (2, b), (3, a)}, {(1, b), (2, a), (3, b)}, {(1, a), (2, b), (3, b)} (3 ways)
Total = 6.
4. Problem 4.4: Given g ◦ f = IX and f ◦ g = IY . From g ◦ f = IX : Since IX is injective
(as IX (x1 ) = IX (x2 ) =⇒ x1 = x2 ), f must be injective (by Theorem 3.3.2). Since
IX is surjective (as for any x ∈ X, IX (x) = x, its range is X), g must be surjective (by
Theorem 4.2.2). From f ◦ g = IY : Since IY is injective, g must be injective. Since IY is
surjective, f must be surjective. So, f is injective and surjective =⇒ f is bijective. And
g is injective and surjective =⇒ g is bijective. (And g = f −1 ).
5. Problem 4.5 (Yuki’s Challenge): (a) f : Z → Z, f (n) = 2n. Injectivity: f (n1 ) =
f (n2 ) =⇒ 2n1 = 2n2 =⇒ n1 = n2 . Yes, f is injective. Surjectivity: Codomain is
Z. Range is the set of all even integers. The range is not equal to Z (e.g., 3 ∈ Z but 3
is not in the range). No, f is not surjective. Bijectivity: Since not surjective, No, f is
not bijective.
(b) g : Q → Q, g(q) = 2q. Injectivity: g(q1 ) = g(q2 ) =⇒ 2q1 = 2q2 =⇒ q1 = q2 .
Yes, g is injective. Surjectivity: Codomain is Q. Let y ∈ Q be arbitrary. We need to
find q ∈ Q such that g(q) = y. Set 2q = y =⇒ q = y/2. If y is rational, then y/2 is
also rational. So q ∈ Q exists for every y ∈ Q. Yes, g is surjective. Bijectivity: Since
injective and surjective, Yes, g is bijective.

7
Part 4: Surjective & Bijective Functions Advanced Functions by Yuki

6. Problem 4.6: f : A → B injective, g : B → C surjective. Can g ◦ f : A → C be

bijective? For g ◦ f to be bijective, it must be injective and surjective.

• Injectivity of g ◦ f : We know f is injective. For g ◦ f to be injective, we additionally

need g to be injective when restricted to the range of f , i.e., g|Ran(f ) must be
injective. If g itself is injective, this condition is met.
• Surjectivity of g ◦ f : We know g is surjective. For g ◦ f to be surjective, we need
g(Ran(f )) = C. Since g is surjective from B to C, if Ran(f ) = B (i.e., f is
surjective), then g(Ran(f )) = g(B) = C, so g ◦ f would be surjective.

So, g ◦ f is bijective if: 1. f is bijective (injective and surjective from A to B). 2. g

is bijective (injective and surjective from B to C). If f is only injective (not necessarily
surjective) and g is only surjective (not necessarily injective), then g ◦ f is not necessarily
bijective. Conditions needed for g ◦ f to be bijective: (1) f must be injective (given). (2)
g must be injective on the range of f . (3) The range of f must be such that when g is
applied to it, all of C is covered. This means g(Ran(f )) = C. The simplest sufficient
conditions are that both f and g are bijective. Consider A = {1}, B = {x, y}, C = {p}.
f : A → B as f (1) = x. (Injective, but not surjective if y is in B and not hit).
g : B → C as g(x) = p, g(y) = p. (Surjective, but not injective). g ◦ f : A → C
is g(f (1)) = g(x) = p. This is injective and surjective (hence bijective). Here f was
injective, g was surjective. g was not injective on B, but g|Ran(f ) (i.e., g on {x}) was
injective. And g(Ran(f )) = g({x}) = {p} = C. So the minimal conditions are: (i) f is
injective, (ii) g|Ran(f ) is injective, and (iii) g(Ran(f )) = C.