Queen’s University
School of Computing
CISC 203: Discrete Mathematics for Computing II
Module 6: Functions
Fall 2021
This module corresponds to the following sections from your textbook:
24. Functions
25. The Pigeonhole Principle
26. Composition
27. Permutations
1 Functions
Definition 1 (Function). A relation f : A −→ B is called a function if (a, b) ∈ f and (a, c) ∈ f implies
b = c.
Intuitively, a function is a “machine” that transforms one quantity into another, but each input quantity can
not have more than one output quantity.
Example 2. Let
f = {(1, 2), (2, 3), (3, 1), (4, 7)} and g = {(1, 2), (1, 3), (4, 7)}.
The relation f is a function but the relation g is not a function because (1, 2), (1, 3) ∈ g and 2 6= 3.
If f is a function whose output value is y when the input is x, we write f(x) = y. We say that f maps x to
y.
For example, we can can express function f(x) = x2 on the integers as a set of ordered pairs, as
f = {. . . , (−3, 9), (−2, 4), (−1, 1), (0, 0), (1, 1), (2, 4), (3, 9), . . .}.
We can also express it in set-builder notation as
f = {(x, y) : x, y ∈ Z, y = x2}.
As another example, the absolute value function abs takes an integer x as input and returns x if x is positive
and returns −x if x is negative, i.e.,
f(x) = abs(x) = |x| =
{
x if x ≥ 0
−x if x < 0.
Similarly, abs can also be expressed as a set of ordered pairs, or in set-builder notation as
f = {(x, y) : x, y ∈ Z, y = |x|}.
Definition 3 (Domain and Image). The domain of a relation or function g is the set of all the first
elements of the ordered pairs in g. We denote this as
dom g = {a ∈ A : ∃b ∈ B, (a, b) ∈ g},
CISC 203: Discrete Mathematics for Computing II
Module 6, Fall 2021 Page 2
or alternatively,
dom g = {a ∈ A : g(a) is defined}.
The image of a relation or function g is the set of all the second elements of the ordered pairs in g. We
denote this as
im g = {b ∈ B : ∃a ∈ A, (a, b) ∈ g},
or alternatively,
im g = {b ∈ B : b = g(a) for some a}.
Definition 4 (f : A −→ B). A function from set A to set B, denoted
f : A −→ B,
is a rule that assigns to each element a ∈ A a unique element f(a) ∈ B.
The domain of f is the set A, i.e., dom f = A. In other words, for every element a ∈ A there is a pair (a, b)
in f .
The image of f is a subset of B, i.e., im f ⊆ B.
In the abs function above, the argument of the function is an integer and the value is a non-negative integer
so we may write abs : Z −→ N.
Definition 5 (One-to-one, Onto, Bijection). Consider a function f : A −→ B.
• The function f is called one-to-one (or injective) if whenever (a1, b), (a2, b) ∈ f, we must have a1 =
a2. In other words, if a1 6= a2, then f(a1) 6= f(a2).
• The function f is called onto B (or surjective) if for every b ∈ B, there exists an a ∈ A such that
f(a) = b.
• The function f is a bijection if it is both one-to-one and onto.
Exercise
Let A = {1, 2} and B = {3, 4}. Write down all functions f : A −→ B. Indicate which are one-to-one
and which are onto B.
To prove that a function is one-to-one, it must be shown that when f(a1) = f(a2), we have a1 = a2. This
can also be done by contrapositive or by contradiction (see Proof Template 20, p. 172).
To prove that a function f : A −→ B is onto B, show that for every element b ∈ B there must be an element
a ∈ A such that f(a) = b. Alternatively, show that the set B is equal to im f (see Proof Template 21, p. 173).
Example 6. Let A be the set of even integers and B be the set of odd integers. The function f : A −→ B
defined by f(x) = x+ 1 is a bijection.
Proof. We must prove that f is both one-to-one and onto.
To show that f is one-to-one, suppose f(a1) = f(a2), where a1 and a2 are even integers:
f(a1) = f(a2) =⇒ a1 + 1 = a2 + 1 =⇒ a1 = a2
So, f is one-to-one.
To show that f is onto B, let b be any element from B (i.e., an odd integer). By definition, b = 2k + 1 for
some integer k. Let a = 2k; since a is clearly even, we have a ∈ A. Then, f(a) = a+ 1 = 2k + 1 = b. So, f
is onto.
Since f is both one-to-one and onto, it is a bijection.
CISC 203: Discrete Mathematics for Computing II
Module 6, Fall 2021 Page 3
Example 7. The function f : Z −→ Z defined by f(x) = x2 is not one-to-one and not onto Z.
Proof. f(3) = f(−3) = 9, but 3 6= −3, so f is not one-to-one.
It is not onto Z either, since f(x) can never be a negative integer, so im f 6= Z.
Example 8. The function f : R −→ Z defined by the floor function f(x) = bxc is onto Z but not one-to-one.
Proof. To show that f is onto Z, let b be any integer. We take a = b, which is clearly in R. Then,
f(a) = bac = bbc = b. So, f is onto.
f(3.1) = f(3.3) = 3, but 3.1 6= 3.3, so f is not one-to-one.
Exercise
Show that the function f : Z −→ Z defined by f(x) = 2x is one-to-one but not onto.
1.1 Inverse functions
Any relation R ⊆ A × B has a unique inverse relation R−1 ⊆ B × A. However, the inverse relation of a
function f need not be a function, as shown in the following counterexample.
Example 9. Let A = {0, 1, 2, 3, 4} and B = {5, 6, 7, 8, 9}. Let f : A→ B be defined by
f = {(0, 5), (1, 7), (2, 8), (3, 9), (4, 7)},
so
f−1 = {(5, 0), (7, 1), (8, 2), (9, 3), (7, 4)}.
f−1 is not a function from B to A, for two reasons:
1. f−1 is not a function, since (7, 1) and (7, 4) are in f−1. This violates Definition 1.
2. dom f−1 6= B. This violates Definition 4. See Example 24.12 in the textbook for an illustration.
Theorem 10. Let A and B be sets and let f : A→ B. The inverse relation f−1 is a function from B to A
if and only if f is one-to-one and onto.
Note that if f is one-to-one, but not onto, the inverse relation f−1 is still a function, but dom f−1 (which
is equal to im f) will be a proper subset of B (and thus f−1 would not be a function from B to A, by
Definition 4).
2 The Pigeonhole Principle
The Pigeonhole Principle states that: If n pigeons are put into m holes, where n > m, then at least one
hole will contain more than one pigeon. To illustrate, suppose there are nine holes in a pigeon coop, and ten
pigeons fly to the coop to roost. If each of the ten pigeons is in a hole, then it must be the case that at least
one hole contains more than one pigeon.
The following two propositions follow from the Pigeonhole Principle.
Proposition 11. For a function f : A −→ B where A and B are finite sets:
i. if |A| > |B|, then f is not one-to-one; and
CISC 203: Discrete Mathematics for Computing II
Module 6, Fall 2021 Page 4
ii. if |A| < |B|, then f is not onto.
We illustrate this with two examples.
Example 12. Let A = {1, 2, 3} and B = {4, 5}. Since |A| > |B|, there is no function f : A −→ B that is
one-to-one.
Let A = {1, 2} and B = {3, 4, 5}. Since |B| > |A|, there is no function f : A −→ B that is onto.
The next proposition follows from the above proposition.
Proposition 13. Let A and B be finite sets and let f : A −→ B. If f is a bijection, then |A| = |B|.
Exercise
Let A = {1, 2, 3} and B = {4, 5}. Give a function f : A −→ B that is onto.
Let A = {1, 2} and B = {3, 4, 5}. Give a function f : A −→ B that is one-to-one.
The following is a generalized version of the Pigeonhole Principle.
Proposition 14. If n elements are partitioned into m subsets, then at least one subset must contain dn/me
or more elements.
Proof. Suppose we have n elements partitioned into m subsets. For the sake of contradiction, suppose that
no subset contains more than dn/me − 1 elements. Then the total number of elements is at most
m
(⌈ n
m
⌉
− 1
)
< m
(( n
m
+ 1
)
− 1
)
= n.
Thus, we must have fewer than n elements. However, we assumed we had exactly n elements. Therefore,
our assumption was incorrect and at least one subset must contain at least dn/me elements. �
Example 15. In the 2017–2018 academic year, there were 11 783 students enrolled in the Faculty of Arts
and Science at Queen’s University. Assume that each of these students was born in the same four-year period
of 1996–1999. The given four-year period consisted of 1 461 days. Therefore, by the pigeonhole principle, at
least d11 783/1 461e = 9 students in the Faculty of Arts and Science were born on the same day.
Note that Proposition 11 and Proposition 13 are meaningful only for finite sets. For example, consider the
set A of all positive integers {1, 2, 3, . . .} and the set B of all nonnegative integers {0, 1, 2, 3, . . .}. But the
function f : A −→ B defined by f(x) = x − 1 is a bijection, even though A is a proper subset of B. Refer
to p. 180 of your textbook for another bijection from N to Z.
3 Composition
The composition of functions f : A −→ B and g : B −→ C is the function g ◦ f : A→ C defined by
(g ◦ f)(a) = g(f(a)) for every a ∈ A.
Note that the composition is defined only if the image of f equals the domain of g.
When dealing with a function composition g ◦ f it is important to remember that the function f is applied
first, and then apply function g to the resulting value.
Example 16. Let A = {1, 2, 3, 4, 5}, B = {6, 7, 8, 9}, and C = {10, 11, 12, 13, 14}. Let f : A −→ B and
g : B −→ C be defined by
f = {(1, 6), (2, 6), (3, 9), (4, 7), (5, 7)}
CISC 203: Discrete Mathematics for Computing II
Module 6, Fall 2021 Page 5
and
g = {(6, 10), (7, 11), (8, 12), (9, 13)}.
Then
(g ◦ f) = {(1, 10), (2, 10), (3, 13), (4, 11), (5, 11)}.
For example, we can calculate (g ◦ f)(3) as follows.
(g ◦ f)(3) = g(f(3)) = g(9) = 13.
Which means (3, 13) ∈ g ◦ f .
Example 17. Let f : Z −→ Z by f(x) = x2 + 1 and g : Z −→ Z by g(x) = 2x− 3.
For example, we can calculate (g ◦ f)(3) as follows.
(g ◦ f)(3) = g(f(3)) = g(32 + 1) = g(10) = 2× 10− 3 = 17.
In general,
(g ◦ f)(x) = g(f(x))
= g(x2 + 1)
= 2(x2 + 1)− 3
= 2x2 + 2− 3
= 2x2 − 1
Note that you may verify the value of (g◦f)(3) by plugging 3 into the general expression for (g◦f)(x). We also
note that the composition of functions is not commutative. For this example, we see that (g◦f)(3) 6= (f◦g)(3):
(f ◦ g)(3) = f(g(3)) = f(2× 3− 3) = f(3) = 32 + 1 = 10.
To prove that two functions f and g are equal, we must show that:
1. The domain of f equals the domain of g; and
2. For every x in their common domain, f(x) = g(x).
Refer to Proof Template 22 on p. 185 of your textbook.
So in the previous example, g ◦ f 6= f ◦ g since we showed that (g ◦ f)(3) 6= (f ◦ g)(3) (which violates the
second condition above).
The composition of functions is associative. For f : A −→ B, g : B −→ C and h : C −→ D we have
h ◦ (g ◦ f) = (h ◦ g) ◦ f.
This is proved in Proposition 26.6 (p. 185) of your textbook.
Definition 18 (Identity function). The identity function on a set A, idA : A→ A, is defined as idA(a) = a
for all a ∈ A.
The identity function is a bijection. For example, the identify function on N, denoted as a set of ordered
pairs, is
idN = {(0, 0), (1, 1), (2, 2), (3, 3), . . .}.
Example 19. Let A and B be sets, and let f : A −→ B. We will prove that f ◦ idA = idB ◦ f = f , using
Proof Template 22.
CISC 203: Discrete Mathematics for Computing II
Module 6, Fall 2021 Page 6
Proof. The first condition of Proof Template 22 is satisfied, since we have:
dom (f ◦ idA) = dom (idA) = A = dom (f)
and
dom (idB ◦ f) = dom (f)
The second condition of Proof Template 22 is satisfied, since we have:
(f ◦ idA)(a) = f(idA(a)) = f(a)
and
(idB ◦ f)(a) = idB(f(a)) = f(a).
So, we have shown that f ◦ idA = idB ◦ f = f .
Proposition 20. Let A and B be sets and suppose f : A −→ B is one-to-one and onto. Then,
f−1 ◦ f = idA
and
f ◦ f−1 = idB ,
where f−1 is the inverse of f .
Exercise
Prove the above proposition, using the same technique (i.e., with Proof Template 22).
4 Permutations
Definition 21 (Permutation). Given a set A, a permutation of A is a bijective function π : A→ A.
A permutation is a function that maps elements of a set A to elements of the same set A. In other words,
if our informal definition of a permutation is an arrangement of elements, then the permutation π itself is
what performs the rearranging of elements.
Example 22. Suppose we have a set A = {1, 2, 3, 4, 5, 6}. Let π : A −→ A be a function given by:
π(1) = 3; π(4) = 2;
π(2) = 4; π(5) = 1;
π(3) = 5; π(6) = 6.
We see that π is a bijection from A to A.
We can more compactly represent the permutation π from the previous example using certain notations.
The two-line notation uses a two-line matrix; the first line lists the elements of the set A, and the second
line lists the permuted elements π(1) through π(6). Thus,
π =
[
1 2 3 4 5 6
3 4 5 2 1 6
]
.
What happens if we compose π with itself? Let’s trace what happens to the element 1. We are going to
apply π twice: The first application maps 1 to 3, and the second application maps 3 to 5. If we apply π
a third time, 5 is mapped back to 1. Treating π as a function, we see that π(1) = 3, (π ◦ π)(1) = 5, and
CISC 203: Discrete Mathematics for Computing II
Module 6, Fall 2021 Page 7
(π ◦ π ◦ π)(1) = 1. We can write this cycle as (1, 3, 5). Repeating the same process by tracing the elements
2 and 6 gives us the two cycles (2, 4) and (6), respectively. So in cycle notation, we can write
π = (1, 3, 5)(2, 4)(6).
In this notation, each set of parentheses represents a cycle, where the first element is mapped to the second
element, the second element is mapped to the third element, and so on, and the last element is mapped back
to the first element. Since the element 6 is always mapped to 6, we can leave that cycle out, giving us
π = (1, 3, 5)(2, 4).
Note that we can write π ◦ π as π2, π ◦ π ◦ π as π3, and so on.
Composing permutations is just like composing other functions. If π and σ are permutations on a set, we
can write π ◦ σ to represent the result of applying σ (as a function) and then applying π.
Example 23. Let
π =
[
1 2 3 4
4 1 3 2
]
and σ =
[
1 2 3 4
2 3 4 1
]
.
We calculate π ◦ σ as follows:
π ◦ σ(1) = π(σ(1)) = π(2) = 1
π ◦ σ(2) = π(σ(2)) = π(3) = 3
π ◦ σ(3) = π(σ(3)) = π(4) = 2
π ◦ σ(4) = π(σ(4)) = π(1) = 4
The result is in fact another permutation. This follows from the fact that the composition of two bijections
will always be a bijection. We can create a diagram to visualize the composition of these two permutations,
as follows.
Figure 1: Visual representation of the composition of π and σ in Example 23.
We can also just think of the operation of a permutation as “turns x into y”, so we can interpret π ◦ σ(3) as
“σ turns 3 into 4, then π turns 4 into 2”.
Exercise
Write π, σ, π ◦ σ, σ ◦ π from the previous example in cycle notation.
Theorem 24. Every permutation can be expressed as a collection of pairwise disjoint cycles. Furthermore,
this representation is unique up to rearranging the cycles and cyclic order of the elements within cycles.
CISC 203: Discrete Mathematics for Computing II
Module 6, Fall 2021 Page 8
Definition 25 (Sn). The set of all permutations on the set {1, 2, . . . , n} is denoted Sn. Sn is called the
symmetric group on n elements—we will revisit this when we cover Groups later in the course.
Example 26. Here, we list all permutations on the set {1, 2} and on the set {1, 2, 3}.
S2 =
{[
1 2
1 2
]
,
[
1 2
2 1
]}
= {(1)(2), (1, 2)}
S3 =
{[
1 2 3
1 2 3
]
,
[
1 2 3
2 1 3
]
,
[
1 2 3
3 2 1
]
,
[
1 2 3
1 3 2
]
,
[
1 2 3
2 3 1
]
,
[
1 2 3
3 1 2
]}
= {(1)(2)(3), (1, 2)(3), (1, 3)(2), (1)(2, 3), (1, 2, 3), (1, 3, 2)}
Note that in S2, (1)(2) = id{1,2} is the identity function on the set {1, 2}. In S3, (1)(2)(3) = id{1,2,3} is the
identity function on the set {1, 2, 3}. For the identity function, we typically simplify the cycle notation to
(1), so we can write id{1,2} = (1) and id{1,2,3} = (1) without any confusion.
We denote the identity function with the Greek letter ι. In fact we almost always use Greek letters to name
permutations: π, σ, and τ are among the favourites.
Example 27. Let π ∈ S9 be given by
π =
[
1 2 3 4 5 6 7 8 9
1 2 6 4 5 3 7 8 9
]
.
In cycle notation, π = (1)(2)(3, 6)(4)(5)(7)(8)(9) = (3, 6). We write ι ∈ S9 as ι = (1).
Proposition 28. There are n! permutations in Sn. The set Sn satisfies the following properties.
1. Closure: If π ∈ Sn and σ ∈ Sn, then π ◦ σ ∈ Sn.
2. Associativity: If π ∈ Sn and σ ∈ Sn and τ ∈ Sn, then π ◦ (σ ◦ τ) = (π ◦ σ) ◦ τ .
3. Identity element: There is a permutation ι such that π ◦ ι = ι ◦ π = π,∀π ∈ Sn.
4. Inverse: If π ∈ Sn, then π−1 ∈ Sn and π ◦ π−1 = π−1 ◦ π = ι.
Each of the above properties follow from the definition of permutations and the properties of functions.
Property 1 says that the composition of two permutations is another permutation. This sounds trivial but
it is our first look at a very important concept: closure. When we apply an operation to two elements of a
set and always get another element of the same set, we say that set is closed under that operation.
Not all sets are closed under all operations. For example, N is not closed under the operation of subtraction
(for instance, 3 ∈ N and 4 ∈ N, but 3 − 4 = −1, and −1 /∈ N). However, N is closed under addition and
multiplication. This concept is vital to us as computer scientists because we frequently work with strongly
typed programming languages, where each variable has a specific type that cannot change. If we are dealing
with integer variables, we need to be sure the operations we perform will only produce integer values.
Property 2 is called the associative property. It says that if we are composing a sequence of permutations
we can group them with parentheses in different ways without changing the result.
Property 3 asserts that the identity permutation ι can be composed with any permutation without changing
it. Once again, we can draw a parallel to other sets and operations. For example, in the set N and the
operation of multiplication, we know that for all x ∈ N, x× 1 = 1× x = x.
Property 4 asserts that every permutation has an inverse. This property is also true for some sets and
operations but not all. For example, in the set Z and the operation of addition, the identity element is 0 and
every element has an inverse (for instance, the inverse of 7 is -7). However in the set N and the operation of
CISC 203: Discrete Mathematics for Computing II
Module 6, Fall 2021 Page 9
addition, the identity element is still 0 but the non-zero values do not have inverses (for instance there is no
integer x ∈ N such that 8 + x = 0).
Property 4 is particularly important when we use permutations in cryptography—there’s not much point
encoding information with a permutation if there is not some other permutation that will do the decoding.
Side note: A set and an operation that satisfy these four properties are called a group. Group theory is one
of the most important branches of mathematics, with applications in communications, theoretical physics,
applied physics, biology, chemistry, robotics and many other fields. We will learn about groups in Chapter
8.
Note that there is a property possessed by many operations that is not true of the composition of permu-
tations: commutativity. Commutativity holds when we can switch the left-to-right order of the operands
without changing the result. For example, when we are adding integers, we know that x + y = y + x and
the same is true for multiplication. Not all operations are commutative. For example, subtraction is not
commutative: x− y 6= y − x except when x = y. Composition of permutations is not commutative.
In general, π ◦ σ 6= σ ◦ π (but they can be equal in some special cases).
Example 29. Given permutations π and σ in Sn, we can always find a permutation α such that π ◦α = σ:
π ◦ α = σ
π−1 ◦ (π ◦ α) = π−1 ◦ σ
(π−1 ◦ π) ◦ α = π−1 ◦ σ
ι ◦ α = π−1 ◦ σ
α = π−1 ◦ σ
It’s easy to check that this is correct: If we take π ◦ α and replace α by π−1 ◦ σ, we get:
π ◦ α = π ◦ (π−1 ◦ σ)
= (π ◦ π−1) ◦ σ
= ι ◦ σ
= σ
But this means that to find α we need to know π−1. We will see that there are at least two simple ways to
calculate π−1 when we are given π.
4.1 Computing the Inverse of a Permutation
Suppose we have a permutation π and we need to compute π−1. We could do it from the standard matrix
representation.
Example 30. Consider
π =
[
1 2 3 4 5 6 7
4 1 5 2 7 3 6
]
.
To compute π−1, we can see that π(1) = 4, so we know that π−1(4) = 1. Similarly, we see that π(4) = 2, so
we know that π−1(2) = 4, and so on. Then, we obtain
π−1 =
[
1 2 3 4 5 6 7
2 4 6 1 3 7 5
]
.
But with the permutation expressed in cycle notation, computing π−1 is simpler: we just reverse each cycle.
The cycle notation of π is (1, 4, 2)(3, 5, 7, 6), so π−1 is simply (2, 4, 1)(6, 7, 5, 3).
CISC 203: Discrete Mathematics for Computing II
Module 6, Fall 2021 Page 10
Note that reversing a cycle is very different from rotating a cycle: if we consider the (a, b, c, d), the cycle
(c, d, a, b) is equivalent, but the cycle (d, c, b, a) is the inverse. It is a common practice to start each cycle
with the lowest number within the cycle, and to order the cycles so that the initial values are in ascending
order. So, we can rewrite π−1 in this example as (1, 2, 4)(3, 6, 7, 5).
4.2 Transpositions
Definition 31 (Transposition). A permutation τ ∈ Sn is called a transposition, provided
• there exist i, j ∈ {1, 2, . . . , n} with i 6= j so that τ(i) = j and τ(j) = i, and
• for all k ∈ {1, 2, . . . , n) with k 6= i and k 6= j, we have τ(k) = k.
Trapositions exchange one pair of elements, and map each of the remaining elements to themselves. We have
already encountered a transposition in Example 27. We now give two examples that show how to write any
permutation as a composition of transpositions. Observe that there is a nice trick for converting a cycle into
a composition of transpositions.
Example 32. Let π = (1, 2, 3, 4, 5). We write π as the composition of transpositions as
(1, 2, 3, 4, 5) = (1, 5) ◦ (1, 4) ◦ (1, 3) ◦ (1, 2).
Example 33. Let π = (1, 4, 2)(3, 5, 7, 6). We write π as the composition of transpositions as
(1, 4, 2)(3, 5, 7, 6) = (1, 2) ◦ (1, 4) ◦ (3, 6) ◦ (3, 7) ◦ (3, 5).
Exercise
Write the permutation π =
[
1 2 3 4 5 6 7 8 9
2 4 1 6 5 3 8 9 7
]
as (i) in cycle notation (i.e., as a composition of disjoint
cycles), and (ii) as a composition of transpositions.
Note that the decomposition of a permutation into transpositions is not unique, e.g.,
(1, 2, 3, 4) = (1, 4) ◦ (1, 3) ◦ (1, 2)
= (1, 2) ◦ (2, 3) ◦ (3, 4)
= (1, 2) ◦ (1, 4) ◦ (2, 3) ◦ (1, 4) ◦ (3, 4).
However, note that each decomposition has an odd number of transpositions. More generally, we have the
following theorem.
Theorem 34. Let π ∈ Sn. Consider any two decompositions of π that we denote as
π = τ1 ◦ τ2 ◦ · · · ◦ τa,
and
π = σ1 ◦ σ2 ◦ · · · ◦ σb.
Then, a and b must have the same parity, i.e., they are both odd or both even.
Proof. See the proof of Theorem 27.12 on p. 193 of the textbook.
This theorem allows us to give the following definition, which we will revisit when we study groups.
Definition 35 (Even and odd permutations). Let π be a permutation on a finite set. We call π even
provided it can be written as the composition of an even number of transpositions. Otherwise, it can be
written as the composition of an odd number of transpositions, in which case we call π odd.
Functions
Inverse functions
The Pigeonhole Principle
Composition
Permutations
Computing the Inverse of a Permutation
Transpositions